Estructura de la comunidad

En el estudio de redes complejas , se dice que una red tiene estructura de comunidad si sus nodos pueden agruparse fácilmente en conjuntos (potencialmente superpuestos) de nodos, de manera que cada conjunto 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 conexiones densas internamente y conexiones más dispersas entre grupos. Sin embargo, también se permiten comunidades superpuestas . La definición más general se basa en el principio de que es más probable que pares de nodos estén conectados si ambos pertenecen a la misma comunidad o comunidades, y menos probable que lo estén si no comparten comunidades. Un problema relacionado, pero diferente, es la búsqueda de comunidades , cuyo objetivo es encontrar una comunidad a la que pertenezca un vértice determinado.

In the study of networks, such as computer and information networks, social networks and biological networks, a number of different characteristics have been found to occur commonly, including the small-world property, heavy-taileddegree distributions, and clustering, among others. Another common characteristic is community structure.^{[1][2][3][4][5]} In the context of networks, community structure refers to the occurrence of groups of nodes in a network that are more densely connected internally than with the rest of the network, as shown in the example image to the right. This inhomogeneity of connections suggests that the network has certain natural divisions within it.

Communities are often defined in terms of the partition of the set of vertices, that is each node is put into one and only one community, just as in the figure. This is a useful simplification and most community detection methods find this type of community structure. However, in some cases a better representation could be one where vertices are in more than one community. This might happen in a social network where each vertex represents a person, and the communities represent the different groups of friends: one community for family, another community for co-workers, one for friends in the same sports club, and so on. The use of cliques for community detection discussed below is just one example of how such overlapping community structure can be found.

Some networks may not have any meaningful community structure. Many basic network models, for example, such as the random graph and the Barabási–Albert model, do not display community structure.

Community structures are quite common in real networks. Social networks include community groups (the origin of the term, in fact) based on common location, interests, occupation, etc.^[5][6]

Finding an underlying community structure in a network, if it exists, is important for a number of reasons. Communities allow us to create a large scale map of a network since individual communities act like meta-nodes in the network which makes its study easier.^[7]

Las comunidades individuales también arrojan luz sobre la función del sistema representado por la red, ya que a menudo corresponden a unidades funcionales del sistema. En las redes metabólicas, estos 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 mutuamente. Esta información puede ser útil para mejorar algunos algoritmos en grafos, 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, centrarse únicamente en las propiedades promedio generalmente deja de lado muchas características importantes e interesantes dentro de las redes. Por ejemplo, en una red social determinada, pueden existir simultáneamente grupos gregarios y retraídos. ^{[ 7 ]}

La existencia de comunidades también influye en diversos procesos, como la propagación de rumores o epidemias en una red. Por lo tanto, para comprender adecuadamente estos procesos, es importante detectar las comunidades y estudiar cómo afectan a la propagación en distintos contextos.

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 observarse por diversas razones. De manera similar, algunos enlaces podrían ingresar erróneamente en los datos debido a errores en la medición. Ambos casos son manejados eficazmente por el algoritmo de detección de comunidades, ya que permite asignar la probabilidad de existencia de una arista entre un par de nodos dado. ^{[ 9 ]}

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 suele ser desconocido y las comunidades a menudo tienen tamaños y/o densidades desiguales. Sin embargo, a pesar de estas dificultades, se han desarrollado y empleado varios métodos para la detección de comunidades con distintos grados de éxito. ^{[ 4 ]}

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 relación y el corte normalizado). Este método se utiliza, por ejemplo, en el balanceo de carga para computación paralela 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 tamaño similar, elegidas de manera que se minimice el número de aristas entre grupos. El método funciona bien en muchas de las aplicaciones para las que fue concebido originalmente, pero no es ideal para encontrar la estructura de comunidades 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 ellas. ^{[ 10 ]}

Otro método para encontrar estructuras comunitarias en redes es el agrupamiento jerárquico . En este método, se define una medida de similitud que cuantifica algún tipo de similitud (generalmente topológica) 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 los nodos similares en comunidades según esta medida. Existen 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 grupos diferentes tienen una similitud menor que un umbral dado, y el agrupamiento de enlace completo , 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 el agrupamiento aglomerativo, lo que indica una estructura comunitaria casi óptima. Una estrategia común consiste en construir una o varias métricas que monitoreen propiedades globales de la red, las cuales alcanzan su máximo en una etapa determinada del agrupamiento. Un enfoque interesante en esta dirección es el uso de varias medidas de similitud o disimilitud, combinadas mediante 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 extiende 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 ]}

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

El algoritmo de Girvan-Newman devuelve resultados de calidad razonable y es popular porque se ha implementado en varios paquetes de software estándar. Sin embargo, también es lento, tardando un 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 ]}

A pesar de sus desventajas conocidas, 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 entre 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 ]}

La utilidad de la optimización de la modularidad es cuestionable, ya que se ha demostrado que a menudo no logra detectar clústeres más pequeños que cierta escala, dependiendo del tamaño de la red ( límite de resolución ^{[ 19 ]} ); por otro lado, el panorama de 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í. ^{[ 20 ]}

Los métodos basados ​​en 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 fundamentada y la capacidad de abordar inherentemente los problemas de significancia estadística . La mayoría de los métodos en la literatura se basan en el modelo de bloques estocásticos ^{[ 21 ],} así como en variantes que incluyen membresía mixta, ^{[ 22 ] [ 23 ]} corrección de grado, ^{[ 24 ]} y estructuras jerárquicas. ^{[ 25 ]} La selección de modelos se puede realizar utilizando enfoques fundamentados como la longitud de descripción mínima ^{[ 26 ] [ 27 ]} (o equivalentemente, selección de modelos bayesianos ^{[ 28 ]} ) y la prueba de razón de verosimilitud . ^{[ 29 ]} Actualmente existen muchos algoritmos para realizar inferencias eficientes de modelos de bloques estocásticos, incluyendo propagación de creencias ^{[ 30 ] [ 31 ]} y Monte Carlo aglomerativo . ^{[ 32 ]}

A diferencia de los enfoques que intentan agrupar una red a partir de una función objetivo, 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 pueden utilizarse para generalizar los datos y predecir la aparición de enlaces faltantes o espurios en la red. ^{[ 33 ] [ 34 ]}

Las camarillas son subgrafos en los que cada nodo está conectado a todos los demás nodos de la camarilla. Dado que los nodos no pueden estar más estrechamente conectados, no sorprende que existan muchos enfoques para la detección de comunidades en redes basados ​​en la detección de camarillas en un grafo y el análisis de cómo se superponen. Cabe destacar que, como un nodo puede pertenecer a más de una camarilla, en estos métodos puede pertenecer a más de una comunidad, lo que da lugar a una " estructura de comunidades superpuestas ".

Un enfoque consiste en encontrar las " camarillas máximas ". Es decir, encontrar las camarillas que no son subgrafos de ninguna otra camarilla. El algoritmo clásico para encontrarlas es el algoritmo de Bron-Kerbosch . La superposición de estas puede utilizarse para definir comunidades de varias maneras. La más sencilla consiste en 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. ^{[ 35 ]} Estos enfoques se implementan a menudo en software de análisis de redes sociales como UCInet.

El enfoque alternativo es usar camarillas de tamaño fijo . La superposición de estas puede usarse para definir un tipo de hipergrafo -regular o una estructura que es una generalización del grafo de línea (el caso cuando ) conocido como " grafo de camarilla ". ^{[ 36 ]} Los grafos de camarilla tienen vértices que representan las camarillas en el grafo original mientras que las aristas del grafo de camarilla registran la superposición de la camarilla en el grafo original. Al aplicar cualquiera de los métodos de detección de comunidades anteriores (que asignan cada nodo a una comunidad) al grafo de camarilla, se asigna cada camarilla a una comunidad. Esto puede usarse para determinar la pertenencia a la comunidad 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 ^{[ 37 ]} define las comunidades como clústeres de percolación de -camarillas . Para hacer esto, encuentra todas las -camarillas en una red, es decir, todos los subgrafos completos de -nodos. Luego, define dos cliques como adyacentes si comparten nodos; esto se utiliza para definir aristas en un grafo de cliques. Una comunidad se define como la unión máxima de cliques en la que se puede alcanzar cualquier clique desde cualquier otro mediante una serie de adyacencias entre cliques. Es decir, las comunidades son simplemente los componentes conectados en el grafo 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}$

Una red puede representarse o proyectarse en un espacio latente mediante métodos de aprendizaje de representación para representar eficientemente un sistema. Posteriormente, se pueden emplear diversos métodos de agrupamiento para detectar estructuras de comunidad. Para espacios euclidianos, se pueden utilizar métodos como la detección de comunidades Silhouette basada en incrustaciones ^{[ 38 ]} . Para espacios latentes hipergeométricos, se puede utilizar el método de brecha crítica o métodos de agrupamiento basados ​​en densidad, jerárquicos o de partición modificados ^{[ 39 ] .}

La evaluación de algoritmos para determinar cuáles son mejores detectando la estructura de la comunidad sigue siendo una cuestión abierta. Debe basarse en análisis de redes con 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 (generalmente 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 grafos de referencia son un caso especial del modelo de l-partición plantada ^{[ 40 ]} 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 estructura de comunidad. Se han propuesto otros conjuntos de datos de referencia más flexibles que permiten tamaños de grupo variables y distribuciones de grado no triviales, como el conjunto de datos de referencia LFR ^{[ 41 ] [ 42 ]} , que es una extensión del conjunto de datos de los cuatro grupos que incluye distribuciones heterogéneas del grado del nodo y el tamaño de la comunidad, lo que lo convierte en una prueba más rigurosa de los métodos de detección de comunidades. ^{[ 43 ] [ 44 ]}

Los benchmarks generados por computadora que se utilizan comúnmente parten de una red de comunidades bien definidas. Luego, esta estructura se degrada mediante la reconfiguración o eliminación de enlaces, lo que dificulta cada vez más que los algoritmos detecten la partición original. Al final, la red alcanza un punto en el que es esencialmente aleatoria. Este tipo de benchmark puede denominarse "abierto". El rendimiento en estos benchmarks se evalúa mediante medidas como la información mutua normalizada o la variación de la información . Estas medidas comparan la solución obtenida por un algoritmo ^{[ 42 ]} con la estructura de la comunidad original, evaluando la similitud de ambas particiones.

En los últimos años, varios grupos han obtenido un resultado bastante sorprendente que demuestra la existencia de una transición de fase en el problema de detección de comunidades. Esta transición muestra que, a medida que la densidad de conexiones dentro de las comunidades y entre ellas se iguala cada vez más, o ambas disminuyen (o, equivalentemente, a medida que la estructura de la comunidad se debilita o la red se dispersa demasiado), las comunidades se vuelven indetectables. En cierto modo, las comunidades siguen existiendo, ya que la presencia o ausencia de aristas aún se correlaciona con la pertenencia a la comunidad de sus extremos; pero, desde el punto de vista de la teoría de la información, resulta imposible etiquetar los nodos mejor que por azar, o incluso distinguir el grafo de uno generado por un modelo nulo como el modelo de Erdos-Renyi sin estructura de comunidad. Esta transición es independiente del tipo de algoritmo utilizado para detectar comunidades, lo que implica que existe un límite fundamental en nuestra capacidad para detectar comunidades en redes, incluso con inferencia bayesiana óptima (es decir, independientemente de nuestros recursos computacionales). ^{[ 45 ] [ 46 ] [ 47 ]}

Consideremos un modelo de bloques estocástico con un total de nodos, grupos de igual tamaño, y sean y las probabilidades de conexión dentro y entre los grupos, respectivamente. Si , la red tendrí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 disperso, y escalan como de modo 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: ^{[ 46 ]}

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

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

• Detección de comunidades en grafos : una introducción
• ¿Existen implementaciones de algoritmos para la detección de comunidades en grafos? – Stack Overflow
• ¿Cuáles son las diferencias entre los algoritmos de detección de comunidades en igraph? – Stack Overflow