Ediciones ENI Editorial | líder en informática
Grafos y redes
Introducción
El estudio de grafos cubre varios aspectos. Se estudian las diferencias o similitudes principales entre grafos, partes de grafos o nodos de grafos (generalmente, en un grafo o parte de un grafo).
El capítulo Introducción presenta la noción de grado, que es una feature sencilla, pero desafortunadamente no es suficiente para cualificar grafos y nodos.
Los nodos (kernels) que se aplican a los grafos permiten capturar y manipular varias características de la estructura de los grafos usando nuestras técnicas habituales de machine learning, pero no vamos a tratar esto aquí. Este capítulo se centra en los aspectos realmente específicos de los grafos.
Primeros pasos
La teoría de grafos incluye numerosos conceptos, teoremas y notaciones muy precisos, aunque algo molestos, porque las definiciones varían entre diferentes autores. No definimos matemáticamente todos los conceptos subyacentes al uso de grafos porque no bastaría con un capítulo. Aquí encontrará una selección de términos clásicos y definiciones «en castellano» que son útiles para manipular grafos en un contexto operativo. En caso de duda, consulte las fuentes citadas en la introducción del libro.
1. Algunas nociones y notaciones adicionales básicas
Es necesario empaparse de las siguientes nociones y reconocerlas en los grafos que encuentre.
Un grafo finito no orientado sin bucle (loop), es decir, un grafo simple (undirected simple) no orientado se escribe G(V, E). Atención, algunas veces denotamos de la misma manera grafos de otra naturaleza (no simples, orientados, hipergrafos, etc.).
Sus nodos o vértices se escriben V(G) = {v1,,..., vn}.
Apunte de vocabulario: en inglés vertices es el plural de vertex.
Sus aristas o edges se escriben E(G) = {e1,,...,en}.
Cuando no hay ambigüedad, no es necesario escribir la (G).
Las aristas o bordes son los elementos del producto cartesiano V x V.
Dos nodos distintos son adyacentes cuando comparten la misma arista.
Dos aristas distintas son adyacentes cuando comparten un solo nodo.
Una cadena (walk) entre dos nodos distintos, es decir, sus extremos es un grafo de nodos adyacentes de modo que solo los extremos tienen un grado igual a 1 dentro de este grafo. Algunas veces hablamos de una cadena abierta u open walk.
Una cadena elemental (trail) es una cadena cuyo grado máximo de un nodo es 2, es decir, se trata de una cadena que nunca pasa por el mismo nodo (atención, en algunos textos el término cadena hacer referencia a una cadena elemental).
Un ciclo (closed walk cycle) es un grafo de nodos adyacentes de grado mayor o igual a 2 dentro de este grafo.
Un ciclo elemental es un ciclo cuyos nodos tienen exactamente un grado igual a 2. Atención: en algunos textos el término ciclo hace referencia a un ciclo elemental.
Un ciclo de orden n se puede escribir Cn.
Un grafo completo de orden n que se ha formado conectando todos los nodos, se puede escribir como Kn.
El orden (order) del grafo que se corresponde con el número...
Grafos y redes (sociales)
Los conceptos que vamos a implementar aquí no son específicos del estudio de las redes sociales, pero se utilizan mucho en este contexto.
Una red social está formada por actores (humanos, grupos de humanos o personas jurídicas, etc.), las cuales están relacionadas a través de vínculos sociales, que normalmente establecen interacciones, síncronas o no.
Evidentemente, se acostumbra a representar los actores usando nodos, y las relaciones con aristas o arcos, construyendo lo que algunas veces se denomina sociograma cuando las relaciones llevan directa o indirectamente a conceptos de afinidad entre los actores (quién es elegido por quién, quién es líder, etc.).
Las relaciones pueden ser estructurales (usadas por, colega de, etc.), fácticas (dialoga con, participar en… con…) o declarativas (like…, me gusta…). A menudo, estas relaciones se extienden a los objetos que rodean a los actores: «A tal y tal le gusta tal o cual película».
Cuando las relaciones son simétricas, como estar unidos en LinkedIn, por ejemplo, obtenemos grafos no orientados. Cuando los grafos representan la expresión de opiniones (sobre alguien o algo) o cuando representan las suscripciones a servicios o el envío de tweets o correos electrónicos, se generan grafos orientados.
Si se cuantifica la relación como la cantidad de tweets que se envían a alguien, la cantidad de estrellas que indican que nos gusta algo, el número de enlaces comunes, emoticonos, etc., estamos ante un grafo valorado (que incluye pesos, weights en inglés).
Los tipos de relaciones están etiquetados en los arcos o aristas (colega, follower, etc.).
1. Análisis de las redes sociales: conceptos básicos
Los conceptos más utilizados en el análisis de redes sociales son la densidad de enlaces de la red (density of links) y la centralidad (centrality).
La densidad de enlaces representa el número de enlaces reales frente al número de enlaces posibles. Aparece cuando ciertas partes del grafo tienen muchos vínculos (a menudo hablamos de comunidades) y los vínculos entre estas comunidades son relativamente escasos. Esta es una forma conveniente de definir los clústeres de un grafo.
La centralidad es una noción más sutil...
