Coeficiente de agrupamiento

Medida de qué tan conectado y agrupado está un nodo en su gráfico

En teoría de grafos , un coeficiente de agrupamiento es una medida del grado en que los nodos de un grafo tienden a agruparse. La evidencia sugiere que en la mayoría de las redes del mundo real, y en particular en las redes sociales , los nodos tienden a crear grupos muy unidos que se caracterizan por una densidad relativamente alta de vínculos; esta probabilidad tiende a ser mayor que la probabilidad promedio de un vínculo establecido aleatoriamente entre dos nodos (Holland y Leinhardt, 1971; ^[1] Watts y Strogatz, 1998 ^[2] ).

Existen dos versiones de esta medida: la global y la local. La versión global fue diseñada para dar una indicación general de la agrupación en la red, mientras que la local da una indicación del grado de "agrupación" de un solo nodo.

Coeficiente de agrupamiento local

Ejemplo de coeficiente de agrupamiento local en un grafo no dirigido. El coeficiente de agrupamiento local del nodo azul se calcula como la proporción de conexiones entre sus vecinos que se realizan realmente en comparación con el número de todas las conexiones posibles. En la figura, el nodo azul tiene tres vecinos, que pueden tener un máximo de 3 conexiones entre ellos. En la parte superior de la figura se realizan las tres conexiones posibles (segmentos negros gruesos), lo que da un coeficiente de agrupamiento local de 1. En la parte media de la figura solo se realiza una conexión (línea negra gruesa) y faltan 2 conexiones (líneas rojas punteadas), lo que da un coeficiente de agrupamiento local de 1/3. Finalmente, no se realiza ninguna de las conexiones posibles entre los vecinos del nodo azul, lo que produce un valor de coeficiente de agrupamiento local de 0.

El coeficiente de agrupamiento local de un vértice (nodo) en un grafo cuantifica qué tan cerca están sus vecinos de ser una camarilla (grafo completo). Duncan J. Watts y Steven Strogatz introdujeron la medida en 1998 para determinar si un grafo es una red de mundo pequeño .

Un grafo consta formalmente de un conjunto de vértices y un conjunto de aristas entre ellos. Una arista conecta vértice con vértice . ${\displaystyle G=(V,E)}$ ${\displaystyle V}$ ${\displaystyle E}$ ${\displaystyle e_{ij}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{j}}$

La vecindad de un vértice se define como sus vecinos inmediatamente conectados de la siguiente manera: ${\displaystyle N_{i}}$ ${\displaystyle v_{i}}$

${\displaystyle N_{i}=\{v_{j}:e_{ij}\in E\lor e_{ji}\in E\}.}$

Definimos como el número de vértices, , en el entorno, , del vértice . ${\displaystyle k_{i}}$ ${\displaystyle |N_{i}|}$ ${\displaystyle N_{i}}$ ${\displaystyle v_{i}}$

El coeficiente de agrupamiento local para un vértice se da entonces como una proporción del número de vínculos entre los vértices dentro de su vecindad dividido por el número de vínculos que podrían existir entre ellos. Para un grafo dirigido, es distinto de , y por lo tanto para cada vecindad hay vínculos que podrían existir entre los vértices dentro de la vecindad ( es el número de vecinos de un vértice). Por lo tanto, el coeficiente de agrupamiento local para grafos dirigidos se da como ^[2] ${\displaystyle C_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle e_{ij}}$ ${\displaystyle e_{ji}}$ ${\displaystyle N_{i}}$ ${\displaystyle k_{i}(k_{i}-1)}$ ${\displaystyle k_{i}}$

${\displaystyle C_{i}={\frac {|\{e_{jk}:v_{j},v_{k}\in N_{i},e_{jk}\in E\}|}{k_{i}(k_{i}-1)}}.}$

Un grafo no dirigido tiene la propiedad de que y se consideran idénticos. Por lo tanto, si un vértice tiene vecinos, podrían existir aristas entre los vértices dentro del vecindario. Por lo tanto, el coeficiente de agrupamiento local para grafos no dirigidos se puede definir como ${\displaystyle e_{ij}}$ ${\displaystyle e_{ji}}$ ${\displaystyle v_{i}}$ ${\displaystyle k_{i}}$ ${\displaystyle {\frac {k_{i}(k_{i}-1)}{2}}}$

${\displaystyle C_{i}={\frac {2|\{e_{jk}:v_{j},v_{k}\in N_{i},e_{jk}\in E\}|}{k_{i}(k_{i}-1)}}.}$

Sea el número de triángulos en para un grafo no dirigido . Es decir, es el número de subgrafos de con 3 aristas y 3 vértices, uno de los cuales es . Sea el número de triples en . Es decir, es el número de subgrafos (no necesariamente inducidos) con 2 aristas y 3 vértices, uno de los cuales es y tal que es incidente en ambas aristas. Entonces también podemos definir el coeficiente de agrupamiento como ${\displaystyle \lambda _{G}(v)}$ ${\displaystyle v\in V(G)}$ ${\displaystyle G}$ ${\displaystyle \lambda _{G}(v)}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle \tau _{G}(v)}$ ${\displaystyle v\in G}$ ${\displaystyle \tau _{G}(v)}$ ${\displaystyle v}$ ${\displaystyle v}$

${\displaystyle C_{i}={\frac {\lambda _{G}(v)}{\tau _{G}(v)}}.}$

Es sencillo demostrar que las dos definiciones anteriores son las mismas, ya que

${\displaystyle \tau _{G}(v)=C({k_{i}},2)={\frac {1}{2}}k_{i}(k_{i}-1).}$

Estas medidas son 1 si cada vecino conectado a también está conectado a cada otro vértice dentro del vecindario, y 0 si ningún vértice que está conectado a se conecta a ningún otro vértice que esté conectado a . ${\displaystyle v_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle v_{i}}$

Dado que cualquier gráfico está completamente especificado por su matriz de adyacencia A , el coeficiente de agrupamiento local para un gráfico simple no dirigido se puede expresar en términos de A como: ^[3]

${\displaystyle C_{i}={\frac {1}{k_{i}(k_{i}-1)}}\sum _{j,k}A_{ij}A_{jk}A_{ki}}$

dónde:

${\displaystyle k_{i}=\sum _{j}A_{ij}}$

y C _i = 0 cuando k _i es cero o uno. En la expresión anterior, el numerador cuenta el doble del número de triángulos completos en los que está involucrado el vértice i . En el denominador, k _i ² cuenta el número de pares de aristas en los que está involucrado el vértice i más el número de aristas simples atravesadas dos veces. k _i es el número de aristas conectadas al vértice i, y al restar k _i se elimina este último, dejando solo un conjunto de pares de aristas que podrían concebirse para formar triángulos. Por cada par de aristas de este tipo, habrá otro par de aristas que podría formar el mismo triángulo, por lo que el denominador cuenta el doble del número de triángulos concebibles en los que podría estar involucrado el vértice i .

Coeficiente de agrupamiento global

El coeficiente de agrupamiento global se basa en tripletes de nodos. Un triplete son tres nodos que están conectados por dos (triplete abierto) o tres (triplete cerrado) vínculos no dirigidos. Por lo tanto, un grafo triangular incluye tres tripletes cerrados, uno centrado en cada uno de los nodos ( nota: esto significa que los tres tripletes en un triángulo provienen de selecciones superpuestas de nodos). El coeficiente de agrupamiento global es el número de tripletes cerrados (o 3 x triángulos) sobre el número total de tripletes (tanto abiertos como cerrados). El primer intento de medirlo fue realizado por Luce y Perry (1949). ^[4] Esta medida da una indicación del agrupamiento en toda la red (global), y se puede aplicar tanto a redes dirigidas como no dirigidas (a menudo llamada transitividad, consulte Wasserman y Faust, 1994, página 243 ^[5] ).

El coeficiente de agrupamiento global se define como:

${\displaystyle C={\frac {\mbox{number of closed triplets}}{\mbox{number of all triplets (open and closed)}}}}$.

En la literatura también se ha hecho referencia al número de tripletes cerrados como 3 × triángulos, por lo que:

${\displaystyle C={\frac {3\times {\mbox{number of triangles}}}{\mbox{number of all triplets}}}}$.

Opsahl y Panzarasa (2009) propusieron una generalización a redes ponderadas ^[6] y Opsahl (2009) una redefinición a redes de dos modos (tanto binarias como ponderadas) ^{[7] .}

Dado que cualquier gráfico simple está completamente especificado por su matriz de adyacencia A , el coeficiente de agrupamiento global para un gráfico no dirigido se puede expresar en términos de A como:

${\displaystyle C={\frac {\sum _{i,j,k}A_{ij}A_{jk}A_{ki}}{{\frac {1}{2}}\sum _{i}k_{i}(k_{i}-1)}}}$

dónde:

${\displaystyle k_{i}=\sum _{j}A_{ij}}$

y C = 0 cuando el denominador es cero.

Coeficiente de agrupamiento promedio de la red

^{Como alternativa al coeficiente de agrupamiento global, Watts y Strogatz [2]} miden el nivel general de agrupamiento en una red como el promedio de los coeficientes de agrupamiento local de todos los vértices  : ^[8] ${\displaystyle n}$

${\displaystyle {\bar {C}}={\frac {1}{n}}\sum _{i=1}^{n}C_{i}.}$

Vale la pena señalar que esta métrica coloca más peso en los nodos de bajo grado, mientras que el índice de transitividad coloca más peso en los nodos de alto grado.

^{Barrat et al. (2004) [9]} propusieron una generalización a redes ponderadas y Latapy et al. (2008) ^[10] y Opsahl (2009) ^[7] una redefinición a gráficos bipartitos (también llamados redes de dos modos).

^{Fagiolo (2007) [11]} y Clemente y Grassi (2018) ^[12] han proporcionado generalizaciones alternativas a los gráficos ponderados y dirigidos .

Esta fórmula no está definida, por defecto, para gráficos con vértices aislados; véase Kaiser (2008) ^[13] y Barmpoutis et al. ^[14]. Se ha descubierto que las redes con el coeficiente de agrupamiento promedio más grande posible tienen una estructura modular y, al mismo tiempo, tienen la distancia promedio más pequeña posible entre los diferentes nodos. ^[14]

Percolación de redes agrupadas

Para una red aleatoria tipo árbol sin correlación grado-grado, se puede demostrar que dicha red puede tener un componente gigante , y el umbral de percolación (probabilidad de transmisión) está dado por , donde es la función generadora correspondiente a la distribución de grado en exceso . ${\displaystyle p_{c}={\frac {1}{g_{1}'(1)}}}$ ${\displaystyle g_{1}(z)}$

En redes con baja agrupación, el punto crítico se escala de tal manera que: ${\displaystyle 0<C\ll 1}$ ${\displaystyle (1-C)^{-1}}$

${\displaystyle p_{c}={\frac {1}{1-C}}{\frac {1}{g_{1}'(1)}}.}$^[15]

Esto indica que, para una distribución de grados dada, la agrupación conduce a un umbral de percolación mayor, principalmente porque, para un número fijo de enlaces, la estructura de agrupación refuerza el núcleo de la red con el precio de diluir las conexiones globales. Para redes con una alta agrupación, una agrupación fuerte podría inducir la estructura núcleo-periferia, en la que el núcleo y la periferia podrían percolar en diferentes puntos críticos, y el tratamiento aproximado anterior no es aplicable. ^[16]

Para estudiar la robustez de las redes agrupadas se desarrolló un enfoque de percolación. ^{[17] [18]}

Véase también

• Grafo dirigido
• Teoría de grafos
• Teoría de redes
• Ciencia de redes
• Teoría de la percolación
• Red libre de escala
• Mundo pequeño

Referencias

1. PW Holland y S. Leinhardt (1971). "Transitividad en modelos estructurales de grupos pequeños". Estudios comparativos de grupos . 2 (2): 107–124. doi :10.1177/104649647100200201. S2CID  145544488.
2. DJ Watts y Steven Strogatz (junio de 1998). «Dinámica colectiva de redes de «mundo pequeño»». Nature . 393 (6684): 440–442. Bibcode :1998Natur.393..440W. doi :10.1038/30918. PMID  9623998. S2CID  4429113.
3. Wang, Yu; Ghumare, Eshwar; Vandenberghe, Rik; Dupont, Patrick (2017). "Comparación de diferentes generalizaciones del coeficiente de agrupamiento y la eficiencia local para gráficos no dirigidos ponderados". Neural Computation . 29 (2): 313–331. doi : 10.1162/NECO_a_00914 . PMID  27870616. S2CID  11000115. Archivado desde el original el 10 de agosto de 2020 . Consultado el 8 de agosto de 2020 .
4. RD Luce y AD Perry (1949). "Un método de análisis matricial de la estructura de grupo". Psychometrika . 14 (1): 95–116. doi :10.1007/BF02289146. hdl : 10.1007/BF02289146 . PMID  18152948. S2CID  16186758.
5. Stanley Wasserman , Katherine Faust, 1994. Análisis de redes sociales: métodos y aplicaciones. Cambridge: Cambridge University Press.
6. Tore Opsahl y Pietro Panzarasa (2009). "Clustering in Weighted Networks". Redes sociales . 31 (2): 155–163. doi :10.1016/j.socnet.2009.02.002. Archivado desde el original el 1 de julio de 2019 . Consultado el 11 de junio de 2009 .
7. Tore Opsahl (2009). "Clustering in Two-mode Networks". Conferencia y taller sobre análisis social bimodal (30 de septiembre-2 de octubre de 2009) . Archivado desde el original el 21 de marzo de 2016. Consultado el 11 de septiembre de 2009 .
8. Kemper, Andreas (2009). Valoración de los efectos de red en los mercados de software: un enfoque de redes complejas. Springer. p. 142. ISBN 9783790823660.
9. Barrat, A.; Barthelemy, M.; Pastor-Satorras, R.; Vespignani, A. (2004). "La arquitectura de redes ponderadas complejas". Actas de la Academia Nacional de Ciencias . 101 (11): 3747–3752. arXiv : cond-mat/0311416 . Bibcode :2004PNAS..101.3747B. doi : 10.1073/pnas.0400087101 . PMC 374315. PMID  15007165 . 
10. Latapy, M.; Magnien, C.; Del Vecchio, N. (2008). "Nociones básicas para el análisis de grandes redes bimodales" (PDF) . Redes sociales . 30 (1): 31–48. doi :10.1016/j.socnet.2007.04.006.
11. Fagiolo, G. (2007). "Agrupamiento en redes complejas dirigidas". Physical Review E . 76 (2 Pt 2): 026107. arXiv : physics/0612169 . CiteSeerX 10.1.1.262.1006 . doi :10.1103/PhysRevE.76.026107. PMID  17930104. S2CID  2317676. 
12. Clemente, GP; Grassi, R. (2018). "Agrupamiento dirigido en redes ponderadas: una nueva perspectiva". Caos, solitones y fractales . 107 : 26–38. arXiv : 1706.07322 . Código Bibliográfico :2018CSF...107...26C. doi :10.1016/j.chaos.2017.12.007. S2CID  21919524.
13. Kaiser, Marcus (2008). "Coeficientes de agrupamiento medios: el papel de los nodos y hojas aislados en las medidas de agrupamiento para redes de mundo pequeño". New Journal of Physics . 10 (8): 083042. arXiv : 0802.2512 . Bibcode :2008NJPh...10h3042K. doi :10.1088/1367-2630/10/8/083042. S2CID  16480565.
14. Barmpoutis, D.; Murray, RM (2010). "Redes con la distancia promedio más pequeña y el agrupamiento promedio más grande". arXiv : 1007.4031 [q-bio.MN].
15. Berchenko, Yakir; Artzy-Randrup, Yael; Teicher, Mina; Stone, Lewi (30 de marzo de 2009). "Aparición y tamaño del componente gigante en gráficos aleatorios agrupados con una distribución de grados dada". Physical Review Letters . 102 (13): 138701. doi :10.1103/PhysRevLett.102.138701. ISSN  0031-9007. PMID  19392410. Archivado desde el original el 4 de febrero de 2023 . Consultado el 24 de febrero de 2022 .
16. Berchenko, Yakir; Artzy-Randrup, Yael; Teicher, Mina; Stone, Lewi (30 de marzo de 2009). "Aparición y tamaño del componente gigante en gráficos aleatorios agrupados con una distribución de grados dada". Physical Review Letters . 102 (13): 138701. doi :10.1103/PhysRevLett.102.138701. ISSN  0031-9007. PMID  19392410. Archivado desde el original el 4 de febrero de 2023 . Consultado el 24 de febrero de 2022 .
17. MEJ Newman (2009). "Gráficos aleatorios con agrupamiento". Phys. Rev. Lett . 103 (5): 058701. arXiv : 0903.4009 . doi :10.1103/PhysRevLett.103.058701. PMID  19792540. S2CID  28214709.
18. A. Hackett; S. Melnik y JP Gleeson (2011). "Cascadas en una clase de redes aleatorias agrupadas". Phys. Rev. E . 83 (5 Pt 2): 056107. arXiv : 1012.3651 . doi :10.1103/PhysRevE.83.056107. PMID  21728605. S2CID  18071422.

Enlaces externos

• Medios relacionados con Coeficiente de agrupamiento en Wikimedia Commons