En el estudio de redes complejas , se dice que una red tiene estructura comunitaria si los nodos de la red pueden agruparse fácilmente en conjuntos de nodos (potencialmente superpuestos) de modo que cada conjunto de nodos esté densamente conectado internamente. En el caso particular de un hallazgo de comunidad no superpuesto , esto implica que la red se divide naturalmente en grupos de nodos con conexiones densas internamente y conexiones más dispersas entre grupos. Pero superpuestotambién se permiten comunidades. La definición más general se basa en el principio de que es más probable que los pares de nodos estén conectados si ambos son miembros de la (s) misma (s) comunidad (s), y es menos probable que estén conectados si no comparten comunidades. Un problema relacionado pero diferente es la búsqueda de comunidades , donde el objetivo es encontrar una comunidad a la que pertenece un determinado vértice.
Propiedades
En el estudio de las redes , como las redes informáticas y de información, las redes sociales y las redes biológicas, se ha encontrado que ocurren comúnmente una serie de características diferentes, incluida la propiedad del mundo pequeño , las distribuciones de grados de cola pesada y la agrupación , entre otras. Otra característica común es la estructura comunitaria. [1] [2] [3] [4] [5] En el contexto de las redes, la estructura de la comunidad se refiere a la aparición de grupos de nodos en una red que están más densamente conectados internamente que con el resto de la red, como se muestra. en la imagen de ejemplo a la derecha. Esta falta de homogeneidad de conexiones sugiere que la red tiene ciertas divisiones naturales dentro de ella.
Las comunidades a menudo se definen en términos de la partición del conjunto de vértices, es decir, cada nodo se coloca en una y solo una comunidad, tal como se muestra en la figura. Esta es una simplificación útil y la mayoría de los métodos de detección de comunidades encuentran este tipo de estructura comunitaria. Sin embargo, en algunos casos, una mejor representación podría ser aquella en la que los vértices se encuentran en más de una comunidad. Esto puede suceder en una red social donde cada vértice representa a una persona y las comunidades representan los diferentes grupos de amigos: una comunidad para la familia, otra comunidad para los compañeros de trabajo, una para los amigos del mismo club deportivo, etc. El uso de camarillas para la detección de comunidades que se analiza a continuación es solo un ejemplo de cómo se puede encontrar esa estructura comunitaria superpuesta.
Algunas redes pueden no tener una estructura comunitaria significativa. Muchos modelos de red básicos, por ejemplo, como el gráfico aleatorio y el modelo Barabási-Albert , no muestran la estructura de la comunidad.
Importancia
Las estructuras comunitarias son bastante comunes en las redes reales. Las redes sociales incluyen grupos comunitarios (el origen del término, de hecho) basados en una ubicación común, intereses, ocupación, etc. [5] [6]
Encontrar una estructura comunitaria subyacente en una red, si existe, es importante por varias razones. Las comunidades nos permiten crear un mapa a gran escala de una red, ya que las comunidades individuales actúan como meta-nodos en la red, lo que facilita su estudio. [7]
Las comunidades individuales también arrojan luz sobre la función del sistema representado por la red, ya que las comunidades a menudo corresponden a unidades funcionales del sistema. En las redes metabólicas, dichos grupos funcionales corresponden a ciclos o vías, mientras que en la red de interacción de proteínas , las comunidades corresponden a proteínas con una funcionalidad similar dentro de una célula biológica. De manera similar, las redes de citas forman comunidades por tema de investigación. [1] Ser capaz de identificar estas subestructuras dentro de una red puede proporcionar información sobre cómo la función y la topología de la red se afectan entre sí. Esta información puede ser útil para mejorar algunos algoritmos en gráficos como el agrupamiento espectral . [8]
Una razón muy importante que hace que las comunidades sean importantes es que a menudo tienen propiedades muy diferentes a las propiedades promedio de las redes. Por lo tanto, concentrarse solo en las propiedades promedio generalmente pierde muchas características importantes e interesantes dentro de las redes. Por ejemplo, en una red social determinada, pueden existir simultáneamente grupos gregarios y reticentes. [7]
La existencia de comunidades también generalmente afecta a varios procesos como la propagación de rumores o la propagación de epidemias que ocurren en una red. Por lo tanto, para comprender adecuadamente estos procesos, es importante detectar comunidades y también estudiar cómo afectan los procesos de propagación en varios entornos.
Finalmente, una aplicación importante que la detección de comunidades ha encontrado en la ciencia de redes es la predicción de enlaces perdidos y la identificación de enlaces falsos en la red. Durante el proceso de medición, es posible que algunos enlaces no se observen por varias razones. Del mismo modo, algunos enlaces podrían ingresar falsamente en los datos debido a los errores en la medición. Ambos casos están bien manejados por el algoritmo de detección de la comunidad, ya que permite asignar la probabilidad de existencia de un borde entre un par de nodos dado. [9]
Algoritmos para encontrar comunidades
Encontrar comunidades dentro de una red arbitraria puede ser una tarea computacionalmente difícil. El número de comunidades, si las hay, dentro de la red generalmente se desconoce y las comunidades son a menudo de tamaño y / o densidad desiguales. Sin embargo, a pesar de estas dificultades, se han desarrollado y empleado varios métodos para encontrar comunidades con distintos niveles de éxito. [4]
Método de corte mínimo
Uno de los algoritmos más antiguos para dividir redes en partes es el método de corte mínimo (y variantes como corte de relación y corte normalizado). Este método se utiliza, por ejemplo, en el equilibrio de carga para la computación en paralelo con el fin de minimizar la comunicación entre los nodos del procesador.
En el método de corte mínimo, la red se divide en un número predeterminado de partes, generalmente de aproximadamente el mismo tamaño, elegidas de manera que se minimice el número de bordes entre grupos. El método funciona bien en muchas de las aplicaciones para las que se diseñó originalmente, pero no es ideal para encontrar la estructura de la comunidad en redes generales, ya que encontrará comunidades independientemente de si están implícitas en la estructura, y solo encontrará un número fijo. de ellos. [10]
Agrupación jerárquica
Otro método para encontrar estructuras comunitarias en redes es la agrupación jerárquica . En este método, se define una medida de similitud que cuantifica algún tipo (generalmente topológico) de similitud entre pares de nodos. Las medidas comúnmente utilizadas incluyen la similitud del coseno , el índice de Jaccard y la distancia de Hamming entre filas de la matriz de adyacencia . Luego, se agrupan nodos similares en comunidades de acuerdo con esta medida. Existen varios esquemas comunes para realizar la agrupación, los dos más simples son la agrupación de un solo enlace , en el que dos grupos se consideran comunidades separadas si y solo si todos los pares de nodos en diferentes grupos tienen una similitud menor que un umbral dado, y una agrupación de vinculación completa , en el que todos los nodos dentro de cada grupo tienen una similitud mayor que un umbral. Un paso importante es cómo determinar el umbral para detener la agrupación aglomerativa, lo que indica una estructura comunitaria cercana a la óptima. Una estrategia común consiste en construir una o varias métricas que monitorean las propiedades globales de la red, que alcanzan su punto máximo en un paso dado de la agrupación. Un enfoque interesante en este sentido es el uso de diferentes medidas de similitud o disimilitud, combinado a través de sumas convexas , [11] . Otra aproximación es el cálculo de una cantidad que monitorea la densidad de aristas dentro de conglomerados con respecto a la densidad entre conglomerados, como la densidad de partición, que se ha propuesto cuando se define la métrica de similitud entre aristas (lo que permite la definición de comunidades superpuestas). , [12] y extendido cuando se define la similitud entre nodos, lo que permite considerar definiciones alternativas de comunidades como gremios (es decir, grupos de nodos que comparten un número similar de enlaces con respecto a los mismos vecinos pero no necesariamente conectados entre sí). [13] Estos métodos pueden extenderse para considerar redes multidimensionales, por ejemplo, cuando se trata de redes que tienen nodos con diferentes tipos de enlaces. [13]
Algoritmo de Girvan-Newman
Otro algoritmo comúnmente utilizado para encontrar comunidades es el algoritmo Girvan-Newman . [1] Este algoritmo identifica los bordes en una red que se encuentran entre las comunidades y luego los elimina, dejando atrás solo las comunidades. La identificación se realiza empleando la centralidad de intermediación de la medida de la teoría gráfica , que asigna un número a cada borde que es grande si el borde se encuentra "entre" muchos pares de nodos.
El algoritmo Girvan-Newman devuelve resultados de calidad razonable y es popular porque se ha implementado en varios paquetes de software estándar. Pero también funciona lentamente, tardando O ( m 2 n ) en una red de n vértices y m bordes, lo que lo hace poco práctico para redes de más de unos pocos miles de nodos. [14]
Maximización de la modularidad
A pesar de sus conocidos inconvenientes, uno de los métodos más utilizados para la detección de comunidades es la maximización de la modularidad. [14] La modularidad es una función de beneficio que mide la calidad de una división particular de una red en comunidades. El método de maximización de la modularidad detecta comunidades al buscar en las posibles divisiones de una red una o más que tengan una modularidad particularmente alta. Dado que la búsqueda exhaustiva de todas las divisiones posibles suele ser intratable, los algoritmos prácticos se basan en métodos de optimización aproximados, como algoritmos codiciosos, recocido simulado u optimización espectral, con diferentes enfoques que ofrecen diferentes equilibrios entre velocidad y precisión. [15] [16] Un enfoque popular de maximización de la modularidad es el método Louvain , que optimiza iterativamente las comunidades locales hasta que la modularidad global ya no puede mejorarse debido a las perturbaciones del estado actual de la comunidad. [17] [18] Un algoritmo que utiliza el esquema RenEEL, que es un ejemplo del paradigma Extremal Ensemble Learning (EEL), es actualmente el mejor algoritmo de maximización de modularidad. [19] [20]
La utilidad de la optimización de la modularidad es cuestionable, ya que se ha demostrado que la optimización de la modularidad a menudo no detecta clústeres más pequeños que alguna escala, dependiendo del tamaño de la red ( límite de resolución [21] ); por otro lado, el panorama de los valores de modularidad se caracteriza por una enorme degeneración de particiones con alta modularidad, cercanas al máximo absoluto, que pueden ser muy diferentes entre sí. [22]
Inferencia estadística
Los métodos basados en la inferencia estadística intentan ajustar un modelo generativo a los datos de la red, que codifica la estructura de la comunidad. La ventaja general de este enfoque en comparación con las alternativas es su naturaleza más basada en principios y la capacidad de abordar de manera inherente cuestiones de importancia estadística . La mayoría de los métodos en la literatura se basan en el modelo de bloque estocástico [23] , así como en variantes que incluyen membresía mixta, [24] [25] corrección de grados, [26] y estructuras jerárquicas. [27] La selección del modelo se puede realizar utilizando enfoques basados en principios, como la longitud mínima de descripción [28] [29] (o de manera equivalente, la selección del modelo bayesiano [30] ) y la prueba de razón de verosimilitud . [31] Actualmente existen muchos algoritmos para realizar inferencias eficientes de modelos de bloques estocásticos, incluida la propagación de creencias [32] [33] y el Monte Carlo aglomerativo . [34]
A diferencia de los enfoques que intentan agrupar una red dada una función objetiva, esta clase de métodos se basa en modelos generativos, que no solo sirven como descripción de la estructura a gran escala de la red, sino que también se pueden utilizar para generalizar la red. datos y predecir la aparición de enlaces faltantes o espurios en la red. [35] [36]
Métodos basados en camarillas
Las camarillas son subgrafos en los que cada nodo está conectado a todos los demás nodos de la camarilla. Como los nodos no pueden estar más estrechamente conectados que esto, no es de extrañar que existan muchos enfoques para la detección de comunidades en redes basados en la detección de camarillas en un gráfico y el análisis de cómo se superponen. Tenga en cuenta que como un nodo puede ser miembro de más de una camarilla, un nodo puede ser miembro de más de una comunidad en estos métodos, lo que proporciona una " estructura de comunidad superpuesta ".
Un enfoque es encontrar las " camarillas máximas ". Eso es encontrar las camarillas que no son el subgrafo de ninguna otra camarilla. El algoritmo clásico para encontrarlos es el algoritmo de Bron – Kerbosch . La superposición de estos se puede utilizar para definir comunidades de varias formas. La más simple es considerar solo las camarillas máximas mayores que un tamaño mínimo (número de nodos). La unión de estas camarillas define entonces un subgrafo cuyos componentes (partes desconectadas) definen comunidades. [37] Estos enfoques se implementan a menudo en software de análisis de redes sociales como UCInet.
El enfoque alternativo es utilizar camarillas de tamaño fijo. . La superposición de estos se puede utilizar para definir un tipo de-Hipergrama regular o una estructura que es una generalización del gráfico de líneas (el caso cuando) conocido como " gráfico Clique ". [38] Los gráficos de la camarilla tienen vértices que representan las camarillas en el gráfico original, mientras que los bordes del gráfico de la camarilla registran la superposición de la camarilla en el gráfico original. La aplicación de cualquiera de los métodos de detección de comunidad anteriores (que asignan cada nodo a una comunidad) al gráfico de la camarilla, luego asigna cada camarilla a una comunidad. Esto se puede utilizar para determinar la pertenencia a la comunidad de los nodos de las camarillas. Nuevamente, como un nodo puede estar en varias camarillas, puede ser miembro de varias comunidades. Por ejemplo, el método de percolación de camarillas [39] define a las comunidades como grupos de percolación de k {\ Displaystyle k} -cliques . Para hacer esto encuentra todo-cliques en una red, es decir, todos los subgrafos completos de -nodos. Luego define dos-cliques para ser adyacentes si comparten nodos, es decir, esto se usa para definir bordes en un gráfico de camarilla. Una comunidad se define entonces como la unión máxima de-cliques en los que podemos llegar a cualquier -clique de cualquier otro -clique a través de series de -clique adyacencias. Es decir, las comunidades son solo los componentes conectados en el gráfico de la camarilla. Dado que un nodo puede pertenecer a varios-clique grupos de percolación al mismo tiempo, las comunidades pueden superponerse entre sí.
Métodos de prueba para encontrar algoritmos de comunidades
La evaluación de algoritmos, para detectar cuáles son mejores para detectar la estructura de la comunidad, sigue siendo una cuestión abierta. Debe basarse en análisis de redes de estructura conocida. Un ejemplo típico es la prueba de "cuatro grupos", en la que una red se divide en cuatro grupos de igual tamaño (generalmente de 32 nodos cada uno) y las probabilidades de conexión dentro y entre grupos varían para crear estructuras más o menos desafiantes para la detección. algoritmo. Estos gráficos de referencia son un caso especial del modelo de partición l plantado [40] de Condon y Karp , o más generalmente de " modelos de bloques estocásticos ", una clase general de modelos de red aleatorios que contienen estructura comunitaria. Se han propuesto otros puntos de referencia más flexibles que permiten diferentes tamaños de grupo y distribuciones de grado no triviales, como el punto de referencia LFR [41] [42], que es una extensión del punto de referencia de cuatro grupos que incluye distribuciones heterogéneas de grado de nodo y tamaño de comunidad, lo que lo convierte en una prueba más severa de los métodos de detección de la comunidad. [43] [44]
Los puntos de referencia generados por computadora de uso común comienzan con una red de comunidades bien definidas. Luego, esta estructura se degrada al volver a cablear o eliminar enlaces y cada vez es más difícil para los algoritmos detectar la partición original. Al final, la red llega a un punto en el que es esencialmente aleatorio. Este tipo de punto de referencia puede denominarse "abierto". El desempeño en estos puntos de referencia se evalúa mediante medidas como la información mutua normalizada o la variación de la información . Comparan la solución obtenida por un algoritmo [42] con la estructura de la comunidad original, evaluando la similitud de ambas particiones.
Detectabilidad
Durante los últimos años, varios grupos han obtenido un resultado bastante sorprendente que muestra que existe una fase de transición en el problema de detección de comunidades, mostrando que a medida que la densidad de conexiones dentro de las comunidades y entre comunidades se vuelve cada vez más igual o ambas se reducen (equivalentemente , a medida que la estructura de la comunidad se vuelve demasiado débil o la red se vuelve demasiado escasa), de repente las comunidades se vuelven indetectables. En cierto sentido, las comunidades mismas todavía existen, ya que la presencia y ausencia de bordes todavía está correlacionada con la pertenencia a la comunidad de sus puntos finales; pero se vuelve teóricamente imposible etiquetar los nodos mejor que el azar, o incluso distinguir el gráfico de uno generado por un modelo nulo como el modelo Erdos-Renyi sin estructura comunitaria. Esta transición es independiente del tipo de algoritmo que se utiliza para detectar comunidades, lo que implica que existe un límite fundamental en nuestra capacidad para detectar comunidades en las redes, incluso con una inferencia bayesiana óptima (es decir, independientemente de nuestros recursos computacionales). [45] [46] [47]
Considere un modelo de bloque estocástico con total nodos, grupos de igual tamaño, y dejar y ser las probabilidades de conexión dentro y entre los grupos, respectivamente. Si, la red poseería una estructura de comunidad ya que la densidad de enlaces dentro de los grupos sería mayor que la densidad de enlaces entre los grupos. En el caso escaso, y escala como de modo que el grado medio sea constante:
- y
Entonces se vuelve imposible detectar las comunidades cuando: [46]
Resistencia de las redes modulares
La resiliencia de las redes modulares debido a fallas de nodos o enlaces generalmente se estudia utilizando la teoría de la filtración. Se ha estudiado la estructura de la red mientras ataca los inter-nodos (es decir, nodos que conectan comunidades). [48] Además, un estudio reciente analizó cómo los vínculos entre comunidades fortalecen la resiliencia de las comunidades. [49] Un estudio reciente de Gaogao Dong et al identificó estructuras modulares de resistencia óptima. [50]
Epidemias en redes modulares
El estudio de modelos epidémicos en redes modulares ha sido estudiado por Valdez et al. [51] Estos autores también estudiaron el criterio para declarar una pandemia.
Redes modulares espaciales
Gross et al. Han desarrollado un modelo para redes espacialmente modulares. [52] El modelo describe, por ejemplo, infraestructuras en un país donde las comunidades (módulos) representan ciudades con muchas conexiones ubicadas en un espacio bidimensional. Los vínculos entre comunidades (ciudades) son menores y generalmente con los vecinos más cercanos (ver Fig. 2). La propagación de la epidemia en estas redes se ha estudiado en Gross y Havlin. [53]
Ver también
- Red compleja
- Jerarquía
- Teoría de redes
- Teoría de la filtración
Referencias
- ^ a b c M. Girvan ; MEJ Newman (2002). "Estructura comunitaria en redes sociales y biológicas" . Proc. Natl. Acad. Sci. USA . 99 (12): 7821–7826. arXiv : cond-mat / 0112110 . Código Bibliográfico : 2002PNAS ... 99.7821G . doi : 10.1073 / pnas.122653799 . PMC 122977 . PMID 12060727 .
- ^ S. Fortunato (2010). "Detección de comunidades en gráficos". Phys. Rep . 486 (3-5): 75-174. arXiv : 0906.0612 . Código Bibliográfico : 2010PhR ... 486 ... 75F . doi : 10.1016 / j.physrep.2009.11.002 . S2CID 10211629 .
- ^ FD Malliaros; M. Vazirgiannis (2013). "Clustering y detección de comunidades en redes dirigidas: una encuesta". Phys. Rep . 533 (4): 95-142. arXiv : 1308.0971 . Código Bibliográfico : 2013PhR ... 533 ... 95M . doi : 10.1016 / j.physrep.2013.08.002 . S2CID 15006738 .
- ^ a b MA Porter; J.-P. Onnela; PJ Mucha (2009). "Comunidades en redes" (PDF) . Avisos de la Sociedad Matemática Estadounidense . 56 : 1082-1097, 1164-1166.
- ^ a b Fani, Hossein; Bagheri, Ebrahim (2017). "Detección de comunidades en redes sociales". Enciclopedia con Computación Semántica e Inteligencia Robótica . 1 . págs. 1630001 [8]. doi : 10.1142 / S2425038416300019 .
- ^ Hamdaqa, Mohammad; Tahvildari, Ladan; LaChapelle, Neil; Campbell, Brian (2014). "Detección de escenas culturales con optimización inversa de Louvain" . Ciencia de la Programación de Computadores . 95 : 44–72. doi : 10.1016 / j.scico.2014.01.006 .
- ^ a b MEJNeman (2006). "Encontrar estructura de comunidad en redes utilizando los vectores propios de matrices". Phys. Rev. E . 74 (3): 1–19. arXiv : física / 0605087 . Código Bibliográfico : 2006PhRvE..74c6104N . doi : 10.1103 / PhysRevE.74.036104 . PMID 17025705 . S2CID 138996 .
- ^ Zare, Habil; P. Shooshtari; A. Gupta; R. Brinkman (2010). "Reducción de datos para la agrupación espectral para analizar datos de citometría de flujo de alto rendimiento" . BMC Bioinformática . 11 (1): 403. doi : 10.1186 / 1471-2105-11-403 . PMC 2923634 . PMID 20667133 .
- ^ Aaron Clauset; Cristopher Moore; MEJ Newman (2008). "Estructura jerárquica y predicción de enlaces perdidos en redes". Naturaleza . 453 (7191): 98–101. arXiv : 0811.0484 . Código Bib : 2008Natur.453 ... 98C . doi : 10.1038 / nature06830 . PMID 18451861 . S2CID 278058 .
- ^ MEJ Newman (2004). "Detección de estructura comunitaria en redes". EUR. Phys. J. B . 38 (2): 321–330. Código Bibliográfico : 2004EPJB ... 38..321N . doi : 10.1140 / epjb / e2004-00124-y . hdl : 2027,42 / 43867 . S2CID 15412738 .
- ^ Álvarez, Alejandro J .; Sanz-Rodríguez, Carlos E .; Cabrera, Juan Luis (13/12/2015). "Ponderación de disimilitudes para detectar comunidades en redes" . Phil. Trans. R. Soc. Una . 373 (2056): 20150108. Código Bibliográfico : 2015RSPTA.37350108A . doi : 10.1098 / rsta.2015.0108 . ISSN 1364-503X . PMID 26527808 .
- ^ Ahn, Y.-Y .; Bagrow, JP; Lehmann, S. (2010). "Las comunidades de enlaces revelan la complejidad de múltiples escalas en las redes". Naturaleza . 466 (7307): 761–764. arXiv : 0903.3178 . doi : 10.1038 / nature09182 . PMID 20562860 .
- ^ a b Pascual-García, Alberto; Bell, Thomas (2020). "functionInk: Un método eficiente para detectar grupos funcionales en redes multidimensionales revela la estructura oculta de las comunidades ecológicas". Métodos Ecol Evol . 11 (7): 804–817. doi : 10.1111 / 2041-210X.13377 .
- ^ a b MEJ Newman (2004). "Algoritmo rápido para la detección de estructura comunitaria en redes". Phys. Rev. E . 69 (6): 066133. arXiv : cond-mat / 0309508 . Código Bibliográfico : 2004PhRvE..69f6133N . doi : 10.1103 / PhysRevE.69.066133 . PMID 15244693 . S2CID 301750 .
- ^ L. Danon; J. Duch; A. Díaz-Guilera; A. Arenas (2005). "Comparación de la identificación de la estructura de la comunidad". J. Stat. Mech . 2005 (9): P09008. arXiv : cond-mat / 0505245 . Código Bibliográfico : 2005JSMTE..09..008D . doi : 10.1088 / 1742-5468 / 2005/09 / P09008 . S2CID 14798969 .
- ^ R. Guimera; LAN Amaral (2005). "Cartografía funcional de redes metabólicas complejas" . Naturaleza . 433 (7028): 895–900. arXiv : q-bio / 0502035 . Código Bibliográfico : 2005Natur.433..895G . doi : 10.1038 / nature03288 . PMC 2175124 . PMID 15729348 .
- ^ VD Blondel; J.-L. Guillaume; R. Lambiotte; E. Lefebvre (2008). "Despliegue rápido de jerarquías comunitarias en grandes redes". J. Stat. Mech . 2008 (10): P10008. arXiv : 0803.0476 . Código bibliográfico : 2008JSMTE..10..008B . doi : 10.1088 / 1742-5468 / 2008/10 / P10008 . S2CID 334423 .
- ^ "Detección de comunidad ultrarrápida en las redes sociales: una implementación escalable del algoritmo de Louvain". 2013. S2CID 16164925 . Cite journal requiere
|journal=
( ayuda ) - ^ J. Guo; P. Singh; KE Bassler (2019). "Esquema de aprendizaje de conjuntos extremos de redes reducidas (RenEEL) para la detección de comunidades en redes complejas" . Informes científicos . 9 (14234): 14234. arXiv : 1909.10491 . Código Bib : 2019NatSR ... 914234G . doi : 10.1038 / s41598-019-50739-3 . PMC 6775136 . PMID 31578406 .
- ^ "RenEEL-Modularidad" . 31 de octubre de 2019.
- ^ S. Fortunato; M. Barthelemy (2007). "Límite de resolución en la detección de comunidades" . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 104 (1): 36–41. arXiv : física / 0607100 . Código Bibliográfico : 2007PNAS..104 ... 36F . doi : 10.1073 / pnas.0605965104 . PMC 1765466 . PMID 17190818 .
- ^ BH Bueno; Y.-A. de Montjoye; A. Clauset (2010). "El rendimiento de la maximización de la modularidad en contextos prácticos". Phys. Rev. E . 81 (4): 046106. arXiv : 0910.0165 . Código bibliográfico : 2010PhRvE..81d6106G . doi : 10.1103 / PhysRevE.81.046106 . PMID 20481785 . S2CID 16564204 .
- ^ Holanda, Paul W .; Kathryn Blackmond Laskey; Samuel Leinhardt (junio de 1983). "Modelos de bloques estocásticos: Primeros pasos". Redes sociales . 5 (2): 109-137. doi : 10.1016 / 0378-8733 (83) 90021-7 . ISSN 0378-8733 .
- ^ Airoldi, Edoardo M .; David M. Blei; Stephen E. Fienberg; Eric P. Xing (junio de 2008). "Modelos de bloques estocásticos de pertenencia mixta" . J. Mach. Aprender. Res . 9 : 1981–2014. ISSN 1532-4435 . PMC 3119541 . PMID 21701698 . Consultado el 9 de octubre de 2013 .
- ^ Ball, Brian; Brian Karrer; MEJ Newman (2011). "Método eficiente y de principios para la detección de comunidades en redes". Revisión E física . 84 (3): 036103. arXiv : 1104.3590 . Código bibliográfico : 2011PhRvE..84c6103B . doi : 10.1103 / PhysRevE.84.036103 . PMID 22060452 . S2CID 14204351 .
- ^ Karrer, Brian; MEJ Newman (21 de enero de 2011). "Bloques estocásticos y estructura comunitaria en redes". Revisión E física . 83 (1): 016107. arXiv : 1008.3926 . Código bibliográfico : 2011PhRvE..83a6107K . doi : 10.1103 / PhysRevE.83.016107 . PMID 21405744 . S2CID 9068097 .
- ^ Peixoto, Tiago P. (24 de marzo de 2014). "Estructuras de bloques jerárquicos y selección de modelos de alta resolución en grandes redes". Physical Review X . 4 (1): 011047. arXiv : 1310.4377 . Código Bibliográfico : 2014PhRvX ... 4a1047P . doi : 10.1103 / PhysRevX.4.011047 . S2CID 5841379 .
- ^ Martin Rosvall; Carl T. Bergstrom (2007). "Un marco teórico de la información para resolver la estructura de la comunidad en redes complejas" . Actas de la Academia Nacional de Ciencias de los Estados Unidos de América . 104 (18): 7327–7331. arXiv : física / 0612035 . Código Bibliográfico : 2007PNAS..104.7327R . doi : 10.1073 / pnas.0611034104 . PMC 1855072 . PMID 17452639 .
- ^ P. Peixoto, T. (2013). "Inferencia de módulo parsimonioso en grandes redes". Phys. Rev. Lett . 110 (14): 148701. arXiv : 1212.4794 . Código Bibliográfico : 2013PhRvL.110n8701P . doi : 10.1103 / PhysRevLett.110.148701 . PMID 25167049 . S2CID 2668815 .
- ^ P. Peixoto, T. (2019). "Modelado de bloques estocásticos bayesianos". Avances en agrupación en clústeres de redes y modelado de bloques . págs. 289–332. arXiv : 1705.10225 . doi : 10.1002 / 9781119483298.ch11 . ISBN 9781119224709. S2CID 62900189 .
- ^ Yan, Xiaoran; Jacob E. Jensen; Florent Krzakala; Cristopher Moore; Cosma Rohilla Shalizi; Lenka Zdeborová ; Pan Zhang; Yaojia Zhu (17 de julio de 2012). "Selección de modelos para modelos de bloques con corrección de grados" . Revista de Mecánica Estadística: Teoría y Experimento . 2014 (5): P05007. arXiv : 1207.3994 . Código bibliográfico : 2014JSMTE..05..007Y . doi : 10.1088 / 1742-5468 / 2014/05 / P05007 . PMC 4498413 . PMID 26167197 .
- ^ Gopalan, Prem K .; David M. Blei (3 de septiembre de 2013). "Descubrimiento eficiente de comunidades superpuestas en redes masivas" . Actas de la Academia Nacional de Ciencias . 110 (36): 14534-14539. Código bibliográfico : 2013PNAS..11014534G . doi : 10.1073 / pnas.1221839110 . ISSN 0027-8424 . PMC 3767539 . PMID 23950224 .
- ^ Decelle, Aurelien; Florent Krzakala; Cristopher Moore; Lenka Zdeborová ( 12 de diciembre de 2011 ). "Análisis asintótico del modelo de bloques estocásticos para redes modulares y sus aplicaciones algorítmicas". Revisión E física . 84 (6): 066106. arXiv : 1109.3041 . Código Bibliográfico : 2011PhRvE..84f6106D . doi : 10.1103 / PhysRevE.84.066106 . PMID 22304154 . S2CID 15788070 .
- ^ Peixoto, Tiago P. (13 de enero de 2014). "Montecarlo eficiente y heurístico codicioso para la inferencia de modelos de bloques estocásticos". Revisión E física . 89 (1): 012804. arXiv : 1310.4378 . Código Bibliográfico : 2014PhRvE..89a2804P . doi : 10.1103 / PhysRevE.89.012804 . PMID 24580278 . S2CID 2674083 .
- ^ Guimerà, Roger; Marta Sales-Pardo (29 de diciembre de 2009). "Interacciones faltantes y espurias y reconstrucción de redes complejas" . Actas de la Academia Nacional de Ciencias . 106 (52): 22073–22078. arXiv : 1004.4791 . Código Bibliográfico : 2009PNAS..10622073G . doi : 10.1073 / pnas.0908366106 . PMC 2799723 . PMID 20018705 .
- ^ Clauset, Aaron; Cristopher Moore; MEJ Newman (1 de mayo de 2008). "Estructura jerárquica y predicción de enlaces perdidos en redes". Naturaleza . 453 (7191): 98–101. arXiv : 0811.0484 . Código Bib : 2008Natur.453 ... 98C . doi : 10.1038 / nature06830 . ISSN 0028-0836 . PMID 18451861 . S2CID 278058 .
- ^ MG Everett; SP Borgatti (1998). "Análisis de conexiones de superposición de camarillas". Conexiones . 21 : 49.
- ^ TS Evans (2010). "Gráficos de camarillas y comunidades superpuestas". J. Stat. Mech . 2010 (12): P12037. arXiv : 1009.0638 . Código bibliográfico : 2010JSMTE..12..037E . doi : 10.1088 / 1742-5468 / 2010/12 / P12037 . S2CID 2783670 .
- ^ G. Palla; I. Derényi; I. Farkas; T. Vicsek (2005). "Descubriendo la estructura comunitaria superpuesta de redes complejas en la naturaleza y la sociedad". Naturaleza . 435 (7043): 814–818. arXiv : física / 0506133 . Código Bibliográfico : 2005Natur.435..814P . doi : 10.1038 / nature03607 . PMID 15944704 . S2CID 3250746 .
- ^ Condon, A .; Karp, RM (2001). "Algoritmos para la partición gráfica en el modelo de partición plantado". Estructura aleatoria. Algor . 18 (2): 116-140. CiteSeerX 10.1.1.22.4340 . doi : 10.1002 / 1098-2418 (200103) 18: 2 <116 :: AID-RSA1001> 3.0.CO; 2-2 .
- ^ A. Lancichinetti; S. Fortunato; F. Radicchi (2008). "Gráficos de referencia para probar algoritmos de detección de comunidades". Phys. Rev. E . 78 (4): 046110. arXiv : 0805.4770 . Código Bibliográfico : 2008PhRvE..78d6110L . doi : 10.1103 / PhysRevE.78.046110 . PMID 18999496 . S2CID 18481617 .
- ^ a b Fathi, Reza (abril de 2019). "Detección de comunidad distribuida eficiente en el modelo de bloque estocástico". arXiv : 1904.07494 [ cs.DC ].
- ^ Pasta MQ; F. Zaidi (2017). "Aprovechando la dinámica de la evolución para generar redes complejas de referencia con estructuras comunitarias". arXiv : 1606.01169 [ cs.SI ].
- ^ Pasta, MQ; Zaidi, F. (2017). "Topología de redes complejas y limitaciones de rendimiento de algoritmos de detección de comunidad" . Acceso IEEE . 5 : 10901–10914. doi : 10.1109 / ACCESS.2017.2714018 .
- ^ Reichardt, J .; Leone, M. (2008). "Estructura de clúster (no) detectable en redes dispersas". Phys. Rev. Lett . 101 (78701): 1–4. arXiv : 0711.1452 . Código Bibliográfico : 2008PhRvL.101g8701R . doi : 10.1103 / PhysRevLett.101.078701 . PMID 18764586 . S2CID 41197281 .
- ^ a b Decelle, A .; Krzakala, F .; Moore, C .; Zdeborová, L. (2011). "Inferencia y transiciones de fase en la detección de módulos en redes dispersas". Phys. Rev. Lett . 107 (65701): 1–5. arXiv : 1102.1182 . Código Bibliográfico : 2011PhRvL.107f5701D . doi : 10.1103 / PhysRevLett.107.065701 . PMID 21902340 . S2CID 18399723 .
- ^ Nadakuditi, RR; Newman, MEJ (2012). "Graph Spectra y la detectabilidad de la estructura comunitaria en redes". Phys. Rev. Lett . 108 (188701): 1–5. arXiv : 1205.1813 . Código bibliográfico : 2012PhRvL.108r8701N . doi : 10.1103 / PhysRevLett.108.188701 . PMID 22681123 . S2CID 11820036 .
- ^ Shai, S .; Kenett, DY; Kenett, YN; Faust, M .; Dobson, S .; Havlin, S. (2015). "Punto de inflexión crítico que distingue dos tipos de transiciones en estructuras de red modular" . Phys. Rev. E . 92 (6): 062805. Código Bibliográfico : 2015PhRvE..92f2805S . doi : 10.1103 / PhysRevE.92.062805 . PMID 26764742 .
- ^ Dong, Gaogao; Fan, Jingfang; Shekhtman, Louis M; Shai, Saray; Du, Ruijin; Tian, Lixin; Chen, Xiaosong; Stanley, H Eugene; Havlin, Shlomo (2018). "La resiliencia de las redes con estructura comunitaria se comporta como bajo un campo externo" . Actas de la Academia Nacional de Ciencias . 115 (27): 6911–6915. arXiv : 1805.01032 . Código bibliográfico : 2018PNAS..115.6911D . doi : 10.1073 / pnas.1801588115 . PMC 6142202 . PMID 29925594 .
- ^ G Dong, F Wang, LM Shekhtman, MM Danziger, J Fan, R Du, J Liu, L Tian, H Eugene Stanley y Shlomo Havlin (2021). "Resistencia óptima de las redes interactivas modulares". Actas de la Academia Nacional de Ciencias . 118 (22).CS1 maint: varios nombres: lista de autores ( enlace )
- ^ LD Valdez, LA Braunstein, S Havlin (2020). "Epidemia propagación en redes modulares: El miedo a declarar una pandemia". Revisión E física . 101 (3).CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Bnaya Gross, Dana Vaknin, Sergey Buldyrev, Shlomo Havlin (2020). "Dos transiciones en redes espaciales modulares" . Nueva Revista de Física . 22 (5): 053002. doi : 10.1088 / 1367-2630 / ab8263 . S2CID 210966323 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Gross, B .; Havlin, S. (2020). "Estrategias de control y propagación de epidemias en red modular espacial" . Ciencia de redes aplicada . 5 : 1-14. doi : 10.1007 / s41109-020-00337-4 . PMID 33263074 .
enlaces externos
- Detección de comunidades en gráficos : una introducción
- ¿Existen implementaciones de algoritmos para la detección de comunidades en gráficos? - Desbordamiento de pila
- ¿Cuáles son las diferencias entre los algoritmos de detección de comunidades en igraph? - Desbordamiento de pila