Estructura de la comunidad

Concepto en la teoría de grafos

En el estudio de redes complejas , se dice que una red tiene estructura de comunidad si los nodos de la red se pueden agrupar fácilmente en conjuntos de nodos (potencialmente superpuestos) de modo que cada conjunto de nodos esté densamente conectado internamente. En el caso particular de la búsqueda de comunidades no superpuestas , esto implica que la red se divide naturalmente en grupos de nodos con densas conexiones internas y conexiones más dispersas entre grupos. Pero también se permiten comunidades superpuestas . 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 misma comunidad (o comunidades), 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

Fig. 1: Esbozo de una red pequeña que muestra la estructura de la comunidad , con tres grupos de nodos con conexiones internas densas y conexiones más dispersas entre grupos.

En el estudio de redes , como redes de computadoras y de información, redes sociales y redes biológicas, se ha encontrado que ocurren comúnmente varias características diferentes, incluyendo la propiedad de mundo pequeño , distribuciones de grado de cola pesada y agrupamiento , entre otras. Otra característica común es la estructura de la comunidad. ^{[1] [2] [3] [4] [5]} En el contexto de las redes, la estructura de la comunidad se refiere a la ocurrencia de grupos de nodos en una red que están conectados internamente más densamente 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 suelen definirse 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 de comunidad. Sin embargo, en algunos casos, una mejor representación podría ser una en la que los vértices estén en más de una comunidad. Esto podría suceder en una red social donde cada vértice representa a una persona y las comunidades representan a 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 dicha estructura de comunidad 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 de Barabási-Albert , no muestran una estructura comunitaria.

Importancia

Las estructuras comunitarias son bastante comunes en las redes reales. Las redes sociales incluyen grupos comunitarios (de ahí el origen del término) basados ​​en una ubicación, intereses, ocupación, etc. comunes. ^{[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 metanodos 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 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í. Dicha información puede ser útil para mejorar algunos algoritmos en gráficos como el agrupamiento espectral . ^[8]

Es importante destacar que las comunidades suelen tener propiedades muy diferentes a las propiedades promedio de las redes. Por lo tanto, si nos centramos únicamente en las propiedades promedio, normalmente pasamos por alto muchas características importantes e interesantes dentro de las redes. Por ejemplo, en una red social dada, pueden existir simultáneamente grupos gregarios y reticentes. ^[7]

La existencia de comunidades también afecta a diversos procesos, como la propagación de rumores o epidemias, que se producen en una red. Por lo tanto, para comprender adecuadamente estos procesos, es importante detectar las comunidades y estudiar también cómo afectan a los procesos de propagación en diversos 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 faltantes y la identificación de enlaces falsos en la red. Durante el proceso de medición, algunos enlaces pueden no ser observados por diversas razones. De manera similar, algunos enlaces podrían ingresar falsamente en los datos debido a errores en la medición. Ambos casos son bien manejados por el algoritmo de detección de comunidades ya que permite asignar la probabilidad de existencia de un borde entre un par dado de nodos. ^[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 es generalmente desconocido y las comunidades suelen ser 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 el corte de proporción y el corte normalizado). Este método se utiliza, por ejemplo, en el equilibrio de carga para computación paralela con el fin de minimizar la comunicación entre nodos de procesadores.

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 modo que se minimice el número de aristas entre los grupos. El método funciona bien en muchas de las aplicaciones para las que fue pensado 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 encontrará solo un número fijo de ellas. ^[10]

Agrupamiento jerárquico

Otro método para encontrar estructuras de comunidad en redes es el agrupamiento jerárquico . En este método se define una medida de similitud que cuantifica algún tipo (normalmente topológico) de similitud entre pares de nodos. Las medidas de uso común incluyen la similitud del coseno , el índice de Jaccard y la distancia de Hamming entre filas de la matriz de adyacencia . Luego se agrupan los nodos similares en comunidades según esta medida. Hay varios esquemas comunes para realizar la agrupación, los dos más simples son el agrupamiento de enlace simple , en el que dos grupos se consideran comunidades separadas si y solo si todos los pares de nodos en diferentes grupos tienen una similitud inferior a un umbral dado, y el agrupamiento de enlace completo , en el que todos los nodos dentro de cada grupo tienen una similitud superior a un umbral. Un paso importante es cómo determinar el umbral para detener el agrupamiento aglomerativo, lo que indica una estructura de comunidad cercana a la óptima. Una estrategia común consiste en construir una o varias métricas que monitoreen las propiedades globales de la red, que alcanzan su punto máximo en un paso determinado del agrupamiento. Un enfoque interesante en esta dirección es el uso de varias medidas de similitud o disimilitud, combinadas 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 los clústeres con respecto a la densidad entre clústeres, como la densidad de partición, que se ha propuesto cuando la métrica de similitud se define entre aristas (lo que permite la definición de comunidades superpuestas), ^[12] y se extendió cuando la similitud se define 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 se pueden extender para considerar redes multidimensionales, por ejemplo cuando tratamos con redes que tienen nodos con diferentes tipos de enlaces. ^[13]

Algoritmo de Girvan-Newman

Otro algoritmo de uso común para encontrar comunidades es el algoritmo de Girvan-Newman ^[1] . Este algoritmo identifica los bordes de una red que se encuentran entre comunidades y luego los elimina, dejando solo las comunidades en sí. La identificación se realiza empleando la medida de teoría de grafos centralidad de intermediación , que asigna un número a cada borde que es grande si el borde se encuentra "entre" muchos pares de nodos.

El algoritmo de Girvan-Newman arroja resultados de calidad razonable y es popular porque se ha implementado en varios paquetes de software estándar. Pero también se ejecuta lentamente, tomando tiempo O( m ² n ) en una red de n vértices y m aristas, 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 conocidas desventajas, 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 buscando en las posibles divisiones de una red una o más que tengan una modularidad particularmente alta. Dado que la búsqueda exhaustiva en todas las divisiones posibles suele ser intratable, los algoritmos prácticos se basan en métodos de optimización aproximada, como algoritmos voraces, 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 de Louvain , que optimiza iterativamente las comunidades locales hasta que la modularidad global ya no se puede mejorar dadas las perturbaciones en el estado actual de la comunidad. ^{[17] [18]} Un algoritmo que utiliza el esquema RenEEL, que es un ejemplo del paradigma de aprendizaje de conjuntos extremos (EEL), es actualmente el mejor algoritmo de maximización de la 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 grupos más pequeños que cierta 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 inherentemente cuestiones de significación 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 grado, ^[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 equivalentemente, la selección del modelo bayesiano ^[30] ) y la prueba de razón de verosimilitud . ^[31] Actualmente existen muchos algoritmos para realizar una inferencia eficiente 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 objetivo, esta clase de métodos se basa en modelos generativos, que no solo sirven como una descripción de la estructura a gran escala de la red, sino que también se pueden utilizar para generalizar los datos y predecir la aparición de enlaces faltantes o espurios en la red. ^{[35] [36]}

Métodos basados ​​en camarillas

Los cliques son subgrafos en los que cada nodo está conectado a todos los demás nodos del clique. Como los nodos no pueden estar más estrechamente conectados que esto, no es sorprendente que existan muchos enfoques para la detección de comunidades en redes basados ​​en la detección de cliques en un grafo y el análisis de cómo se superponen. Tenga en cuenta que, como un nodo puede ser miembro de más de un clique, un nodo puede ser miembro de más de una comunidad en estos métodos, lo que da una " estructura de comunidad superpuesta ".

Un enfoque consiste en encontrar los " cliques máximos ", es decir, encontrar los cliques que no son el subgrafo de ningún otro clique. El algoritmo clásico para encontrarlos es el algoritmo de Bron-Kerbosch . La superposición de estos puede utilizarse para definir comunidades de varias maneras. La más sencilla es considerar solo los cliques máximos mayores que un tamaño mínimo (número de nodos). La unión de estos cliques define entonces un subgrafo cuyos componentes (partes desconectadas) definen entonces comunidades. ^[37] Estos enfoques se suelen implementar en software de análisis de redes sociales como UCInet.

El enfoque alternativo es utilizar camarillas de tamaño fijo . La superposición de estas puede utilizarse para definir un tipo de hipergrafo -regular o una estructura que es una generalización del grafo lineal (el caso cuando ) conocido como " grafo de camarilla ". ^[38] Los grafos de camarilla tienen vértices que representan las camarillas en el grafo original mientras que los bordes del grafo de camarilla registran la superposición de la camarilla en el grafo original. La aplicación de cualquiera de los métodos de detección de comunidad anteriores (que asignan cada nodo a una comunidad) al grafo de camarillas asigna entonces cada camarilla a una comunidad. Esto puede utilizarse entonces para determinar la pertenencia comunitaria de los nodos en 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 las comunidades como cúmulos de percolación de -camarillas . Para ello, encuentra todas las -camarillas en una red, es decir, todos los subgrafos completos de -nodos. Luego, define dos -cliques como adyacentes si comparten nodos, es decir, esto se utiliza para definir bordes en un gráfico de cliques. Luego, una comunidad se define como la unión máxima de -cliques en la que podemos llegar a cualquier -clique desde cualquier otro -clique a través de una serie de adyacencias de -cliques. Es decir, las comunidades son solo los componentes conectados en el gráfico de cliques. Dado que un nodo puede pertenecer a varios clústeres de percolación de -cliques diferentes al mismo tiempo, las comunidades pueden superponerse entre sí. ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k=2}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k-1}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Detección de comunidades en espacios de características latentes

Una red se puede representar o proyectar en un espacio latente mediante métodos de aprendizaje de representación para representar un sistema de manera eficiente. Luego, se pueden emplear varios métodos de agrupamiento para detectar estructuras de comunidad. Para espacios euclidianos, se pueden utilizar métodos como la detección de comunidad Silhouette basada en incrustaciones ^[40] . Para espacios latentes hipergeométricos, se pueden utilizar métodos de agrupamiento basados ​​en densidad modificada, jerárquicos o basados ​​en particiones. ^[41]

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 una comunidad es todavía una cuestión abierta. Debe basarse en análisis de redes de estructura conocida. Un ejemplo típico es la prueba de los "cuatro grupos", en la que una red se divide en cuatro grupos de igual tamaño (normalmente de 32 nodos cada uno) y se varían las probabilidades de conexión dentro y entre grupos para crear estructuras más o menos desafiantes para el algoritmo de detección. Estos gráficos de referencia son un caso especial del modelo de partición l plantada ^[42] de Condon y Karp , o más generalmente de los " modelos de bloques estocásticos ", una clase general de modelos de redes aleatorias que contienen la estructura de la comunidad. Se han propuesto otros puntos de referencia más flexibles que permiten tamaños de grupo variables y distribuciones de grado no triviales, como el punto de referencia LFR ^{[43] [44],} que es una extensión del punto de referencia de los cuatro grupos que incluye distribuciones heterogéneas de grado de nodo y tamaño de la comunidad, lo que lo convierte en una prueba más severa de los métodos de detección de la comunidad. ^{[45] [46]}

Los benchmarks generados por ordenador que se utilizan habitualmente comienzan con una red de comunidades bien definidas. A continuación, esta estructura se degrada recableando o eliminando enlaces y se hace cada vez 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 aleatoria. Este tipo de benchmark puede denominarse "abierto". El rendimiento de estos benchmarks 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 ^[44] con la estructura de la comunidad original, evaluando la similitud de ambas particiones.

Detectabilidad

En los últimos años, varios grupos han obtenido un resultado bastante sorprendente que muestra que existe una transición de fase 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 vuelven más pequeñas (equivalentemente, a medida que la estructura de la comunidad se vuelve demasiado débil o la red se vuelve demasiado dispersa), de repente las comunidades se vuelven indetectables. En cierto sentido, las comunidades en sí mismas todavía existen, ya que la presencia y ausencia de bordes todavía está correlacionada con las membresías comunitarias de sus puntos finales; pero se vuelve imposible, en teoría de la información, 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 de comunidad. 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 redes, incluso con una inferencia bayesiana óptima (es decir, independientemente de nuestros recursos computacionales). ^{[47] [48] [49]}

Considere un modelo de bloques estocástico con nodos totales, grupos de igual tamaño y sean y las probabilidades de conexión dentro y entre los grupos respectivamente. Si , la red tendría 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 disperso, y escala de manera que el grado promedio sea constante: ${\displaystyle n}$ ${\displaystyle q=2}$ ${\displaystyle p_{\text{in}}}$ ${\displaystyle p_{\text{out}}}$ ${\displaystyle p_{\text{in}}>p_{\text{out}}}$ ${\displaystyle p_{\text{in}}}$ ${\displaystyle p_{\text{out}}}$ ${\displaystyle O(1/n)}$

${\displaystyle p_{\text{in}}=c_{\text{in}}/n}$y ${\displaystyle p_{\text{out}}=c_{\text{out}}/n}$

Entonces resulta imposible detectar las comunidades cuando: ^[48]

${\displaystyle c_{\text{in}}-c_{\text{out}}={\sqrt {2(c_{\text{in}}+c_{\text{out}})}}}$

Véase también

• Red compleja
• Jerarquía
• Teoría de redes
• Teoría de la percolación

Referencias

1. M. Girvan ; MEJ Newman (2002). "Estructura comunitaria en redes sociales y biológicas". Proc. Natl. Sci. USA . 99 (12): 7821–7826. arXiv : cond-mat/0112110 . Bibcode :2002PNAS...99.7821G. doi : 10.1073/pnas.122653799 . PMC 122977 . PMID  12060727. 
2. S. Fortunato (2010). "Detección de comunidades en grafos". 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.
3. FD Malliaros; M. Vazirgiannis (2013). "Agrupamiento y detección de comunidades en redes dirigidas: un estudio". 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.
4. MA Porter; J.-P. Onnela; PJ Mucha (2009). "Comunidades en redes" (PDF) . Avisos de la American Mathematical Society . 56 : 1082–1097, 1164–1166. Archivado (PDF) desde el original el 13 de junio de 2021. Consultado el 28 de abril de 2021 .
5. Fani, Hossein; Bagheri, Ebrahim (2017). "Detección de comunidades en redes sociales". Enciclopedia con Computación Semántica e Inteligencia Robótica . Vol. 1. págs. 1630001 [8]. doi :10.1142/S2425038416300019. S2CID  52471002.
6. Hamdaqa, Mohammad; Tahvildari, Ladan; LaChapelle, Neil; Campbell, Brian (2014). "Detección de escenas culturales mediante optimización inversa de Louvain". Science of Computer Programming . 95 : 44–72. doi : 10.1016/j.scico.2014.01.006 . Archivado desde el original el 2020-08-07 . Consultado el 2019-08-29 .
7. MEJNeman (2006). "Encontrar la estructura de la comunidad en redes usando los vectores propios de matrices". Phys. Rev. E . 74 (3): 1–19. arXiv : physics/0605087 . Bibcode :2006PhRvE..74c6104N. doi :10.1103/PhysRevE.74.036104. PMID  17025705. S2CID  138996.
8. Zare, Habil; P. Shooshtari; A. Gupta; R. Brinkman (2010). "Reducción de datos para agrupamiento espectral para analizar datos de citometría de flujo de alto rendimiento". BMC Bioinformatics . 11 (1): 403. doi : 10.1186/1471-2105-11-403 . PMC 2923634 . PMID  20667133. 
9. Aaron Clauset; Cristopher Moore; MEJ Newman (2008). "Estructura jerárquica y predicción de enlaces faltantes en redes". Nature . 453 (7191): 98–101. arXiv : 0811.0484 . Bibcode :2008Natur.453...98C. doi :10.1038/nature06830. PMID  18451861. S2CID  278058.
10. MEJ Newman (2004). "Detección de la estructura de la comunidad en redes". Eur. Phys. J. B . 38 (2): 321–330. Bibcode :2004EPJB...38..321N. doi :10.1140/epjb/e2004-00124-y. hdl : 2027.42/43867 . S2CID  15412738.
11. Alvarez, Alejandro J.; Sanz-Rodríguez, Carlos E.; Cabrera, Juan Luis (13 de diciembre de 2015). "Ponderación de disimilitudes para detectar comunidades en redes". Phil. Trans. R. Soc. A. 373 ( 2056): 20150108. Bibcode :2015RSPTA.37350108A. doi : 10.1098/rsta.2015.0108 . ISSN  1364-503X. PMID  26527808.
12. Ahn, Y.-Y.; Bagrow, JP; Lehmann, S. (2010). "Las comunidades de enlaces revelan complejidad multiescala en redes". Nature . 466 (7307): 761–764. arXiv : 0903.3178 . Bibcode :2010Natur.466..761A. doi :10.1038/nature09182. PMID  20562860. S2CID  4404822.
13. 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. S2CID  214033410.
14. MEJ Newman (2004). "Algoritmo rápido para detectar la estructura de la comunidad en redes". Phys. Rev. E . 69 (6): 066133. arXiv : cond-mat/0309508 . Bibcode :2004PhRvE..69f6133N. doi :10.1103/PhysRevE.69.066133. PMID  15244693. S2CID  301750.
15. L. Danón; J. Duch; A. Díaz-Guilera; A. Arenas (2005). "Comparación de la identificación de la estructura comunitaria". J. estadística. Mec . 2005 (9): P09008. arXiv : cond-mat/0505245 . Código Bib : 2005JSMTE..09..008D. doi :10.1088/1742-5468/2005/09/P09008. S2CID  14798969.
16. R. Guimera; LAN Amaral (2005). "Cartografía funcional de redes metabólicas complejas". Nature . 433 (7028): 895–900. arXiv : q-bio/0502035 . Bibcode :2005Natur.433..895G. doi :10.1038/nature03288. PMC 2175124 . PMID  15729348. 
17. 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.
18. "Detección de comunidades ultrarrápida en las redes sociales: una implementación escalable del algoritmo de Louvain" (PDF) . Universidad de Auburn . 2013. S2CID  16164925.^{[ enlace muerto ]}
19. J. Guo; P. Singh; KE Bassler (2019). "Esquema de aprendizaje de conjunto extremo de red reducida (RenEEL) para la detección de comunidades en redes complejas". Scientific Reports . 9 (14234): 14234. arXiv : 1909.10491 . Bibcode :2019NatSR...914234G. doi : 10.1038/s41598-019-50739-3 . PMC 6775136 . PMID  31578406. 
20. "RenEEL-Modularity". GitHub . 31 de octubre de 2019. Archivado desde el original el 1 de enero de 2021 . Consultado el 4 de noviembre de 2019 .
21. 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 : physics/0607100 . Bibcode :2007PNAS..104...36F. doi : 10.1073/pnas.0605965104 . PMC 1765466 . PMID  17190818. 
22. BH Good; 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.
23. Holland, 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. S2CID  34098453.
24. Airoldi, Edoardo M. ; David M. Blei; Stephen E. Fienberg; Eric P. Xing (junio de 2008). "Mixed Membership Stochastic Blockmodels". J. Mach. Learn. Res . 9 : 1981–2014. ISSN  1532-4435. PMC 3119541. PMID 21701698.  Archivado desde el original el 21 de noviembre de 2018. Consultado el 9 de octubre de 2013 . 
25. Ball, Brian; Brian Karrer; MEJ Newman (2011). "Método eficiente y basado en principios para detectar comunidades en redes". Physical Review E . 84 (3): 036103. arXiv : 1104.3590 . Bibcode :2011PhRvE..84c6103B. doi :10.1103/PhysRevE.84.036103. PMID  22060452. S2CID  14204351.
26. Karrer, Brian; MEJ Newman (21 de enero de 2011). "Modelos de bloques estocásticos y estructura de comunidad en redes". Physical Review E . 83 (1): 016107. arXiv : 1008.3926 . Código Bibliográfico :2011PhRvE..83a6107K. doi :10.1103/PhysRevE.83.016107. PMID  21405744. S2CID  9068097.
27. Peixoto, Tiago P. (24 de marzo de 2014). "Estructuras de bloques jerárquicas y selección de modelos de alta resolución en redes grandes". Physical Review X . 4 (1): 011047. arXiv : 1310.4377 . Código Bibliográfico :2014PhRvX...4a1047P. doi :10.1103/PhysRevX.4.011047. S2CID  5841379.
28. 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 : physics/0612035 . Bibcode :2007PNAS..104.7327R. doi : 10.1073/pnas.0611034104 . PMC 1855072 . PMID  17452639. 
29. P. Peixoto, T. (2013). "Inferencia modular parsimoniosa en redes grandes". 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.
30. P. Peixoto, T. (2019). "Modelado de bloques estocástico bayesiano". Avances en agrupamiento de redes y modelado de bloques . pp. 289–332. arXiv : 1705.10225 . doi :10.1002/9781119483298.ch11. ISBN. 978-1-119-22470-9. Número de identificación del sujeto  62900189.
31. 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". Journal of Statistical Mechanics: Theory and Experiment . 2014 (5): P05007. arXiv : 1207.3994 . Bibcode :2014JSMTE..05..007Y. doi :10.1088/1742-5468/2014/05/P05007. PMC 4498413 . PMID  26167197. 
32. 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. Bibcode :2013PNAS..11014534G. doi : 10.1073/pnas.1221839110 . ISSN  0027-8424. PMC 3767539 . PMID  23950224. 
33. 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". Physical Review E . 84 (6): 066106. arXiv : 1109.3041 . Bibcode :2011PhRvE..84f6106D. doi :10.1103/PhysRevE.84.066106. PMID  22304154. S2CID  15788070.
34. Peixoto, Tiago P. (13 de enero de 2014). "Monte Carlo eficiente y heurística voraz para la inferencia de modelos de bloques estocásticos". Physical Review E . 89 (1): 012804. arXiv : 1310.4378 . Bibcode :2014PhRvE..89a2804P. doi :10.1103/PhysRevE.89.012804. PMID  24580278. S2CID  2674083.
35. Guimerà, Roger; Marta Sales-Pardo (2009-12-29). "Interacciones faltantes y espurias y la 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. 
36. Clauset, Aaron; Cristopher Moore; MEJ Newman (1 de mayo de 2008). "Estructura jerárquica y predicción de enlaces faltantes en redes". Nature . 453 (7191): 98–101. arXiv : 0811.0484 . Código Bibliográfico :2008Natur.453...98C. doi :10.1038/nature06830. ISSN  0028-0836. PMID  18451861. S2CID  278058.
37. MG Everett; SP Borgatti (1998). "Análisis de las conexiones superpuestas entre camarillas". Connections . 21 : 49.
38. 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.
39. G. Palla; I. Derényi; I. Farkas; T. Vicsek (2005). "Descubrimiento de la estructura comunitaria superpuesta de redes complejas en la naturaleza y la sociedad". Nature . 435 (7043): 814–818. arXiv : physics/0506133 . Bibcode :2005Natur.435..814P. doi :10.1038/nature03607. PMID  15944704. S2CID  3250746.
40. Škrlj, Blaž; Kralj, enero; Lavrač, Nada (1 de noviembre de 2020). "Detección de comunidad Silhouette basada en incrustación". Aprendizaje automático . 109 (11): 2161–2193. doi :10.1007/s10994-020-05882-8. ISSN  1573-0565. PMC 7652809 . PMID  33191975. 
41. Bruno, Matteo (21 de junio de 2019). "Detección de comunidades en el espacio hiperbólico". arXiv : 1906.09082 [physics.soc-ph].
42. Condon, A. ; Karp, RM (2001). "Algoritmos para la partición de grafos en el modelo de partición plantada". Random Struct. 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. 
43. 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 . Bibcode :2008PhRvE..78d6110L. doi :10.1103/PhysRevE.78.046110. PMID  18999496. S2CID  18481617.
44. Fathi, Reza (abril de 2019). "Detección eficiente de comunidades distribuidas en el modelo de bloques estocásticos". arXiv : 1904.07494 [cs.DC].
45. MQ Pasta; F. Zaidi (2017). "Aprovechamiento de la dinámica de la evolución para generar redes complejas de referencia con estructuras comunitarias". arXiv : 1606.01169 [cs.SI].
46. Pasta, MQ; Zaidi, F. (2017). "Topología de redes complejas y limitaciones de rendimiento de algoritmos de detección de comunidades". IEEE Access . 5 : 10901–10914. doi : 10.1109/ACCESS.2017.2714018 .
47. Reichardt, J.; Leone, M. (2008). "Estructura de clúster (in)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.
48. 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.
49. Nadakuditi, RR; Newman, MEJ (2012). "Espectros de grafos y detectabilidad de la estructura de la comunidad 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.

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? – Stack Overflow
• ¿Cuáles son las diferencias entre los algoritmos de detección de comunidades en igraph? – Stack Overflow