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 gráfico 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 caracterizados 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 gráfico no dirigido. El coeficiente de agrupamiento local del nodo azul se calcula como la proporción de conexiones entre sus vecinos que realmente se realizan en comparación con el número de todas las conexiones posibles. En la figura, el nodo azul tiene tres vecinos, los cuales 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), dando un coeficiente de conglomerado local de 1/3. Finalmente, ninguna de las posibles conexiones entre los vecinos del nodo azul se realiza, lo que produce un valor de coeficiente de agrupamiento local de 0.

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

Un gráfico 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 la vecindad, , del vértice . ${\displaystyle k_{i}}$ ${\displaystyle |N_{i}|}$ ${\displaystyle N_{i}}$ ${\displaystyle v_{i}}$

El coeficiente de agrupamiento local para un vértice viene dado por 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 posiblemente 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 gráficos dirigidos viene dado 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 gráfico 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 de la vecindad. Por lo tanto, el coeficiente de agrupamiento local para gráficos 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 un gráfico 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 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 iguales, 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 todos los demás vértices dentro del vecindario, y 0 si ningún vértice 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 no dirigido simple 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 individuales 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 posiblemente podrían conectarse en triángulos. Para cada par de aristas, 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) lazos no dirigidos. Por lo tanto, un gráfico 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 de la agrupación en toda la red (global) y se puede aplicar tanto a redes dirigidas como no dirigidas (a menudo llamada transitividad, ver 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)}}}}$.

El número de trillizos cerrados también se conoce como 3 × triángulos en la literatura, por lo que:

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

^{Opsahl y Panzarasa (2009), [6]} propusieron una generalización a redes ponderadas 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 otorga más peso a los nodos de bajo grado, mientras que la relación de transitividad otorga más peso a los nodos de alto grado.

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

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

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 encuentra que las redes con el mayor coeficiente de agrupamiento promedio posible tienen una estructura modular y, al mismo tiempo, tienen la menor distancia promedio posible entre los diferentes nodos. ^[14]

Percolación de redes agrupadas

Para una red aleatoria en forma de á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 grados 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 filtració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 un alto nivel de agrupamiento, un fuerte agrupamiento podría inducir la estructura centro-periferia, en la que el núcleo y la periferia podrían filtrarse en diferentes puntos críticos, y el tratamiento aproximado anterior no es aplicable. ^[dieciséis]

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

Ver también

• Gráfico dirigido
• Teoría de grafos
• Teoría de redes
• ciencia de la red
• Teoría de la percolación
• Red libre de escala
• Mundo pequeño

Referencias

1. PW Holanda y S. Leinhardt (1971). "Transitividad en modelos estructurales de pequeños grupos". 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 'mundos pequeños'". Naturaleza . 393 (6684): 440–442. Código Bib :1998Natur.393..440W. doi :10.1038/30918. PMID  9623998. S2CID  4429113.
3. Wang, Yu; Ghumare, Eshwar; Vandenberghe, Rik; Dupont, Patricio (2017). "Comparación de diferentes generalizaciones del coeficiente de agrupamiento y la eficiencia local para gráficos no dirigidos ponderados". Computación neuronal . 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 del grupo". Psicometrika . 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: Prensa de la Universidad de Cambridge.
6. Tore Opsahl y Pietro Panzarasa (2009). "Agrupación en redes ponderadas". 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). "Agrupación en redes bimodales". Conferencia y taller sobre análisis social bimodal (30 de septiembre al 2 de octubre de 2009) . Archivado desde el original el 21 de marzo de 2016 . Consultado el 11 de septiembre de 2009 .
8. Kemper, Andrés (2009). Valoración de los efectos de la red en los mercados de software: un enfoque de redes complejas. Saltador. pag. 142.ISBN​ 9783790823660.
9. Barrat, A.; Bartolomé, M.; Pastor-Satorras, R.; Vespignani, A. (2004). "La arquitectura de redes ponderadas complejas". Procedimientos de la Academia Nacional de Ciencias . 101 (11): 3747–3752. arXiv : cond-mat/0311416 . Código bibliográfico : 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). "Agrupación en redes dirigidas complejas". Revisión física E. 76 (2 parte 2): 026107. arXiv : física/0612169 . CiteSeerX 10.1.1.262.1006 . doi : 10.1103/PhysRevE.76.026107. PMID  17930104. S2CID  2317676. 
12. Clemente, médico de cabecera; Grassi, R. (2018). "Agrupación dirigida en redes ponderadas: una nueva perspectiva". Caos, solitones y fractales . 107 : 26–38. arXiv : 1706.07322 . Código Bib : 2018CSF...107...26C. doi :10.1016/j.caos.2017.12.007. S2CID  21919524.
13. Káiser, Marcus (2008). "Coeficientes de agrupación medios: el papel de los nodos y hojas aislados en las medidas de agrupación para redes de mundos pequeños". Nueva Revista de Física . 10 (8): 083042. arXiv : 0802.2512 . Código bibliográfico : 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 la agrupación promedio más grande". arXiv : 1007.4031 [q-bio.MN].
15. Berchenko, Yakir; Artzy-Randrup, Yael; Teicher, Mina; Piedra, Lewis (30 de marzo de 2009). "Aparición y tamaño del componente gigante en gráficos aleatorios agrupados con una distribución de grados determinada". Cartas de revisión física . 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; Piedra, Lewis (30 de marzo de 2009). "Aparición y tamaño del componente gigante en gráficos aleatorios agrupados con una distribución de grados determinada". Cartas de revisión física . 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 agrupación". Física. 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". Física. Rev. E. 83 (5 partes 2): 056107. arXiv : 1012.3651 . doi : 10.1103/PhysRevE.83.056107. PMID  21728605. S2CID  18071422.

enlaces externos

• Medios relacionados con el coeficiente de agrupamiento en Wikimedia Commons