En el estudio de redes complejas , se dice que una red tiene estructura comunitaria 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 del hallazgo de comunidades no superpuestas , esto implica que la red se divide naturalmente en grupos de nodos con conexiones densas internamente y conexiones más escasas 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 pares de nodos estén conectados si ambos son miembros de la misma(s) comunidad(es), y 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.
En el estudio de redes , como redes informáticas y de información, redes sociales y redes biológicas, se ha descubierto que ocurren comúnmente una serie de características diferentes, incluida la propiedad de mundo pequeño , distribuciones de grados de cola pesada y agrupamiento , entre otras. Otra característica común es la estructura comunitaria. [1] [2] [3] [4] [5] En el contexto de las redes, la estructura comunitaria 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 sólo 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 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 la familia, otra comunidad para los compañeros de trabajo, otra 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 sólo un ejemplo de cómo se puede encontrar una estructura comunitaria superpuesta.
Es posible que algunas redes no tengan ninguna estructura comunitaria significativa. Muchos modelos de redes básicos, por ejemplo, como el gráfico aleatorio y el modelo Barabási-Albert , no muestran una estructura comunitaria.
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 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í. Esta información puede resultar útil para mejorar algunos algoritmos en gráficos, como la agrupación espectral . [8]
Es importante destacar que las comunidades suelen tener propiedades muy diferentes a las propiedades promedio de las redes. Por lo tanto, concentrarse únicamente en las propiedades promedio generalmente pasa por alto 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 afecta generalmente a diversos procesos, como la difusión de rumores o la propagación de epidemias que ocurren en una red. Por lo tanto, para comprender adecuadamente dichos procesos, es importante detectar comunidades y también estudiar cómo afectan 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 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 varios motivos. De igual forma, 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 comunitaria, ya que permite asignar la probabilidad de existencia de un borde entre un par de nodos determinado. [9]
Encontrar comunidades dentro de una red arbitraria puede ser una tarea computacionalmente difícil. Generalmente se desconoce el número de comunidades, si las hay, dentro de la red 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]
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 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 fue diseñado originalmente, pero no es ideal para encontrar estructuras comunitarias 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]
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. Hay varios esquemas comunes para realizar la agrupación, los dos más simples son la agrupación de enlace único , en la que dos grupos se consideran comunidades separadas si y sólo si todos los pares de nodos en diferentes grupos tienen una similitud inferior a un umbral determinado, y la agrupación 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 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 monitoreen 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 mediante sumas convexas . [11] Otra aproximación es el cálculo de una cantidad que monitorea la densidad de los bordes dentro de los grupos con respecto a la densidad entre los grupos, como la densidad de partición, que se ha propuesto cuando la métrica de similitud se define entre los bordes (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 pueden ampliarse para considerar redes multidimensionales, por ejemplo cuando se trata de 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 los bordes de una red que se encuentran entre comunidades y luego los elimina, dejando atrás solo las propias comunidades. La identificación se realiza empleando la medida teórica 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 un tiempo O( m 2 n ) en una red de n vértices ym aristas, lo que lo hace poco práctico para redes de más de unos pocos miles de nodos. [14]
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 buscando en 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 aproximada, 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 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 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 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]
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 importancia estadística . La mayoría de los métodos en la literatura se basan en el modelo de bloques estocásticos [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 la descripción [28] [29] (o de manera equivalente, la selección del modelo bayesiano [30] ) y la prueba de índice de verosimilitud . [31] Actualmente existen muchos algoritmos para realizar 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 sólo 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 faltantes o espurios en la red. [35] [36]
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 sorprendente 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 genera una " estructura comunitaria superpuesta ".
Un enfoque consiste en 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 sencilla es considerar sólo 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 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 lineal (el caso en el que ) se conoce como " gráfico de camarilla ". [38] 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 luego 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 las comunidades como grupos de percolación de camarillas . Para hacer esto, encuentra todas las camarillas en una red, es decir, todos los subgrafos completos de los nodos. Luego define dos camarillas para que sean adyacentes si comparten nodos, es decir, esto se usa para definir bordes en un gráfico de camarillas. Entonces, una comunidad se define como la unión máxima de -cliques en la que podemos llegar a cualquier -clique de 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 camarillas. Dado que un nodo puede pertenecer a varios grupos de percolación de camarillas diferentes al mismo tiempo, las comunidades pueden superponerse entre sí.
Una red se puede representar o proyectar en un espacio latente mediante métodos de aprendizaje de representación para representar eficientemente un sistema. Luego, se pueden emplear varios métodos de agrupación para detectar estructuras comunitarias. Para espacios euclidianos, se pueden utilizar métodos como la detección de comunidad Silhouette basada en incrustación [40] . Para espacios latentes hipergeométricos, se pueden utilizar el método de espacio crítico o métodos de agrupamiento basados en densidad, jerárquicos o basados en particiones modificados. [41]
La evaluación de algoritmos, para detectar cuáles son mejores para detectar la estructura comunitaria, sigue siendo 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 del mismo tamaño (normalmente 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 plantada [42] de Condon y Karp , o más generalmente de " modelos de bloques estocásticos ", una clase general de modelos de redes aleatorias que contienen estructura comunitaria. Se han propuesto otros puntos de referencia más flexibles que permiten variar los tamaños de grupo y distribuciones de grados no triviales, como el punto de referencia LFR [43] [44], 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 comunitarios. [45] [46]
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 a los algoritmos les resulta cada vez más difícil detectar la partición original. Al final, la red llega a un punto en el que es esencialmente aleatoria. 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 [44] con la estructura comunitaria original, evaluando la similitud de ambas particiones.
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 vuelven cada vez más iguales 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 comunidades 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 resulta 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 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 poseería una estructura comunitaria ya que la densidad de vínculos dentro de los grupos sería mayor que la densidad de vínculos entre los grupos. En el caso disperso, escale de manera que el grado promedio sea constante:
Entonces resulta imposible detectar las comunidades cuando: [48]
