Estructura de comunidades

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 encontrar comunidades que no se superpongan, esto implica que la red se divide naturalmente en grupos de nodos con conexiones densas internamente y conexiones más dispersas entre grupos. pero superpuestosLas comunidades también están permitidas. 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(s) comunidad(es) 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 pertenezca cierto 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 varias características diferentes, incluida la propiedad de mundo pequeño, las distribuciones de grado de cola pesada y la agrupación, entre otras. Otra característica común es la estructura comunitaria. 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 las 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 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 donde 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 los diferentes grupos de amigos: una comunidad para familiares, otra comunidad para compañeros de trabajo, una para amigos en el 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 una estructura comunitaria superpuesta.

Algunas redes pueden no tener ninguna estructura comunitaria significativa. Muchos modelos básicos de red, 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.

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.

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. 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í. Tal información puede ser útil para mejorar algunos algoritmos en gráficos como el agrupamiento espectral.

Es importante destacar que las comunidades a menudo tienen propiedades muy diferentes a las propiedades promedio de las redes. Por lo tanto, al concentrarse únicamente en las propiedades promedio, generalmente se pierden muchas características importantes e interesantes dentro de las redes. Por ejemplo, en una determinada red social, tanto los grupos sociables como los reticentes pueden existir simultáneamente.

La existencia de comunidades generalmente también afecta 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 tales 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 ha encontrado la detección comunitaria 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, 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 son 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.

Algoritmos para encontrar comunidades

Encontrar comunidades dentro de una red arbitraria puede ser una tarea computacionalmente difícil. Por lo general, se desconoce el número de comunidades, si las hay, dentro de la red y las comunidades suelen tener un 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 diferentes niveles de éxito.

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 proporción y corte normalizado). Este método se utiliza, por ejemplo, en el equilibrio de carga para la 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 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.

Agrupación jerárquica

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 (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 uno agrupa nodos similares en comunidades de acuerdo con esta medida. Hay varios esquemas comunes para realizar el agrupamiento, los dos más simples son el agrupamiento de enlace único, 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 determinado, 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 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 controlen las propiedades globales de la red, que alcanzan su punto máximo en un paso determinado de la agrupación. Un enfoque interesante en esta dirección es el uso de varias medidas de similitud o disimilitud, combinadas a través de sumas convexas,. Otra aproximación es el cálculo de una cantidad que monitorea la densidad de los bordes dentro de los clústeres con respecto a la densidad entre los clústeres, como la densidad de partición, que se ha propuesto cuando se define la métrica de similitud entre los bordes (lo que permite la definición de comunidades superpuestas), y extendida 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í). Estos métodos pueden extenderse para considerar redes multidimensionales, por ejemplo, cuando se trata de redes que tienen nodos con diferentes tipos de enlaces.

Algoritmo de Girvan-Newman

Otro algoritmo de uso común para encontrar comunidades es el algoritmo de Girvan-Newman. Este algoritmo identifica los bordes en una red que se encuentran entre las comunidades y luego los elimina, dejando solo las comunidades mismas. La identificación se realiza empleando la centralidad de intermediación de la medida teórica de gráficos, 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 funciona lentamente, tardando 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.

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. 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 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. 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 se puede mejorar debido a las perturbaciones en el estado actual de la comunidad. Un algoritmo que utiliza el esquema RenEEL, que es un ejemplo del paradigma Extremal Ensemble Learning (EEL), es actualmente el mejor algoritmo que maximiza la modularidad.

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, según el tamaño de la red (límite de resolución); por otro lado, el panorama de los valores de modularidad se caracteriza por una gran degeneración de particiones con una alta modularidad, cercana al máximo absoluto, que pueden ser muy diferentes entre sí.

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 inherente de abordar cuestiones de importancia estadística. La mayoría de los métodos en la literatura se basan en el modelo de bloques estocásticos, así como en variantes que incluyen membresía mixta, corrección de grado y estructuras jerárquicas. La selección del modelo se puede realizar utilizando enfoques basados ​​en principios, como la longitud mínima de la descripción (o, de manera equivalente, la selección del modelo bayesiano) y la prueba de la razón de verosimilitud. Actualmente existen muchos algoritmos para realizar una inferencia eficiente de modelos de bloques estocásticos, incluida la propagación de creencias y Monte Carlo aglomerativo.

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 pueden usarse para generalizar la datos y predecir la aparición de enlaces perdidos o espurios en la red.

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 sorprende que haya muchos enfoques para la detección de comunidades en redes basados ​​en la detección de clicas 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 dando 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 maneras. La más simple es considerar solo 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. Dichos enfoques a menudo se implementan 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 hipergráfico regular o una estructura que es una generalización del gráfico de líneas (el caso cuando ) conocido como " gráfico Clique ". Los gráficos de camarilla tienen vértices que representan las camarillas en el gráfico original, mientras que los bordes del gráfico de camarilla registran la superposición de la camarilla en el gráfico original. Al aplicar cualquiera de los métodos de detección de comunidades anteriores (que asignan cada nodo a una comunidad) al gráfico de camarilla, se asigna cada camarilla a una comunidad. Esto se puede usar 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 define las comunidades como grupos de percolación de -camarillas. Para hacer esto, encuentra todas las camarillas en una red, es decir, todos los subgráficos completos de los nodos. Luego define dos camarillas para que sean adyacentes si compartennodos, es decir, esto se usa para definir bordes en un gráfico de clique. Una comunidad se define entonces 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 -clique. Es decir, las comunidades son solo los componentes conectados en el gráfico de camarilla. Dado que un nodo puede pertenecer a varios grupos de percolación de camarillas diferentes 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 pregunta 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 del mismo tamaño (generalmente de 32 nodos cada uno) y las probabilidades de conexión dentro y entre los grupos varían para crear estructuras más o menos desafiantes para la detección. algoritmo. Dichos gráficos de referencia son un caso especial del modelo de partición L plantado 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 grupos y distribuciones de grados no triviales, como el punto de referencia LFR 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.

Los puntos de referencia generados por computadora comúnmente utilizados comienzan con una red de comunidades bien definidas. Luego, esta estructura se degrada al volver a cablear o eliminar enlaces y se vuelve 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 llamarse "abierto". El rendimiento de 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 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 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 escasa), de repente las comunidades se vuelven indetectables. En cierto sentido, las propias comunidades siguen existiendo, ya que la presencia y ausencia de bordes sigue estando correlacionada con la pertenencia a la comunidad de sus puntos finales; pero se convierte en información, 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 de comunidad.

Considere un modelo de bloque estocástico con nodos totales, grupos de igual tamaño y sean y sean 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 escalar de modo que el grado medio sea constante:y

Entonces se vuelve imposible detectar las comunidades cuando: