Nacimiento de la Teoria de Grafos

La Teoría de Grafos, el subcampo de las matematicas y de ciencia de la computación que proporciona las definiciones, herramientas, técnicas y resultados para los grafos, es lo que está detras de la ciencia de redes. La teoŕia de grafos es de los pocos campos de la ciencia que tienen una fecha de nacimiento, nacio cuando Euler resolvio el problema de los puentes de Königsberg en 1735.

El problema consistia en encontrar un camino, que inicie y termine en el mismo punto, que pasara a traves de todos los puentes pasando solo una vez por cada puente. La siguiente figura muestra los puentes de Königsberg, la izquierda contiene una mapa de la epoca de Königsberg, la central es un esquema de los puentes y las partes que conectan y derecha muestra el grafo correspondiente.

Puentes de Kónisberg

La solución del problema por Euler fue la primera vez que un problema matematico se resolvio usando grafos, algunos problemas se vuelven más sencillos y más abordables si se representacon como grafos. ¿Lo serán los sistemas complejos?

Redes y Grafos

Si queremos comprender los sistemas complejos, primero necesitamos comprender como interactuan sus componentes entre ellos; necesitamos un mapa de sus interacciones.

Una red es una representación de los componentes del sistema, nodos, y las interacciones directas entre ellos, enlaces. Ésta representación ofrece un lenguage común para estudiar sistemas diferentes en naturaleza, apariencia u objetivos.

La figura muestra una pequeña parte de (a) el internet, en el cual routers están conectados entre ellos, (b) la red de actores de Hollywood, donde dos actores están conectados si han participado en la misma pelicula, (c) una red de interacción entre proteinas, están conectadas si hay evidencia de que pueden unirse dentro de la celula.
ejemplos de redes

La figura introduce dos parametros básicos de la teoría de redes:

La red de la figura anterior tiene \(N = 4\) y \(L = 4\).

Los enlaces de una red pueden ser dirigidos o no dirigidos; los enlaces son dirigidos cuando hay una direccion en las interacciones, como en enlaces en las paginas web, o son no dirigidos cuando la interacción es mutua, como los lazos de amistad. Una red es dirigida sí todos sus nodos son dirigidos, y es no dirigida si todos sus nodos son no dirigidos.

Usualmente tendremos que construir la red, a partir de mediciones en algunos elementos y las interacciones entre ellos. La elección de lo que es un elemento y una interacción, tanto como las mediciones que se toman de cada una son muy importantes; es lo que determina no solo que tipo de red puede construirse, sino también los posibles análisis y las conclusiones a extraer.

Por ejemplo, uniendo amigos entre sí podemos obtener la red de amistad, importante en la dispersión de la ideas, productos o habitos, importantes en sociologia, en el mercadotecnia y en las ciencias de la salud.

Grado, grado promedio y distribución de grado

Una propiedad importante de cada nodo es su grado, que es el número de enlaces que tiene hacia los otros nodos.

Grado

El grado del nodo \(i_{esimo}\) de una red se denota con \(k_{i}\); por ejemplo, para la red no dirigida de la figura anterior se tiene \(k_{1} = 2\), \(k_{2} = 3\), \(k_{3} = 2\) y \(k_{4} = 1\). En una red no dirigida el número total de enlaces, \(L\), puede expresarse como la suma de los grados de los nodos.

\[ L = \frac{1}{2}\sum_{i = 1}^ {N} k_{i}\]

El factor \(1 / 2\) corrige el hecho de que cada nodo es contado dos veces.

Grado promedio

Una propiedad importante de una red es su grado promedio, el cual para una red no dirigida es:

\[\langle k \rangle = \frac{1}{2} \sum_{1 = 1}^{N} k_{i} = \frac{2L}{N}\]

En las redes dirigidas se distingue entre el grado entrante, \(k_{i}^{en}\), representando el número de enlaces que apuntan hacia el nodo \(i\), y el grado saliente, \(k_{i}^{sa}\), que es el número de enlaces que salen del nodo \(i\). En las redes no dirigidas, el grado total de un nodo es: \[k_{i} = k_{i}^{en} + k_{i}^{sa}\] Mientras que \(L\) es: \[L = \sum_{i = 1}^ {N} k_{i}^{en} = \sum_{i = 1}^ {N} k_{i}^{sa}\] Para el grado promedio se tiene: \[\langle k^{en} \rangle = \frac{1}{N} \sum_{i = 1}^ {N} k_{i}^{en} =\langle k^{sa} \rangle = \frac{1}{N} \sum_{i = 1}^ {N} k_{i}^{sa} = \frac{L}{N}\]

Distribución de grado

La distribución de grado, \(p_{k}\), da la probabilidad de que un nodo elegido al azar de la red tenga grado \(k\). Al ser \(p_{k}\) una probabilidad, está normalizada: \(\sum_{k = 1}^{\infty} p_{k} = 1\).

Para una red con grado \(k\), la distribución de grado es el histograma normalizado: \[p_{k} = \frac{N_{k}}{N}\] donde \(N_{k}\) es el número de nodos con grado \(k\).

La distribución de grado es muy importante, es de las primeras cosas que calculamos de la red. Por un lado, conocer \(p_{k}\) permite calcular la mayoria de las propiedades de la red; y por otro, la forma particular de \(p_{k}\) determina muchos procesos en la red, de la robustez al flujo de la información.

Matriz de adyacencia

Las interacciones en una red pueden ser expresadas en una matriz binaria \(N x N\) simetrica \(A\) con entradas

\(A\) es llamada matriz de adyacencia, es muy útil, pues no solo sirve para guardar información de los enlaces, sino porque ciertas operaciones en \(A\) proporcionan información del grafo.
Por ejemplo, la suma sobre el renglon \(i\) proporciona el grado de ese nodo, en una red no dirigida; si \(A^{r}\) es la \(r\)-ava potencia de \(A\), la entrada \(A_{ij}^{r}\) contiene el número de caminatas de largo \(r\) entre el nodo \(i\) y el \(j\) en el grafo; también hay varias relaciones interesantes que involucran los eigenvalores de \(A\).

Las matrices reales son dispersas

\(A\) es una manera común de guardar los datos que representan un grafo; sin embargo, si el grafo es muy grande, y especialmente si \(A\) es una matriz dispersa, es preferible usar una lista de adyacencia. Debido a que en esos casos \(A\) será grande y llenada principalmente con \(0\)’s, porque muestra explicitamente si existe un enlace o no; por el otro lado, la lista de adyacencia solo guarda información de los enlaces presentes.

La lista de adyacencia de un grafo es una lista, ordenada de la misma manera que los nodos, donde la entrada \(i\)-esima contiene todos los nodos con los que el nodo \(i\) tiene un enlace. Una variación es la lista de enlaces, una matriz de dos columnas donde cada renglon es un par de nodos que tienen un enlace entre sí.

Redes pesadas

Hay muchos sistemas que se representan mejor por una red pesada, donde cada enlace \((i,j)\) tiene un peso \(w_{ij}\). Por ejemplo, en la red de llamadas telefonicas el peso podría representar el número de minutos que los dos individuos hablan entre ellos.
En las redes pesadas los elementos de \(A\) indican el peso del enlace así: \(A_{ij} = w_{ij}\). A pesar de que la mayoría de las redes son pesadas, no siempre es facil asignar el peso \(w_{ij}\) apropiado a cada enlace; por ello es usual aproximar tales redes como no pesadas, donde \(w_{ij} = 1\).

Redes Bipartitas

Un grafo bipartito es una red cuyos nodos pueden ser divididos en dos conjuntos disjuntos \(U\) y \(V\) de tal manera que cada enlace une un nodo de \(U\) con uno de \(V\).

Es usual inducir dos subgrafos de cualquier grafica bipartita. En el primero hay un enlace entre dos nodos de \(U\) si ambos tienen un enlace a un nodo en \(V\) en la grafica bipartita. En el segundo dos nodos de \(V\) están enlazados si tienen un nodo común en \(V\).

Es facil definir grafos multipartitos, en los cuales los nodos grafo se pueden separar en varios conjuntos disjuntos, de tal manera que no haya enlaces entre nodos de un mismo grupo.

Caminatas y distancias

Es útil discutir el concepto de “movimiento” en un grafo. Un paseo en un grafo, del nodo \(0\) al \(j\) es una secuencia alternante \(\{0,e_{0,1},\ldots,e_{j-1,j},j\}\), donde \(e_{m,n}\) indica el enlace del nodo \(m\) al \(n\); la longitud de ésta caminata es \(j\). Entre los refinamientos de los paseos están los recorridos, los cuales son paseos sin enlaces repetidos, y los caminos que son recorridos que no repiten nodos.

Un recorrido en el que el nodo de inicio y el nodo final es el mismo recibe el nombre de circuito. De manera similar, una caminata, de al menos longitud tres, cuyo nodo final e inicial son el mismo pero en la cual los demas nodos no se repiten, se llama ciclo. Los grafos sin ciclos son llamados aciclicos.

paseos, recorridos y caminos

El paseo mostrado en (a) sigue la ruta \(1 \rightarrow 2 \rightarrow 5\rightarrow 4 \rightarrow 2 \rightarrow 5 \rightarrow 7\), por lo que su longitud es 6. El camino más corto entre los nodos \(1\) y \(7\), \(d_{1,7}\), es el camino con menor número de enlaces que conecta los nodos \(1\) y \(7\) , puede haber varios caminos de la misma longitud, como los dos caminos que se muestran en diferente color en (b).

Geodésicas

El camino más corto, o geodesica, entre el nodo \(i\) y \(j\) es el paseo que contiene el menor numero de enlaces, se denota por \(d_{ij}\), o simplemente \(d\), puede haber varias geodesicas entre un par de nodos.

En una red no dirigida la distancia entre el nodo \(i\) y el \(j\) es igual a la distancia entre el nodo \(j\) e \(i\). En una red dirigida usualmente \(d_{ij} \neq d_{ji}\); mas aún, la existencia de un paseo de \(i\) a \(j\) no garantiza la existencia de uno de \(j\) a \(i\).

Diametro de la red

El diametro de una red, denotado por \(d_{max}\), es la geodesica más grande en la red. En otras palabras, es la distancia más grande entre todos los pares de nodos de la red.

Distancia promedio

La distancia promedio, \(\langle d \rangle\), es la distancia promedio entre todos los pares de nodos de un componente de una red.

Conectividad

Un vertice \(i\) en un grafo \(G\) se dice alcanzable desde otro nodo \(j\) si existe un paseo de \(i\) a \(j\). El grafo \(G\) es conectado si cada nodo es alcanzable desde cualquier otro. Un componente de un grafo, es un subgrafo conectado máximo, cualquier adición de otro nodo arruinaría la propiedad de conectividad.

Coeficientes de Agrupamiento

El coeficiente de agrupamiento captura que tanto los vecinos de un nodo interactuan entre ellos. Para un nodo \(i\) con grado \(k_{i}\) el coeficiente de agrupamiento local está definido como:

\[C_{i} = \frac{2 L_{i}}{k_{i}(k_{i} - 1)}\] donde \(L_{i}\) es el número de enlaces entre los \(k_{i}\) vecinos del nodo \(i\); \(C_{i}\) esta entre 0 y 1.

El grado de agrupamiento de la red completa está capturado por el coeficiente de agrupamiento promedio, \(\langle C \rangle\), el cual es el promedio de \(C_{i}\) de todos los nodos:

\[\langle C \rangle = \frac{1}{N}\sum_{1 = 1}^{N} C_{i}\] \(\langle C \rangle\) es la probabilidad de que dos vecinos de un nodo elegido al azar tengan un enlace entre ellos.

Coeficiente de agrupamiento global

También hay un coeficiente de agrupamiento global, \(C\), que mide el número total de triangulos cerrados en una red. \(C\) está definido como:

\[C = \frac{3 x \textit{número de triangulos}}{\textit{número de tripletes conectados}}\]

donde el número de tripletes conectados es un conjunto ordenado de tres nodos \(ABC\) de tal modo que \(A\) tiene un enlace con \(B\) y \(B\) tiene un enlace con \(C\).

Por ejemplo, un triángulo \(A\), \(B\), \(C\) está hecho de los tres tripletes, \(ABC\), \(BCA\) y \(CAB\); mientras que una cadena \(A\), \(B\), \(C\) en la cual \(A\) esté conectado con \(B\) y \(B\) con \(C\), pero donde el \(A\) no éste enlazada con \(C\), forma un triplete \(ABC\) abierto. Hay que notar que \(\langle C \rangle\) y \(C\) no son equivalentes.

ejemplo de coeficientes de agrupamiento

En la imagen se muestra un ejemplo de los coeficientes de agrupamiento; en (a) está el \(C_{i}\) del nodo central, con grado \(k_{i} = 4\), para tres configuraciones de la red. En (b) se muestra una red pequeña, con el \(C_{i}\) para cada nodo, junto con \(\langle C \rangle\) y \(C\).

Bibliografía

Ésta introducción a la Ciencia de Redes es en su mayoría una traducción, a mi manera, del capítulo dos del libro Networks Science con extractos del libro Statistical Analysis of Network Data y de su versión práctica Statistical Analysis of Network Data with R.

Considero éste reporte la versión 0.1, así que tiene muchos errores. Iré mejorando el reporte paulatinente, conforme vaya aclarando las ideas expuestas y mis habilidades de programación mejoren. De cualquier modo, creo que conservaré los temas y el orden.

Apreciare cualquier comentario