método de percolación de clique

El método de percolación de cliques construye las comunidades a partir de k- cliques , que corresponden a subgrafos completos (totalmente conectados) de k nodos. (Por ejemplo, un k -clique en k  =  3 es equivalente a un triángulo). Dos k -cliques se consideran adyacentes si comparten k − 1 nodos. Una comunidad se define como la unión máxima de k -cliques que se pueden alcanzar entre sí a través de una serie de k -cliques adyacentes. Estas comunidades se pueden interpretar mejor con la ayuda de una plantilla de k -clique (un objeto isomorfo a un grafo completo de k nodos). Dicha plantilla se puede colocar sobre cualquier k -clique en el grafo y trasladar a un k -clique adyacente reubicando uno de sus nodos y manteniendo fijos los otros k − 1 nodos. Por lo tanto, las comunidades de k -cliques de una red son todos aquellos subgrafos que se pueden explorar completamente al trasladar una plantilla de k -clique en ellos, pero de los que no se puede salir con esta plantilla.    

Esta definición permite superposiciones entre las comunidades de forma 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 destaca en rojo. La definición anterior también es local: si un subgrafo determinado cumple los criterios para ser considerado una comunidad, seguirá siéndolo independientemente de lo que ocurra en otra parte de la red alejada. En cambio, al buscar las comunidades optimizando con respecto a una cantidad global, un cambio alejado en la red puede remodelar las comunidades también 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 presenta 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 localizar todos los cliques máximos en lugar de los k -cliques individuales. ^{[ 1 ]} Esto inevitablemente requiere encontrar el clique máximo del grafo, que es un problema NP-difícil . (Enfatizamos al lector que encontrar un clique máximo es mucho más difícil que encontrar un único clique máximo). Esto significa que, aunque las redes con unos pocos millones de nodos ya se han analizado con éxito con este enfoque, ^{[ 4 ]} la complejidad de tiempo de ejecución en el peor caso es exponencial en el número de nodos.

• 
  Figura 1. Ilustración de las comunidades de k -cliques en k  =  4.

En una red con enlaces dirigidos, una k -clique dirigida es un subgrafo completo con k nodos que cumple la siguiente condición: los k nodos pueden ordenarse de tal manera que entre cualquier par de ellos exista un enlace dirigido que apunte desde el nodo de mayor rango hacia el nodo de menor rango. El método de percolación de cliques dirigidas define las comunidades de red dirigidas como los clústeres de percolación de k- cliques dirigidas.

En una red con enlaces ponderados, una k -clique ponderada es un subgrafo completo con k nodos tal 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 cliques ponderadas define las comunidades de red ponderadas como los clústeres de percolación de k- cliques ponderadas. Cabe señalar que la media geométrica de los pesos de los enlaces dentro de un subgrafo se denomina intensidad de dicho subgrafo. ^{[ 5 ]}

Los métodos de percolación de cliques pueden generalizarse registrando diferentes grados de solapamiento entre los distintos k -cliques. Esto define un nuevo tipo de grafo, un grafo de cliques ^{[ 6 ]} , donde cada k -clique del grafo original está representado por un vértice en el nuevo grafo de cliques. Las aristas del grafo de cliques se utilizan para registrar la intensidad del solapamiento de los cliques en el grafo original. Posteriormente, se puede aplicar cualquier método de detección de comunidades a este grafo de cliques para identificar los clústeres del grafo original mediante la estructura de k -cliques.

Por ejemplo, en un grafo simple, podemos definir la superposición entre dos k- cliques como el número de vértices comunes a ambos . El método de percolación de cliques es entonces equivalente a aplicar un umbral a este grafo de cliques, descartando todas las aristas con un peso menor que (k-1), y los componentes conectados restantes forman las comunidades de cliques encontradas en CPM. Para k=2, los cliques son las aristas del grafo original y el grafo de cliques en este caso es el grafo de líneas de la red original.

En la práctica, usar el número de vértices comunes como medida de la fuerza de la superposición de cliques puede dar resultados deficientes, ya que los cliques grandes en el grafo original, aquellos con muchos más de k vértices, dominarán el grafo de cliques. El problema surge porque si un vértice está en n k -cliques diferentes , contribuirá a n(n-1)/2 aristas en dicho grafo de cliques. Una solución simple es hacer que cada vértice común a dos k- cliques superpuestos contribuya con un peso igual a 1/n al medir la fuerza de la superposición de los dos k -cliques.

En general, la perspectiva del grafo de cliques es una forma útil de encontrar generalizaciones de los métodos estándar de percolación de cliques para sortear cualquier problema que se presente. Incluso muestra cómo describir extensiones de estos métodos basadas en otros motivos , subgrafos distintos de los k -cliques. En este caso, un grafo de cliques se puede considerar como un ejemplo particular de un hipergrafo .

S. Mainardi et al. diseñaron y desarrollaron una versión paralela del método de percolación de cliques. ^{[ 20 ]} Aprovechando las arquitecturas de computación multinúcleo/multiprocesador actuales, el método permite extraer comunidades de k -cliques de redes muy grandes como Internet. ^{[ 21 ]} Los autores publicaron el código fuente del método bajo la licencia GPL y lo pusieron a disposición de la comunidad de forma gratuita.