En la 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 empate 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 del agrupamiento en la red, mientras que la local da una indicación de la integración de nodos individuales.
Coeficiente de agrupamiento local
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 consiste formalmente en un conjunto de vértices y un conjunto de bordes entre ellos. Un borde conecta el vértice con vértice .
El barrio para un vértice se define como sus vecinos conectados inmediatamente de la siguiente manera:
Definimos como el número de vértices, , en el vecindario, , de un vértice.
El coeficiente de agrupamiento local para un vértice Entonces viene dada por una proporción del número de enlaces entre los vértices dentro de su vecindad dividido por el número de enlaces que posiblemente podrían existir entre ellos. Para un gráfico dirigido, es distinto de , y por lo tanto para cada barrio existen vínculos que podrían existir entre los vértices dentro del vecindario (es el número de vecinos de un vértice). Por lo tanto, el coeficiente de agrupamiento local para gráficos dirigidos se da como [2]
Un grafo no dirigido tiene la propiedad de que y se consideran idénticos. Por tanto, si un vértice posee vecinos, podrían existir aristas entre los vértices dentro del vecindario. Por lo tanto, el coeficiente de agrupamiento local para gráficos no dirigidos se puede definir como
Dejar ser el número de triángulos en para 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 . Dejar 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 incide en ambos bordes. Entonces también podemos definir el coeficiente de agrupamiento como
Es simple mostrar que las dos definiciones anteriores son las mismas, ya que
Estas medidas son 1 si cada vecino conectado a también está conectado a cualquier otro vértice dentro de la vecindad, y 0 si no hay vértice que esté conectado a se conecta a cualquier otro vértice que esté conectado a .
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]
dónde:
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 2 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 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 de la cantidad de triángulos imaginables en los que el vértice i podría estar involucrado.
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 ( nb, 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 lo realizaron Luce y Perry (1949). [4] Esta medida da una indicación del agrupamiento en toda la red (global), y puede aplicarse 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:
- .
El número de tripletes cerrados también se conoce como triángulos de 3 × en la literatura, por lo que:
- .
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 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:
dónde:
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]
Vale la pena señalar que esta métrica coloca más peso en los nodos de bajo grado, mientras que la relación de transitividad coloca más peso en los nodos de alto grado.
Un gráfico se considera de mundo pequeño , si el gráfico tiene una pequeña longitud de ruta media-más corta que escala con el logaritmo natural del número de nodos en la red,. [9] Por ejemplo, un gráfico aleatorio es de mundo pequeño, mientras que un enrejado no lo es, y los gráficos sin escala a menudo se consideran mundo ultrapequeño, ya que su longitud de trayectoria media-más corta escala con.
Una generalización a redes ponderados fue propuesto por Barrat et al. (2004), [10] y una redefinición a grafos bipartitos (también llamados redes de dos modos) por Latapy et al. (2008) [11] y Opsahl (2009). [7]
Fagiolo (2007) [12] y Clemente y Grassi (2018) han proporcionado generalizaciones alternativas a los gráficos ponderados y dirigidos . [13]
Esta fórmula no está definida por defecto para gráficos con vértices aislados; ver Kaiser (2008) [14] y Barmpoutis et al. [15] 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. [15]
Percolación de redes agrupadas
Para estudiar la robustez de las redes agrupadas, se desarrolla un enfoque de percolación. [16] [17] [18] La robustez con respecto a los ataques localizados se ha estudiado utilizando la percolación localizada. [19] También se ha estudiado la localización de ondas en redes complejas agrupadas. [20]
Ver también
- Gráfico dirigido
- Teoría de grafos
- Teoría de redes
- Ciencia de la red
- Teoría de la filtración
- Escale la red libre
- Mundo pequeño
Referencias
- ^ PW Holland y S. Leinhardt (1971). "Transitividad en modelos estructurales de pequeños grupos". Estudios comparativos de grupo . 2 (2): 107–124. doi : 10.1177 / 104649647100200201 .
- ^ a b c DJ Watts y Steven Strogatz (junio de 1998). "Dinámica colectiva de las redes de 'pequeños mundos'". Naturaleza . 393 (6684): 440–442. Código Bibliográfico : 1998Natur.393..440W . doi : 10.1038 / 30918 . PMID 9623998 .
- ^ Wang, Yu; Ghumare, Eshwar; Vandenberghe, Rik; Dupont, Patrick (2017). "Comparación de diferentes generalizaciones de coeficiente de agrupación y eficiencia local para gráficos no dirigidos ponderados" . Computación neuronal . 29 (2): 313–331. doi : 10.1162 / NECO_a_00914 . Consultado el 8 de agosto de 2020 .
- ^ RD Luce y AD Perry (1949). "Un método de análisis matricial de la estructura del grupo". Psychometrika . 14 (1): 95-116. doi : 10.1007 / BF02289146 . hdl : 10.1007 / BF02289146 . PMID 18152948 .
- ^ Stanley Wasserman , Katherine Faust, 1994. Análisis de redes sociales: métodos y aplicaciones. Cambridge: Cambridge University Press.
- ^ 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 .
- ^ a b Tore Opsahl (2009). "Agrupación en redes de dos modos" . Conferencia y taller sobre análisis social de dos modos (30 de septiembre al 2 de octubre de 2009) .
- ^ Kemper, Andreas (2009). Valoración de los efectos de red en los mercados de software: un enfoque de redes complejas . Saltador. pag. 142. ISBN 9783790823660.
- ^ http://networksciencebook.com/4#ultra-small
- ^ 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 . Código bibliográfico : 2004PNAS..101.3747B . doi : 10.1073 / pnas.0400087101 . PMC 374315 . PMID 15007165 .
- ^ Latapy, M .; Magnien, C .; Del Vecchio, N. (2008). "Nociones básicas para el análisis de grandes redes bimodales". Redes sociales . 30 (1): 31–48. doi : 10.1016 / j.socnet.2007.04.006 .
- ^ Fagiolo, G. (2007). "Clustering en redes dirigidas complejas". Revisión E física . 76 (2 Pt 2): 026107. CiteSeerX 10.1.1.262.1006 . doi : 10.1103 / PhysRevE.76.026107 . PMID 17930104 .
- ^ Clemente, GP; 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.chaos.2017.12.007 .
- ^ Kaiser, Marcus (2008). "Coeficientes de agrupamiento medio: el papel de los nodos aislados y hojas en las medidas de agrupamiento para redes de mundo pequeño". 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 .
- ^ a b Barmpoutis, D .; Murray, RM (2010). "Redes con la distancia media más pequeña y la agrupación media más grande". arXiv : 1007.4031 [ q-bio.MN ].
- ^ MEJ Newman (2009). "Gráficos aleatorios con agrupación". Phys. Rev. Lett . 103 : 058701.
- ^ A. Hackett; S. Melnik y JP Gleeson (2011). "Cascadas en una clase de redes aleatorias agrupadas". Phys. Rev. E . 83 : 056107.
- ^ S. Shao; X. Huang; HE Stanley; S. Havlin (2014). "Robustez de una red parcialmente interdependiente formada por redes agrupadas". Phys. Rev. E . 89 : 032812.
- ^ , Fan Wang; Ruijin Du; Lixin Tian; Shuai Shao; H Eugene Stanley; Shlomo Havlin (2019). "Ataque localizado en redes con agrupamiento de Huifang Hao". Nueva Revista de Física . 21 : 013014.
- ^ L. Jahnke; JW Kantelhardt; R. Berkovits; S. Havlin Phys (2008). "Localización de ondas en redes complejas con alta agrupación". Phys. Rev. Lett . 101 : 175702.
enlaces externos
- Medios relacionados con el coeficiente de agrupamiento en Wikimedia Commons