Capítulo 4 - Análisis descriptivo de las características de los grafos

(Extraído de: [1] "Statistical Analysis of Network Data with R")

4.1 Introducción 

En el estudio de un sistema complejo determinado, pueden surgir preguntas de interés sobre  aspectos de la estructura o características del grafo correspondiente. Tradicionalmente, el análisis estructural de un grafo se ha tratado  como una tarea descriptiva, en lugar de una tarea inferencial, y las herramientas comúnmente utilizadas para tales propósitos derivan en gran parte de áreas que están fuera de  la estadística "convencional". Por ejemplo, una proporción abrumadora de estas herramientas provienen principalmente del campo de la teoría de grafos y por lo tanto tienen sus orígenes en la matemática e informática. En este capítulo se presenta una breve descripción general de algunas de las muchas herramientas disponibles, comenzando con un resumen de las características de los vértices y aristas, en la sección 4.2, continuando con las medidas de cohesión de una red, en la sección 4.3, y con métodos para la partición de grafos, en la sección 4.4, y terminando con los temas de assortividad y mezcla, en la sección 4.5.

4.2 Características de los vértices y aristas

4.2.1 Grado de un vértice

El grado $d_v$ de un vértice $v$, en un grafo $G = (V, E)$, cuenta el número de aristas en $E$ que inciden sobre $v$. Dado un grafo $G$, se define $f_d$ como la fracción de vértices $v \in V$ con grado $d_v = d$. La colección $\lbrace f_d \rbrace$ con $d \geq 0$ se llama distribución de grados de $G$, y es simplemente un cambio de escala del conjunto de frecuencias de grados, formado a partir de la secuencia de grados original. La distribución de grados para el grafo del club de karate (Figura 4.1.2) se muestra a continuación usando un histograma.

1 > library(igraph)

2 > library(sand)

3 > data(karate)

4 > hist(degree(karate), col="lightblue", xlim=c(0, 50),

5 + xlab="Grado del vértice", ylab="Frecuencia", main="")

Figura 4.1.1

Donde el grafo cuenta con la siguiente estructura:

6 > plot(karate)

Figura 4.1.2

Podemos ver que los dos vértices más conectados corresponden a los actores 1 y 34 del grafo, representando al instructor y administrador. 

Donde los grados de los vértices son: 

> degree(karate)

Mr Hi  Actor 2  Actor 3  Actor 4  Actor 5  Actor 6  Actor 7  Actor 8  Actor 9 

   16        9       10        6        3        4        4        4        5 

Actor 10 Actor 11 Actor 12 Actor 13 Actor 14 Actor 15 Actor 16 Actor 17 Actor 18 

       2        3        1        2        5        2        2        2        2 

Actor 19 Actor 20 Actor 21 Actor 22 Actor 23 Actor 24 Actor 25 Actor 26 Actor 27 

       2        3        2        2        2        5        3        3        2 

Actor 28 Actor 29 Actor 30 Actor 31 Actor 32 Actor 33   John A 

       4        3        4        4        6       12       17 

Para grafos ponderados, una generalización útil de grado es la noción de fuerza del vértice, que se obtiene simplemente sumando los pesos de las aristas incidentes a un vértice dado. La distribución de la fuerza a veces denominada distribución de grados ponderados, es definida en analogía con la distribución de grados ordinaria. A continuación, con el siguiente histograma podemos ilustrar, la fuerza del vértice para el grafo del club de karate. 

 1 > hist(graph.strength(karate), col="pink",

 2 + xlab="Fuerza del vértice", ylab="Frecuencia", main="")

Figura 4.1.3

Para este grafo, el rango de la fuerza del vértice se extiende mucho más allá del grado del vértice, y se pierde la distinción observada anteriormente entre los tres grupos de vértices (Figura 4.1.1). Sin embargo, se podría decir que ambos histogramas comunican información importante sobre el grafo. 

Nota: Entre las métricas aplicables a grafos ponderados tenemos como medida la ya mencionada fuerza del vértice. 

Las distribuciones de grados pueden exhibir una variedad de formas. Para una red de interacciones entre pares de proteínas en levadura, por ejemplo:

1 > library(igraphdata) 

2 > data(yeast)

4 > d.yeast <- degree(yeast)

5 > hist(d.yeast,col="blue",

6 + xlab="Grado", ylab="Frecuencia",

7 + main="Distribución de grados")

Figura 4.1.4

En particular, si bien hay una fracción sustancial de vértices de grado bastante bajo, de un orden de magnitud similar a los del grafo del club de karate, también hay un número no trivial de vértices con grados en órdenes de magnitud sucesivamente superiores.

Además del histograma presentado(Figura 4.1.4), una escala logarítmica es efectiva al resumir la información, donde obtenemos:

Figura 4.1.5 Distribución de grados para una red de interacciones proteína-proteína en levadura en escala logarítmica. 

Más allá de la distribución de grados en sí, puede ser interesante comprender como se enlazan vértices de diferentes grados entre sí. Esta característica es la noción de grado medio de los vecinos de un vértice dado. Por ejemplo, una gráfica del grado de vecinos promedio versus grado del vértice en los datos de levadura, como se muestra a continuación, sugiere que, si bien existe una tendencia a vértices de grados más altos para enlazar con vértices similares, los vértices de grado más bajo tienden a enlazarse con vértices de grados inferiores y superiores.

1 > a.nn.deg.yeast <- graph.knn(yeast,V(yeast))$knn

2 > plot(d.yeast, a.nn.deg.yeast, log="xy",

3 + col="goldenrod", xlab=c("Grado del vértice(escala logarítmica)"),

4 + ylab=c("Grado de vecino promedio(escala logarítmica)"))

Figura 4.1.6, Grado de vecinos promedio versus grado del vértice (escala logarítmica) para los datos de levadura

4.2.2 Centralidad de un vértice 

La centralidad es una medida de la importancia relativa de un vértice dentro del grafo. Esta importancia no es una propiedad intrínseca del vértice, si no que viene determinada por la posición de éste en el grafo.

Existen múltiples métricas que permiten determinar la centralidad de un vértice. Estas métricas se clasifican en dos grupos: métricas radiales y mediales. En las métricas radiales el vértice en cuestión es origen o destino de caminos generados con un cierto criterio, y la métrica de centralidad determina la cantidad de caminos existentes (métrica de volumen) o la longitud de estos (métrica de longitud). Sin embargo, en las métricas mediales se emplea para determinar la centralidad de los vértices y la cantidad de caminos que atraviesan dicho vértice.[2] Algunas de las métricas de centralidad más importantes son la centralidad de grado, de cercanía, de proximidad y de vector propio.

• Centralidad de grado

La centralidad de grado es una medida radial de volumen que se calcula como el número de aristas incidentes en el vértice. Esta medida da una idea de la conectividad de un vértice. La siguiente figura muestra la escala de centralidad de grado de los vértices de un grafo, en una escala en la que mayor oscuridad significa mayor centralidad.  [2]

Figura 4.1.7, [2]. Aplicación de teoría de grafos a redes con elementos autónomos. 

• Centralidad de cercanía

La centralidad de cercanía es una métrica radial de longitud calculada como la inversa del valor medio de las distancias mínimas desde ese vértice al resto de vértices del grafo. Por tanto, cuanto mayor sea la distancia media menor será la centralidad del vértice y viceversa [2]. Las medidas de centralidad de cercanía intentan capturar la noción de que un vértice es central 'si está cerca' de muchos otros vértices.

El enfoque estándar, introducido por Sabidussi , es dejar que la centralidad varíe inversamente con una medida del total de la distancia de un vértice a todos los demás,

$$C_{Cl}(V)= \frac{1}{\sum_{u\in V} dist(v,u)},$$

Donde $dist (v,u)$ es la distancia geodésica (camino más corto) entre los vértices ${u,v\in V}$. Esta media esta entre el intervalo $[0,1]$, mediante la multiplicación por un factor $N_{v-1}$.

• Centralidad de intermediación

La centralidad de intermediación es una medida de centralidad medial que viene dada por la fracción de caminos más cortos entre vértices del grafo que atraviesan el vértice en cuestión [2]. En otras palabras, las medidas de centralidad de intermediación tienen como objetivo resumir hasta qué punto un vértice se encuentra "entre" otros pares de vértices. Estas centralidades se basan en la perspectiva de que la 'importancia' se relaciona con la ubicación de un vértice con respecto a las rutas en el grafo, puesto que es probable que haya rutas más críticas para el proceso de comunicación. 

La centralidad de intermediación, introducida por Freeman , se define como: 
$$C_{B}(V)= \sum_{s\neq t\neq v \in V}\frac{\sigma (s,t\mid v)}{\sigma (s,t)},$$
Donde $\sigma (s,t\mid v)$ es el número total de caminos más cortos entre $s$ y $t$ que pasan a través de $v$ , y $\sigma (s,t)$ es el número total de caminos más cortos entre $s$ y $t$ (independiente de si pasan o no por $v$). En el caso de que los caminos más cortos sean únicos, $C_{B}(V)$ solo cuenta el número de caminos más cortos que pasan por $v$ . Esta medida de centralidad puede estar restringida al intervalo unitario mediante la división por un factor de $( N_{v - 1}) ( N_{v - 2}) / 2$.

Finalmente, otras medidas de centralidad se basan en nociones de "estatus" o "prestigio" o "rango". Es decir, buscan capturar la idea de que cuanto más centrales son los vecinos de un vértice, más central es ese vértice en sí. Estas medidas están implícitas de forma inherente en su definición y, por lo general, pueden expresarse en términos de soluciones de vectores propios de sistemas lineales de ecuaciones adecuadamente definidos.

• Centralidad de vector propio

Otra medida de centralidad radial de volumen es la centralidad de vector propio. Esta métrica mide la influencia de un vértice en el grafo de modo que esta centralidad será elevada si un vértice está conectado a muchos vértices, los cuales están a su vez conectados a muchos vértices. [2]

Hay muchas medidas de centralidad del vector propio . Por ejemplo, Bonacich , siguiendo el trabajo de Katz y otros, definieron una medida de centralidad de la forma:
$$C_{Ei}(v)= \alpha \sum_{ \lbrace u,v  \rbrace\in E } {C_{Ei}(u)}.$$
El vector $C_{Ei}={(C_{Ei}(1), . . . ,C_{Ei}(N_v))}^T$ es la solución del problema de valor propio $A_{C_{Ei}}={\alpha}^{-1}$, donde $A$ es la matriz de adyacencia para el grafo $G$, Bonacich argumenta que una elección óptima de ${\alpha}^{-1}$ es el valor propio más grande de $A$ , y por tanto $C_{Ei}$es el vector propio correspondiente.
Cuando $G$ no es dirigido y conexo, el valor propio más grande de $A$ será simple (multiplicidad algebraica 1) y el vector propio correspondiente tendrá  todas sus entradas distintas de cero y compartiendo el mismo signo. Las entradas automáticamente estarán entre 0 y 1 por la ortonormalidad (conjunto ortogonal y la norma de cada uno de sus vectores es igual a 1) de vectores propios. 

Una forma intuitivamente atractiva de mostrar centralidades de vértices (para grafos de tamaño pequeño a moderado) es utilizar un diseño radial, con más vértices centrales ubicados más cerca del centro. La función gplot.target , en el paquete sna , se puede utilizar para este propósito. Por ejemplo,

1 > A <- get.adjacency(karate, sparse=FALSE)
2 > library(network)
3 > g <- network::as.network.matrix(A)
4 > library(sna)
5 > sna::gplot.target(g, degree(g), main="Degree",
6 + circ.lab = FALSE, circ.col="skyblue",
7 + usearrows = FALSE,
8 + vertex.col=c("blue", rep("red", 32), "yellow"),
9 + edge.col="darkgray")

produce una visualización de la centralidad de grado para el grafo del club de karate, como se muestra en la Figura 4.1.8

Figura 4.1.8

La visualización de las otras tres centralidades se producen de manera similar, reemplazando el argumento degree(g), por los argumentos closeness(g), betweenness(g), y evcent(g)$vector,respectivamente. 

Las extensiones de estas medidas de centralidad de grafos no dirigidos a grafos dirigidos son sencillas. Sin embargo, en este último caso, existen además otras útiles opciones. Por ejemplo, el algoritmo HITS, basado en el concepto de 'hubs y autoridades', como lo presentó Kleinberg, en el contexto de la World Wide Web, un buen centro representa una página que apunta a muchas otras páginas, mientras que una buena autoridad representa una página que está vinculada por muchos centros diferentes, en otras palabras los denominados vértices hubs se caracterizan por la cantidad de vértices de autoridad a los que apuntan y los llamados vértices de autoridad por la cantidad de ejes que apuntan a ellos.

Específicamente, dada una matriz de adyacencia $A$ para un grafo dirigido, los hubs son determinados de acuerdo con la centralidad del vector propio de la matriz $M_{hub}=A{A}^T$ , y autoridades, de acuerdo con la de $M_{auth}={A}^TA$.

La aplicación de estas medidas a una red de blogs sobre el SIDA indica, que solo 6 de los 146 blogs de esta red desempeñan el papel de hub, mientras que la vasta mayoría de los vértices (incluidos algunos de los hubs) desempeñan el papel de una autoridad.

4.2.3 Caracterización de aristas 

Si nos preguntamos por qué los lazos en una red social son los más importantes para la difusión de, digamos, información o rumores. Podemos comprender que el concepto de centralidad de arista se relaciona con la centralidad del vértice, por ejemplo, la centralidad de intermediación de aristas, se extiende sobre la centralidad de intermediación de vértices de una manera sencilla, asignando a cada arista un valor que refleja el número de caminos más cortos que atraviesan dicha arista.

4.3 Caracterización de la cohesión en una red 

Hay muchas formas en que podemos definir la cohesión de una red, dependiendo del contexto de la pregunta que se hace. Las definiciones difieren, por ejemplo, en escala, de rango local (por ejemplo, tríadas) a global (por ejemplo, componentes gigantes), y también en la medida en que se especifican explícitamente (p. ej., cliques (camarillas)) versus implícitamente (p. ej., 'grupos' o 'comunidades'). En esta sección discutimos una serie de formas comunes de definir y resumir la "cohesión" en una red.

4.3.1 Subgrafos y censos 

Un enfoque para definir la cohesión de una red es mediante la especificación de un cierto subgrafo de interés. El ejemplo canónico de tal subgrafo es el de una camarilla. Recuerde que las camarillas son subgrafos completos y, por tanto, son subconjuntos de vértices que son totalmente cohesivo, en el sentido de que todos los vértices dentro del subconjunto están conectados por aristas. Un censo de camarillas nos permite tener una idea de cómo está estructurado el grafo como en este caso el grafo del club de karate: 

1 > table(sapply(cliques(karate), length))

2

3       1    2   3   4   5

4      34   78  45  11   2

Para el grafo del club de karate, un censo de este tipo refleja que hay 34 nodos (camarillas de tamaño uno) y 78 aristas (camarillas de tamaño dos), seguidos de 45 triángulos (camarillas de tamaño tres), etc. Pero hay cierta redundancia en este análisis, ya que las camarillas de más tamaño incluyen necesariamente camarillas de tamaños más pequeños. Una camarilla máxima es una camarilla que no es un subconjunto de una camarilla más grande. Por ejemplo, en el grafo del club de karate hay dos camarillas máximas.

1 > table(sapply(maximal.cliques(karate), length))

2

3    2   3  4  5
4   11  21  2  2

En la práctica las camarillas máximas son relativamente raras. Para conocer el tamaño de la camarilla máxima (formalmente llamada, numero de camarilla), usamos la siguiente instrucción:

1 > clique.number(karate)
2 [1] 5

Además, es popular para la visualización, usar la noción de núcleos, ya que proporciona una forma de descomponer una red en capas (como una cebolla), esto se pueden combinar de una manera particularmente efectiva con un diseño radial, por ejemplo, en el caso del grafo del club de karate:

1 > cores <- graph.coreness(karate)

2 > sna::gplot.target(g, cores, circ.lab = FALSE,

3 + circ.col="skyblue", usearrows = FALSE,

4 + vertex.col=cores, edge.col="darkgray")
5 > detach("package:network") 
6 > detach("package:sna")

Figura 4.2.2, Representación visual de la descomposición de k-core del grafo del club de karate,  los vértices del núcleo uno están representados en color negro, dos (rojo),tres (verde) y cuatro (azul), se muestran distancias sucesivamente más pequeñas desde el centro, con las mismas distancias para los vértices dentro de cada núcleo.

Más allá de las camarillas y sus variantes, existen otras clases de subgrafos de interés general en definir la cohesión de una red. Dos cantidades fundamentales (análisis de redes sociales), que son las díadas y tríadas.

Las diadas son pares de vértices que, en grafos dirigidos, puede tomar tres estados posibles: nulo (sin aristas dirigidas), asimétrico (una arista dirigida) o mutuo (dos aristas dirigidas). En cambio, las tríadas pueden tomar 16 estados posibles, como lo podemos observar en el siguiente gráfico: 

Figura 4.2.3

Un censo de los posibles estados de estas dos clases de subgrafos, es decir, contando cuántas veces se observa cada estado en un grafo $G$ , puede dar una idea de la naturaleza de la conectividad en un grafo. Por ejemplo, en la red de blogs sobre el SIDA (Figura 4.1.9), vemos que la gran mayoría de diadas son nulas, mientras de las que no son nulas, casi todas son asimétricas, lo que indica la clara unilateralidad con la que los blogs en la red se hacen referencia entre sí.

1 > aidsblog <- simplify(aidsblog)

2 > dyad.census(aidsblog)

3    mut

4     [1]     3

5

6    asym

7     [1]     177

8

9     null
10    [1]    10405

Como podemos observar este análisis es consistente con las observaciones del análisis anterior de hubs y autoridades en esta red. 

Podemos efectuar un censo de cualquier subgrafo de internes. Los pequeños subgrafos de interés conexos se denominan comúnmente motivos, ejemplos de estos motivos, son subgrafos con una estructura en forma de abanico (varias aristas dirigidas que emanan de un solo vértice) y bucles de avance (es decir, tres aristas rectas, entre tres vértices, de la forma $\lbrace u, v \rbrace$, $\lbrace v, w \rbrace$ y $\lbrace u, w \rbrace$ ). En una red enumerar estas apariciones puede llevar bastante tiempo. Por lo que se utiliza métodos de muestreo, con recuentos de motivos estimados, usando la función graph.motifs.

4.3.2 Densidad y nociones relacionadas de frecuencia relativa

La densidad de un grafo es la relación entre el número de aristas del grafo y el número de aristas máximo, el cual es el número de aristas de un grafo completo con el mismo número de vértices. Por ejemplo, en un grafo $G$ (no dirigido) sin bucles automáticos y sin múltiples aristas, la densidad de un subgrafo $H = ( V_H , V_H )$ es

$$den(H)= \frac{\vert E_H \vert}{\vert V_H \vert (\vert V_H \vert - 1)/2},$$

El valor de $den(H)$ estará entre cero y uno (la densidad máxima es 1 (para un grafo completo) y la densidad mínima es de 0 ), proporcionando una medida de que tan cerca está $H$ de ser una camarilla. En el caso de que $G$ sea un dígrafo, el denominador se sustituye por ${\vert V_H \vert (\vert V_H \vert - 1)}$. 

El concepto posiblemente simple de densidad se vuelve interesante a través de la libertad que tenemos en la elección del subgrafo $H$. Por ejemplo, tomando $H = G$ se obtiene la densidad del grafo general G . Por el contrario, tomando $H = H_V$ como el conjunto de vecinos de un vértice $v \in V$ , y las aristas entre ellos, da una medida de densidad en la vecindad inmediata de $v$.

Aplicando estas ideas al grafo del club de Karate, por ejemplo, vemos que, en los subgrafos correspondientes a cada uno de los instructores y administradores, en unión con sus respectivos vecindarios inmediatos, es decir, las redes egocéntricas alrededor vértices 1 y 34: son notablemente más densos que la red general.

1 > ego.instr <- induced.subgraph(karate,
2 + neighborhood(karate, 1, 1)[[1]])
3 > ego.admin <- induced.subgraph(karate,
4 + neighborhood(karate, 1, 34)[[1]])
5 > graph.density(karate)
6 [1] 0.1390374
7 > graph.density(ego.instr)
8 [1] 0.25
9 > graph.density(ego.admin)

10 [1] 0.209150

Lo cual es consistente con el grafo: 

Figura 4.2.4

La frecuencia relativa también se utiliza para definir las nociones de "agrupación" en un grafo. Por ejemplo, el uso estándar del término coeficiente de agrupamiento típicamente se refiere a la cantidad

$$cl_{T}(G)= \frac{3\tau_\bigtriangleup (G)}{\tau_3 (G)},$$

donde $\tau_\bigtriangleup(G)$ es el número de triángulos en el grafo $G$ , y $\tau_3(G)$, es el número de triples conectados (es decir, un subgrafo de tres vértices conectados por dos aristas, también a veces llamado 2-star). El valor $cl_T(G)$ es llamado transitividad del grafo, y es una cantidad estándar de interés en la literatura de redes sociales ,donde también se conoce como la "fracción de triples transitivos". Hay que tener en cuenta que $cl_T(G)$ es una medida de agrupamiento global, que resume la frecuencia relativa con la que los triples conectados se acercan para formar triángulos. Por ejemplo, en el grafo del club de karate vemos que sólo alrededor de una cuarta parte de los triples conectados se cierran de esta manera.

1 > transitivity(karate)

2 [1] 0.2556818

Respecto a los dígrafos, un concepto exclusivo es el de la reciprocidad, es decir, el grado de reciprocidad entre lazos en una red dirigida, en otras palabras, la reciprocidad es una medida de la probabilidad de que los vértices de una red dirigida se vinculen mutuamente entre sí . Una forma tradicional de definir la reciprocidad $r$ es usando la proporción de número de enlaces que apuntan en ambas direcciones ${L}^{<->}$ en el número total de enlaces L.[3]

$$r = \frac{L^{<->}}{L}$$

Con esta definición, $r = 1$ hace referencia a una red puramente bidireccional, mientras que $r = 0$ para una puramente unidireccional. En general las redes reales tienen un valor intermedio entre 0 y 1.

Sin embargo, esta definición de reciprocidad tiene algunos defectos. No puede distinguir la diferencia relativa de reciprocidad en comparación con una red puramente aleatoria con el mismo número de vértices y aristas. La información útil de la reciprocidad no es el valor en sí mismo, sino si los vínculos mutuos ocurren más o menos a menudo de lo que se espera por azar. Además, en las redes que contienen auto-bucles (enlaces que empiezan y terminan en el mismo vértice), estos deben excluirse al calcular L.

Hay dos principales enfoques, distinguidos por si la unidad de interés en el cálculo de frecuencias relativas es el de díadas o aristas dirigidas. En el caso que las díadas se utilicen como unidades, la reciprocidad se define como el número de díadas con aristas directas recíprocas (es decir, mutuas) dividido por el número de díadas con una sola arista no correspondida. Alternativamente, la reciprocidad se define como el número total de aristas recíprocas dividido por el número total de aristas. En la red de blogs sobre el SIDA, la reciprocidad es bastante baja, como se nota a continuación :

1 > reciprocity(aidsblog, mode="default")

2 [1] 0.03278689

3 > reciprocity(aidsblog, mode="ratio")

4 [1] 0.01666667

Recordando nuestro censo de díadas de la misma red, este resultado no es sorprendente, debido a que teníamos 177 diadas asimétricas (unilaterales) y apenas 3 diadas mutuas.

1 > aidsblog <- simplify(aidsblog)

2 > dyad.census(aidsblog)

3    mut

4     [1]     3

5

6    asym

7     [1]     177

4.3.3 Conectividad, cortes y flujos 

Se dice que un grafo $G$ es conexo si cada vértice es accesible entre sí, y que una componente de un grafo es un subgrafo conectado al máximo, es decir que, el subgrafo en si es conexo, pero no es conexo con otros subgrafos . 

Nota: Un grafo no dirigido es conexo si existe un camino entre cada par de vértices y un grafo dirigido se denomina fuertemente conexo si existe un camino desde cualquier vértice a cualquier otro vértice, además un grafo no conexo $G$ se puede partir de una sola forma en un conjunto de subgrafos conexos y cada uno de ellos es una componente conexa de $G$.

A menudo en el caso de que una de las componentes conexas en un grafo $G$ domina a otras en magnitud y contiene la gran mayoría de los vértices en $G$ . Tal se llama componente gigante, es decir, un grupo de vértices enlazados entre sí, y que agrupan a la mayoría de los vértices de la red.

Nota: el efecto percolación se produce cuando se llega un punto en el que los diferentes componentes aislados se unen.

Recordando, el ejemplo de la red de interacciones de proteínas en levadura, sabemos que la red de 2617 vértices no es conexa.

1 > is.connected(yeast)

2 [1] FALSE

Sin embargo, un censo de todas las componentes conexas dentro del grafo muestra claramente que existe una componente gigante

1 > comps <- decompose.graph(yeast)

2 > table(sapply(comps, vcount))

3

4      2  3 4 5 6 7 2375

5     63 13 5 6 1 3    1

Como apreciamos este componente tiene $2375/2617≈90\%$ de los vértices de la red. Por el contrario, ninguno de los otros componentes por si solo tiene siquiera el $1\%$. En la práctica, a menudo la atención se limitaría a este componente gigante para llevar a cabo más análisis de modelado. 

Por ejemplo, una característica célebre observada en el componente gigante de muchas redes del mundo real es la llamada propiedad del mundo pequeño , que se refiere a la situación en la que (a) la distancia de ruta más corta entre pares de vértices es generalmente bastante pequeña, (b) la agrupación es relativamente alta. En nuestra red de interacciones proteicas en levadura, vemos que la longitud media del camino en la componente gigante es apenas mayor de cinco.

1 > yeast.gc <- decompose.graph(yeast)[[1]]

2 > average.path.length(yeast.gc)

3 [1] 5.09597

Incluso el camino más largo no es muy extenso. 

1 > diameter(yeast.gc)

2 [1] 15

Por lo tanto, la distancia de la ruta más corta en esta red se considera “Pequeña”, al mismo tiempo, la agrupación en esta red es relativamente grande.

1 > transitivity(yeast.gc)

[1] 0.4686663

Lo que indica que cerca del $50\%$ de los triples conectados se cierran para formar triángulos. 

Nota: La instrucción transitivity mide la probabilidad de que los vértices adyacentes de un vértice estén conectados. A veces, esto también se denomina coeficiente de agrupamiento.

Una noción de conectividad algo más refinada que la de los componentes se deriva preguntando si, un subconjunto arbitrario de k vértices (aristas) se elimina de un grafo, el subgrafo restante está conectado. Los conceptos de conectividad de vértice, arista ,y los conceptos relacionados de cortes de vértice y arista, ayudan a precisar tales nociones. 

Un grafo $G$ se llama k-vértice-conectado si (i) el número de vértices $N_v>k$ , y (ii) la eliminación de cualquier subconjunto de vértices $X ⊂ V$ de cardinalidad $\vert X \vert < k$ deja un subgrafo que está conectado. De manera similar, $G$ se llama k-arista-conectada si (i) $N_v ≥ 2$, y (ii) la eliminación de cualquier subconjunto de aristas $Y ⊆ E$ de cardinalidad $\vert Y \vert < k$ deja un subgrafo que está conectado.

En el caso de la componente gigante de la red de proteínas en levadura, la conectividad respecto al vértice y arista es igual a uno

1 > vertex.connectivity(yeast.gc)

2 [1] 1

3 > edge.connectivity(yeast.gc)

4 [1] 1

Por lo tanto, se requiere la eliminación de un solo vértice o arista bien elegida para dividir este subgrafo en componentes adicionales . Si la eliminación de un conjunto particular de vértices o arista en un grafo desconecta el grafo, ese conjunto se denomina corte de vértice . Un solo vértice que se desconecta se llama vértice de corte o, a veces, punto de articulación. La identificación de tales vértices puede proporcionar una idea de dónde una red es vulnerable (por ejemplo, en el sentido de un ataque, donde desconectarse produce consecuencias no deseadas, como un corte de energía en una red de energía eléctrica).

En la componente gigante de la red proteínas en levadura, casi el $15\%$ de los vértices son vértices de corte.

1 > yeast.cut.vertices <- articulation.points(yeast.gc)

2 > length(yeast.cut.vertices)

3 [1] 350

Un resultado fundamental en la teoría de grafos, conocido como teorema de Menger, esencialmente nos dice, sean $u,v \in V_G$ (con $V_G$ conjunto de vértices de un grafo), la cantidad de vértices en $uv$ - corte mínimo es igual a la máxima cantidad de $uv$ – caminos internamente ajenos.

Nota: Para profundizar en el enunciado y demostración del teorema de Menger así como en los conceptos de corte mínimo y caminos internamente ajenos visite el siguiente enlace: https://www.youtube.com/watch?v=39R7nDI9KcU&t=292s

Por lo tanto, el teorema de Menger relaciona la robustez de un grafo ante la eliminación de sus vértices (aristas) con la máxima cantidad de distintos caminos que lo recorren. Por lo tanto, un grafo con conectividad de vértices (aristas) puede tener rutas y, en consecuencia, contener información fluyendo sobre esos caminos, lo cual puede ser interrumpido por la eliminación apropiada de un pequeño número de vértices (aristas). Funciones como shortest.paths, graph.maxflow, y graph.mincut se pueden usar en igraph para calcular cantidades relevantes para esta conexión entre cortes y flujos.

4.4 Particionamiento de grafos

La partición, en términos generales, se refiere a la segmentación de un conjunto de elementos en subconjuntos 'naturales'. Más formalmente, una partición $\mathscr{C} = \lbrace C_1,...,C_k \rbrace$ de un conjunto finito $S$ es una descomposición de $S$ en $K$ subconjuntos no vacíos, disjuntos $C_k$ tal que $U_{k=1}^{K} C_k=S.$

La partición es una herramienta útil para encontrar, subconjuntos de vértices que demuestran una 'cohesión' con respeto a los patrones relacionales subyacentes. 

Un subconjunto 'cohesivo' de vértices generalmente se toma para referirse a un subconjunto de vértices que (i) están bien conectados entre sí, y al mismo tiempo (ii) están relativamente bien separado de los vértices restantes.

Es decir, el objetivo del particionamiento de grafos es que, dado un grafo de $v$ vértices completamente conexos y sus aristas con un peso determinado. El objetivo es dividir un grafo en $K$ subgrafos. Todos estos subgrafos deben tener incorporados a lo menos 2 vértices y a lo más el doble de los vértices que habría de existir en cada subgrafo si se divide el grafo total en $K$ subgrafos de igual cantidad de vértices. La principal idea y final es que estos subgrafos al quedar conectados entre sí por aristas tengan el menor grado de cohesión posible, es decir, que las aristas que unen los subgrafos pesen lo menos posible y de esa manera poder evitar una cierta “dependencia trascendental” entre ellos. 

4.4.1 Agrupación jerárquica 

Una gran cantidad de métodos para la partición de grafos son esencialmente variaciones de los conceptos más generales de agrupamiento jerárquico utilizado en el análisis de datos.

Hay numerosas técnicas que se han propuesto para el problema general de agrupamiento, centrándose principalmente en (i) cómo evalúan la calidad de las agrupaciones propuestas y(ii) los algoritmos mediante los cuales buscan optimizar esa calidad.

Podemos observar dos tipos de técnicas de agrupamiento jerárquico:

• Técnicas aglomerativas: comenzar con cada caso como un cluster individual. En cada paso, combinar el par de clusters más cercano hasta que sólo quede uno o k. [4]
• Técnicas divisivas: comenzar con un único cluster que englobe todos los casos de nuestro conjunto de datos. En cada paso, partir un cluster hasta que cada cluster contenga un único caso (o queden k clusters). [4]

En cada etapa, la partición candidata se modifica de una manera que minimiza una medida especificada de costo. En los métodos aglomerativos, la combinación menos costosa de dos elementos de partición previamente existentes se ejecuta, mientras que, en los métodos divisivos, se ejecuta la división menos costosa de un solo elemento de partición existente en dos. La medida de costo incorporada en un método de agrupamiento jerárquico utilizado en la partición de grafos debe reflejar nuestro sentido de lo que define un subconjunto 'cohesivo' de vértices. Se han propuesto muchas medidas de costos. Una popular medida es la de modularidad.

La modularidad es una medida de la estructura de las redes o grafos. Fue diseñado para medir la fuerza de la división de una red en módulos (también llamados grupos, agrupamientos o comunidades). Las redes con alta modularidad tienen conexiones sólidas entre los vértices dentro de los módulos, pero escasas conexiones entre vértices en diferentes módulos. La modularidad se utiliza a menudo en los métodos de optimización para la detección de la estructura comunitaria de las redes. Sin embargo, se ha demostrado que la modularidad sufre un límite de resolución y, por lo tanto, no es capaz de detectar pequeñas comunidades. Las redes biológicas, incluidos los cerebros animales, presentan un alto grado de modularidad.

Un enfoque rápido y ávido de optimización en forma de un algoritmo de agrupamiento jerárquico aglomerativo, es implementado en igraph como fastgreedy.community. Aplicando este método al grafo del club de karate:

1 > kc <- fastgreedy.community(karate)

Observamos que tenemos 3 comunidades

1 > length(kc) 

2 [1] 3 

Y sus tamaños respectivos

3 > sizes(kc)

4 Community sizes

5     1    2    3

6    18   11    5

Basado en lo que sabemos de esta red y examinando la membresía de la comunidad

 

1 > membership(kc)

2       Mr Hi Actor 2 Actor 3  Actor 4  Actor 5  Actor 6

3           2       2       2        2        3        3

4     Actor 7 Actor 8 Actor 9 Actor 10 Actor 11 Actor 12

5           3       2       1        1        3        2

6  Actor 13 Actor 14 Actor 15 Actor 16 Actor 17 Actor 18

7         2        2        1        1        3        2

8  Actor 19 Actor 20 Actor 21 Actor 22 Actor 23 Actor 24

9         1        2        1        2        1        1

10 Actor 25 Actor 26 Actor 27 Actor 28 Actor 29 Actor 30

11        1        1        1        1        1        1

12 Actor 31 Actor 32 Actor 33   John A

13        1        1        1        1

La representación visual obtenida al trazar la red es

1 > plot(kc, karate)

Figura 4.2.5

Donde, la comunidad más grande es de 18 miembros y está centrada alrededor del administrador (es decir, John A, ID de vértice 34). La segunda comunidad más grande es de 11 miembros y se centra en el instructor principal (es decir, el Sr.Hi, ID de vértice 1).

La jerarquía resultante normalmente se representa en forma de un árbol, llamado dendrograma (organiza los datos en subcategorías que se van dividiendo en otros hasta llegar al nivel de detalle deseado asemejándose a las ramas de un árbol que se van dividiendo en otras sucesivamente). Este tipo de representación permite apreciar claramente las relaciones de agrupación entre los datos e incluso entre grupos de ellos, aunque no las relaciones de similitud o cercanía entre categorías. Observando las sucesivas subdivisiones podemos hacernos una idea sobre los criterios de agrupación de los mismos, la distancia entre los datos según las relaciones establecidas, etc. Como podemos ver a continuación:

 1 > install.packages("ape")

 2 > library(ape)

 3 > dendPlot(kc, mode="phylo")

Figura 4.2.6

4.4.2 Particionamiento espectral

Un enfoque popular de ese particionamiento está basado en el análisis de le llamado laplaciano de un grafo. El grafo laplaciano de un grafo $G$ , con matriz de adyacencia $A$ , es una matriz $L =D - A$ , donde $D = diag [( d_v )]$ es una matriz diagonal con elementos $D_{vv}= d_v$ (cuenta el número de aristas en $E$ que inciden sobre $v$)que son las entradas de la secuencia de grado de $G$ . Un resultado formal en la teoría de grafos espectrales establece que un grafo $G$ constará de $K$ componentes conectados si y solo si $\lambda_1(L)=...=\lambda_k(L)=0$ y  $\lambda_{K+1}(L)>0$, donde $\lambda_1\leq...\leq\lambda_{N_v}$ son los valores propios (no necesariamente distintos) de $L$ , ordenados de pequeño a grande. Por lo tanto, el número de componentes en un grafo está directamente relacionado con el número de valores propios distintos de cero del grafo laplaciano.

Se puede demostrar que el valor propio más pequeño de $L$ es idénticamente igual a cero, con el vector propio correspondiente $x_1={(1,...,1)}^T$ . Por lo tanto, por ejemplo, si sospechamos que un grafo $G$ consta de "casi" $K = 2$ componentes y, por lo tanto, es un buen candidato para la bisección (división de un elemento en dos partes iguales), podríamos esperar que $\lambda_2(L)$ esté cerca de cero. De hecho, tales expectativas son razonables, ya que el valor $\lambda_2$ está estrechamente relacionado con una serie de medidas de conectividad y estructura del grafo. En particular, estas relaciones indican que cuanto menor es $\lambda_2$, más fácil es que el grafo se separe en dos subgrafos cortando un número relativamente pequeño de aristas entre los dos. Fiedler fue el primero en asociar $\lambda_2$ con la conectividad de un grafo, sugirió dividir los vértices separándolos según el signo de sus entradas en el vector propio correspondiente $x_2$ . El resultado es producir dos subconjuntos de vértices (un supuesto corte).

$S=\lbrace v \in V : x_2(v) \geq 0 \rbrace$  y  $\lbrace \overline{S} = v \in V : x_2(v) < 0\rbrace$

Por lo tanto, el vector $x_2$ a menudo se denomina vector de Fiedler, y el valor propio correspondiente $\lambda_2$, valor de Fiedler. Ilustramos el uso en el grafo del club de karate nuevamente. Es sencillo realizar el análisis-propio necesario. 

1 > k.lap <- graph.laplacian(karate)

2 > eig.anal <- eigen(k.lap)

Trazamos los valores propios del grafo laplaciano.

1 > plot(eig.anal$values, col="blue",

2 + ylab="Valores propios del grafo laplaciano")

Figura 4.2.7, Autovalores del grafo laplaciano L para el grafo del club de kárate.

Notamos que (a)  solo hay un valor propio exactamente igual a cero (como se esperaba, ya que esta red es conexa) y (b) el segundo valor propio más pequeño $\lambda_2$ está bastante cerca de cero. 

Extrayendo el vector de Fiedler

1 > f.vec <- eig.anal$vectors[, 33]

Y graficando las entradas de ese vector frente al número de actor

1 > faction <- get.vertex.attribute(karate, "Faction")

2 > f.colors <- as.character(length(faction))

3 > f.colors[faction == 1] <- "red"

4 > f.colors[faction == 2] <- "cyan"

5 > plot(f.vec, pch=16, xlab="Número de Actor",

6 + ylab="Entradas del vector de Fiedler", col=f.colors)

7 > abline(0, 0, lwd=2, col="lightgray")

Figura 4.2.8

En la figura observamos el vector Fiedler y su partición correspondiente (indicada por la línea horizontal gris). Las dos facciones del club de karate (lideradas por el instructor y el administrador, respectivamente) están indicadas en rojo y cian.

En general, por supuesto, podemos esperar que una red se divida en más de dos subgrafos. El método de partición espectral que se acaba de describir se puede aplicar iterativamente, primero dividiendo un grafo en dos subgrafos, luego cada uno de esos dos subgrafos en subgrafos adicionales, y así sucesivamente. Idealmente, sin embargo, es deseable que tales iteraciones estén destinadas a optimizar alguna función objetivo común. 

4.4.3 Validación del particionamiento de grafos

Al igual que en el problema general de la agrupación de datos, la cuestión de la validación es importante para la partición de grafos, pero a menudo no es trivial.

Por ejemplo, las proteínas que se encuentran agrupadas en un grafo de proteínas entre las acciones a menudo participan en procesos biológicos similares; de manera similar, los actores agrupados en una red social pueden compartir ciertos intereses. La partición de grafos puede verse como una herramienta para descubrir dichos subconjuntos en la ausencia de conocimiento de estas características. Cuando tengamos conocimiento de alguna noción definida externamente de pertenencia a una clase, puede ser interesante comparar y contrastar las asignaciones resultantes con las que se derivan de la partición de grafos.

4.5 Assortividad y mezcla 

El enlace selectivo entre vértices, según una determinada característica (s), se denomina mezcla selectiva en la literatura de las redes sociales. Medidas que cuantifican la mezcla selectiva en una red dada se ha denominado assortatividad de coeficientes , y son esencialmente variaciones del concepto de coeficientes de correlación (medida de dependencia lineal entre dos variables aleatorias cuantitativas).

El coeficiente de assortividad en esta configuración se define como:

$$r_a=\frac{\sum_i f_{ij}-\sum_i f_{i+} f_{i+1}}{1- \sum_i f_{i+}  f_{i+1}}$$

donde $f_{ij}$ es la fracción de aristas en $G$ que unen un vértice en la i-ésima categoría con un vértice en la j-ésima categoría, $f_{i+}$ y $f_{i+1}$ denotan la i-ésima suma marginal de filas y columnas, respectivamente, de la matriz resultante $f$. El valor $r_a$ se encuentra entre -1 y 1. Es igual a cero cuando la mezcla en el grafo no es diferente de la obtenida a través de una asignación aleatoria de aristas que conserva la distribución de grados marginales (distribución de probabilidad de un subconjunto de variables aleatorias de un conjunto de variables aleatorias). Del mismo modo, es igual a uno cuando hay una mezcla perfecta (es decir, cuando las aristas solo conectan vértices de la misma categoría). Sin embargo, en el caso de que la mezcla sea perfectamente desasortativa (describe un grafo en el que los vértices de grado bajo son más propensos a conectarse con vértices de grado alto.) en el sentido de que cada arista del grafo conecta vértices de dos categorías diferentes, el coeficiente en $r_a$ no necesariamente toma el valor -1. 

Considerando nuevamente la red de interacciones proteína-proteína en la levadura. El hecho de que se sepa que la unión física de proteínas es directamente relevante para las clases funcionales sugiere que con frecuencia habrá una fuerte mezcla selectiva en redes de interacción proteína-proteína con respectivas a estas clases como atributos. Por ejemplo, para la clase "P", que representa proteínas que se sabe que desempeñan un papel en la síntesis de proteínas, vemos un coeficiente de assortividad de casi 0,5.

1 > assortativity.nominal(yeast, (V(yeast)$Class=="P")+1,

2 + directed=FALSE) 

3 [1] 0.4965229 

Cuando la característica del vértice de interés es continua, en lugar de discreta, denote por $(x_e, y_e)$ los valores de esa característica para los vértices unidos por una arista $e \in E$. Entonces, un candidato natural para cuantificar la assortatividad en esta característica es el coeficiente de correlación de Pearson de los pares  $(x_e, y_e)$ ,

$$r = \frac{\sum_{x,y} xy (f_{xy} - f_{x+}  f_{+y})}{\sigma_x \sigma_y}.$$

Aquí la suma es sobre todos los pares únicos observados $(x, y)$, con $f_{xy}$, $f_{x+}$ y $f_{+y}$ definidos en analogía con el caso categórico, $\sigma_x$ y $\sigma_y$ son las desviaciones estándar correspondientes a la distribución de frecuencias {$f_{x+}$} y {$f_{+y}$}, respectivamente. Un uso común del coeficiente de assortividad $r$ es resumir la correlación grado-grado de vértices adyacentes, al estudiar la estructura de la red. Para la red de proteínas en levadura, encontramos que el grado de correlación es positivo y relativamente grande.

 1 > assortativity.degree(yeast) 

 2 [1] 0.4610798

Esta observación es coherente con el análisis de la Figura 4.1.6. Donde si bien existe una tendencia a vértices de grados más altos para enlazar con vértices similares, los vértices de grado más bajo tienden a enlazarse con vértices de grados inferiores y superiores. 

Bibliografía

[1] Kolaczyk, E. D., & Csárdi, G. (2014). Statistical Analysis of Network Data with R. Boston: Springer.

[2] Bayo, M. V. Aplicación de teoría de grafos a redes con elementos autónomos. Madrid: Universidad de Alcalá-Grado en Ingeniería en Tecnologías de las Telecomunicaciones (Escuela Politécnica Superior). 

[3] M. E. J. Newman, S. Forrest, and J. Balthrop, Phys. Rev. E 66, 035101(R) (2002)

[4] Berzal, F. (s.f.). Clustering jerárquico. Granada: DECSAI-Universidad de Granada.