El método de percolación de camarillas [1] es un enfoque popular para analizar la estructura comunitaria superpuesta de las redes . El término comunidad de red (también llamado módulo, clúster o grupo cohesivo) no tiene una definición única ampliamente aceptada y generalmente se define como un grupo de nodos que están conectados más densamente entre sí que con otros nodos de la red. Existen numerosos métodos alternativos para detectar comunidades en redes, [2] por ejemplo, el algoritmo de Girvan-Newman , la agrupación jerárquica y la maximización de la modularidad .
El método de percolación de camarillas construye las comunidades a partir de k -camarillas , que corresponden a subgrafos completos (totalmente conectados) de k nodos. (Por ejemplo, una k -camarilla en k = 3 es equivalente a un triángulo). Dos k -camarillas se consideran adyacentes si comparten k − 1 nodos. Una comunidad se define como la unión máxima de k -camarillas a las que se puede llegar entre sí a través de una serie de k -camarillas adyacentes. Dichas comunidades se pueden interpretar mejor con la ayuda de una plantilla de k -camarillas (un objeto isomorfo a un grafo completo de k nodos). Dicha plantilla se puede colocar sobre cualquier k -camarilla en el grafo y rodar a una k -camarilla adyacente reubicando uno de sus nodos y manteniendo fijos sus otros k − 1 nodos. Por lo tanto, las comunidades de k -camarillas de una red son todos aquellos subgrafos que se pueden explorar completamente rodando una plantilla de k -camarillas en ellos, pero que no se pueden abandonar por esta plantilla.
Esta definición permite superposiciones entre las comunidades de una manera natural, como se ilustra en la Fig.1, que muestra cuatro comunidades k -clique en k = 4. Las comunidades están codificadas por colores y la superposición entre ellas se enfatiza en rojo. La definición anterior también es local: si un determinado subgrafo cumple los criterios para ser considerado como una comunidad, entonces seguirá siendo una comunidad independientemente de lo que le suceda a otra parte de la red que esté lejos. Por el contrario, cuando se buscan las comunidades optimizando con respecto a una cantidad global, un cambio que se encuentre lejos en la red también puede remodelar las comunidades en las regiones no perturbadas. Además, se ha demostrado que los métodos globales pueden sufrir un problema de límite de resolución, [3] donde el tamaño de la comunidad más pequeña que se puede extraer depende del tamaño del sistema. Una definición de comunidad local como la que se muestra aquí evita este problema automáticamente.
Dado que incluso las redes pequeñas pueden contener una gran cantidad de k -cliques, la implementación de este enfoque se basa en la localización de todos los cliques máximos en lugar de los k -cliques individuales. [1] Esto requiere inevitablemente encontrar el clique máximo del grafo , que es un problema NP-hard . (Enfatizamos al lector que encontrar un clique máximo es mucho más difícil que encontrar un solo clique máximo). Esto significa que, aunque ya se han analizado redes con unos pocos millones de nodos con éxito con este enfoque, [4] la complejidad del tiempo de ejecución del peor caso es exponencial en el número de nodos.
En una red con enlaces dirigidos, una k -clique dirigida es un subgrafo completo con k nodos que cumplen la siguiente condición. Los k nodos pueden ordenarse de tal manera que entre un par arbitrario de ellos exista un enlace dirigido que apunte desde el nodo con el rango más alto hacia el nodo con el rango más bajo. El método de percolación de cliques dirigidos define las comunidades de redes dirigidas como los clústeres de percolación de k -cliques dirigidos.
En una red con enlaces ponderados, una k -clique ponderada es un subgrafo completo con k nodos de modo que la media geométrica de los k ( k - 1) / 2 pesos de los enlaces dentro de la k -clique es mayor que un valor umbral seleccionado, I . El método de percolación de clique ponderado define las comunidades de red ponderadas como los clústeres de percolación de k -cliques ponderados . Nótese que la media geométrica de los pesos de los enlaces dentro de un subgrafo se denomina intensidad de ese subgrafo. [5]
Los métodos de percolación de camarillas se pueden generalizar registrando diferentes cantidades de superposición entre las diversas k -camarillas. Esto define un nuevo tipo de gráfico, un gráfico de camarillas , [6] donde cada k -camarilla en el gráfico original está representada por un vértice en el nuevo gráfico de camarillas. Los bordes del gráfico de camarillas se utilizan para registrar la fuerza de la superposición de camarillas en el gráfico original. A continuación, se puede aplicar cualquier método de detección de comunidades a este gráfico de camarillas para identificar los grupos en el gráfico original a través de la estructura de k -camarillas.
Por ejemplo, en un gráfico simple, podemos definir la superposición entre dos k -cliques como el número de vértices comunes a ambos k -cliques. El método de percolación de cliques es entonces equivalente a establecer un umbral para este gráfico de cliques, descartando todos los bordes con un peso menor que (k-1), y los componentes conectados restantes forman las comunidades de cliques que se encuentran en CPM. Para k=2 , los cliques son los bordes del gráfico original y el gráfico de cliques en este caso es el gráfico lineal de la red original.
En la práctica, el uso del número de vértices comunes como medida de la fuerza de la superposición de camarillas puede dar malos resultados, ya que las camarillas grandes en el grafo original, aquellas con muchos más de k vértices, dominarán el grafo de camarillas. El problema surge porque si un vértice está en n k -camarillas diferentes , contribuirá a n(n-1)/2 aristas en dicho grafo de camarillas. Una solución simple es permitir que cada vértice común a dos k- camarillas superpuestas contribuya con un peso igual a 1/n al medir la fuerza de la superposición de las dos k -camarillas.
En general, el punto de vista del gráfico de camarillas es una forma útil de encontrar generalizaciones de los métodos estándar de percolación de camarillas para evitar cualquier problema que surja. Incluso muestra cómo describir extensiones de estos métodos en función de otros motivos , subgrafos distintos de k -camarillas. En este caso, lo mejor es pensar en un gráfico de camarillas como un ejemplo particular de un hipergrafo .
El modelo de Erdős–Rényi muestra una serie de transiciones interesantes cuando aumenta la probabilidad p de que dos nodos estén conectados. Para cada k se puede encontrar una cierta probabilidad umbral p c por encima de la cual las k -camarillas se organizan en una comunidad gigante. [7] [8] [9] (El tamaño de la comunidad gigante es comparable al tamaño del sistema, en otras palabras, la comunidad gigante ocupa una parte finita del sistema incluso en el límite termodinámico). Esta transición es análoga a la transición de percolación en física estadística . También se puede observar un fenómeno similar en muchas redes reales: si k es grande, solo las partes más densamente vinculadas se aceptan como comunidades, por lo tanto, generalmente permanecen pequeñas y dispersas. Cuando k se reduce, tanto el número como el tamaño de las comunidades comienzan a crecer. Sin embargo, en la mayoría de los casos se puede alcanzar un valor crítico de k , por debajo del cual surge una comunidad gigante, difuminando los detalles de la estructura de la comunidad al fusionar (y hacer invisibles) muchas comunidades más pequeñas.
El método de percolación de camarillas se ha utilizado para detectar comunidades a partir de los estudios de metástasis del cáncer [10] [11] a través de varias redes sociales [4] [12] [13] [14] [15] para documentar la agrupación [16] y las redes económicas. [17]
Existen varias implementaciones de la percolación de camarillas. El método de percolación de camarillas fue implementado y popularizado por primera vez por CFinder [1] (software gratuito para uso no comercial) para detectar y visualizar comunidades superpuestas en redes. El programa permite una visualización personalizable y permite recorrer fácilmente las comunidades encontradas. El paquete también contiene una versión de línea de comandos del programa, que es adecuada para la creación de scripts.
Otro grupo ha implementado una implementación más rápida (disponible bajo la GPL). [18] Otro ejemplo, que también es muy rápido en ciertos contextos, es el algoritmo SCP. [19]
S. Mainardi et al. diseñaron y desarrollaron una versión paralela del método de percolación de camarillas . [20] Al explotar las arquitecturas informáticas multinúcleo/multiprocesador actuales, el método permite la extracción de comunidades k -camarillas de redes muy grandes como Internet. [21] Los autores publicaron el código fuente del método bajo la GPL y lo pusieron a disposición de la comunidad de forma gratuita.