ARS 101: Método de percolación de cliques

Método de percolación de cliques


Wikipedia

El método de percolación de clique [1] es un método popular para analizar la estructura de comunidades superpuestas de redes. El término comunidad de redes (también llamado módulo, clúster o grupo cohesivo) ha sido ampliamente aceptado como definición única y por lo general se define como un grupo de nodos que están más densamente conectada entre sí que a otros nodos de la red. Existen numerosos métodos alternativos para la detección de las comunidades en las redes, [2], por ejemplo, el algoritmo Girvan-Newman, la agrupación jerárquica y la maximización de modularidad.


Evolución temporal de las comunidades superpuestas. La estructura (parte) y la dinámica esquemáticas de la red de co-autoría de ~ 30.000 autores cond-mat y la red de comunicación de más de 4 millones de suscriptores de telefonía. De Palla et. al., Nature 446, 664 (2007).

Definiciones

Clique Percolation Method (CPM)

El método de percolación de cliques acumula las comunidades de k-cliques, que corresponden a un grafo completo (totalmente conectados) de sub-grafos de k nodos. (Por ejemplo, una 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 puede alcanzar una de la otra a través de una serie de k-cliques adyacentes. Tales comunidades pueden interpretarse mejor con la ayuda de una plantilla k-clique (un objeto isomorfo a un grafo completo de nodos k). Una plantilla de este tipo puede ser colocado en cualquier k-clique en el gráfico, y rodó a un k-clique adyacente mediante la reubicación de uno de sus nodos y mantener su otro k - 1 nodos fijos. Por lo tanto, las comunidades k-clique de una red son todas aquellas sub-gráficos que se pueden explorar plenamente haciendo rodar una plantilla-k clique en ellos, pero no pueden ser dejados por esta plantilla.

Esta definición permite solapamientos entre las comunidades de una manera natural, como se ilustra en la Figura 1, que muestra cuatro comunidades k-clique en k = 4. Las comunidades están codificados por color y la superposición entre ellas se destacan en rojo. La definición anterior también es local: si un determinado sub-gráfico cumple los criterios para ser considerado como una comunidad, entonces seguirá siendo una comunidad independiente de lo que sucede a otra parte de la red lejos. Por el contrario, en la búsqueda de las comunidades mediante la optimización con respecto a una cantidad global, un cambio muy lejos, en la red se puede formar de nuevo las comunidades de las regiones perturbadas también. Además, se ha demostrado que los métodos globales pueden sufrir de un problema de límite de resolución, [3], donde el tamaño de la comunidad más pequeña que se puede extraer es dependiente del tamaño del sistema. Una definición de la comunidad local, como aquí evita este problema de forma automática.

Puesto que incluso las redes pequeñas pueden contener un gran número de k-cliques, la aplicación de este enfoque se basa en la localización de las cliques máxima en lugar de los k-cliques individuales. [1] Por lo tanto, la complejidad de este enfoque en la práctica es equivalente a la del hallazgo NP-completo máxima de clique, (a pesar de que la búsqueda de k-cliques es polinómica). Esto significa que aunque las redes con pocos millones de nodos ya se han analizado con éxito con este enfoque, [4] ninguna estimación previa se puede dar para el tiempo de ejecución del algoritmo basado simplemente en el tamaño del sistema.


Fig.1. Ilustración de las comunidades k-clique en k = 4.

Método de percolación de cliques dirigidos (CPMD)

En una red con enlaces dirigidos a k-clique dirigida es un subgrafo completo con nodos k cumplir la siguiente condición. Los nodos k pueden ser ordenados de tal manera que entre un par arbitrario de ellos existe un enlace apuntando dirigida desde el nodo con el rango más alto hacia el nodo con el rango inferior. The Clique Método percolación dirigida define dirigida comunidades en red como los clusters de percolación de k-cliques dirigidos.

Método de percolación de cliques ponderado (CPMw)

En una red con enlaces ponderados una k-clique ponderada es un subgrafo completo con k nodos tales que la media geométrica de la k (k - 1) / 2 de enlace de pesos dentro de la k-clique es mayor que un valor umbral seleccionado, I. The Clique ponderado Método percolación define comunidades red ponderados como los clusters de percolación de k-cliques ponderados. Tenga en cuenta que la media geométrica de los pesos de enlace dentro de un subgrafo se llama la intensidad de ese subgrafo. [5]

Generalizaciones de grafos de clique

Los métodos de percolación de clique pueden generalizarse mediante el registro de diferentes cantidades de solapamiento entre las distintas k-cliques. Esto define entonces un nuevo tipo de gráfico, un grafo clique, [6], donde cada k-clique en el gráfico original se representa por un vértice en el nuevo grafo clique. Los enlaces en el grafo de clique se utilizan para registrar la fuerza de la superposición de cliques en el gráfico original. Entonces, uno puede aplicar cualquier método de detección de la comunidad a este grafo clique para identificar los grupos en la gráfica original a través de la estructura de k-clique.

Por ejemplo, en un gráfico simple, podemos definir la superposición entre dos k-cliques ser el número de vértices comunes a los dos k-cliques. El método de percolación de cliques es entonces equivalente a thresholding este grafo clique, cayendo todos los enlaces de peso menor que (k-1), con los componentes conectados restantes que forman las comunidades de cliques que se encuentran en la RPC. Para k = 2 las cliques son los enlaces del grafo original y la grafo de clique en este caso es el grafo de líneas de la red original.

En la práctica, utilizando el número de vértices comunes como una medida de la fuerza de solapamiento clique puede dar resultados pobres como grandes clique en el gráfico original, los que tienen muchos más de k vértices, dominarán el grafo de clique. El problema surge porque si un vértice está en n diferentes k-cliques que contribuirá a n (n-1) / 2 enlaces en un gráfico como clique. Una solución sencilla es dejar que cada vértice común a dos kcliques superpuestas para contribuir un peso igual a 1 / n en la medición de la fuerza de la superposición de los dos k-cliques.

En general, el punto de vista del grafo clique es una manera útil de encontrar generalizaciones de métodos de percolación de cliques estándar para obtener algún problema redondas encontradas. Incluso muestra cómo describir las extensiones de estos métodos basados en otros motivos, subgrafos distinta k-cliques. En este caso un gráfico clique es mejor pensamiento de un ejemplo particular de un hipergrafo.

Transición de percolación en el CPM

El modelo Erdös-Rényi muestra una serie de transiciones interesantes cuando se aumenta la probabilidad p de dos nodos están conectados. Para cada k uno puede encontrar un cierto pc probabilidad umbral por encima del cual los k-cliques se organizan en una comunidad gigante. [7] [8] (El tamaño de la comunidad gigante es comparable con el tamaño del sistema, en palabras oder 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 la física estadística. Un fenómeno similar se observa en muchas redes reales, así: si k es grande, sólo las partes más densamente vinculados son aceptadas como las comunidades, por lo tanto, por lo general permanecen pequeñas y dispersas. Cuando se baja k, tanto el número como el tamaño de las comunidades comienzan a crecer. Sin embargo, en la mayoría de los casos un valor crítico k puede ser alcanzado, por debajo del cual una comunidad gigante emerge, manchando los detalles de la estructura de la comunidad mediante la fusión (y haciendo invisibles) muchas comunidades más pequeñas.

Aplicaciones

El método de percolación clique había sido utilizada para detectar las comunidades de los estudios de la metástasis del cáncer [9] [10] a través de diversas redes sociales [4] [11] [12] [13] [14] para documentar la agrupación [15] y las redes económicas . [16]

Algoritmos y Software

Hay un número de implementaciones de percolación clique. El método de percolación de clique se implementó y popularizado por CFinder [1] (freeware para uso no comercial) de software para detectar y visualizar comunidades superpuestas en las redes de primera. El programa permite la visualización personalizable y permite un fácil paseo a través de las comunidades que se encuentran. El paquete contiene una versión de línea de comandos del programa, así, que es adecuado para scripting.

Una implementación más rápida (disponible bajo la licencia GPL) ha sido implementado por otro grupo. [17] Otro ejemplo, que también es muy rápido en ciertos contextos, es el algoritmo SCP. [18]

Algoritmos Paralelos

Una versión paralela del método de percolación cliques fue diseñado y desarrollado por S. Mainardi et al .. [19] Mediante la explotación de multi-core / multi-procesador arquitecturas de computación de hoy en día, el método permite la extracción de las comunidades k-cliques de redes muy grandes tales como Internet. [20] los autores lanzaron el código fuente del método bajo la GPL y lo hizo libremente disponible para la comunidad.

Referencias

• Uncovering the overlapping community structure of complex networks in nature and society G. Palla, I. Derényi, I. Farkas, and T. Vicsek: Nature 435, 814–818 (2005)
• Community detection in graphs by S. Fortunato, Physics Reports 486, 75-174 (2010)
• Resolution limit in community detection S. Fortunato and M. Barthelemy: Proc. Natl. Acad. Sci. USA 104 (1), 36–41 (2007)
• Quantifying social group evolution G. Palla, A.-L. Barabási and T. Vicsek: Nature 446, 664–667(2007)
• Intensity and coherence of motifs in weighted complex networks J.-P. Onnela, J. Saramäki, J. Kertész, and K. Kaski: Phys. Rev. E 71, 065103 (2005)
• Clique Graphs and Overlapping Communities T.S. Evans: J. Stat. Mech. P12037 (2010) doi:10.1088/1742-5468/2010/12/P12037
• Clique percolation in random networks I. Derényi, G. Palla, and T. Vicsek: Phys. Rev. Lett. 94, 160202 (2005)
• The critical point of k-clique percolation in the Erdos–Renyi graph G. Palla, I. Derényi, and T. Vicsek: J. Stat. Phys. 128, 219–227 (2007)
• Global topological features of cancer proteins in the human interactome P.F. Jonsson and P.A. Bates: Bioinformatics 22(18):2291–2297 (2006)
• Cluster analysis of networks generated through homology: automatic identification of important protein communities involved in cancer metastasis P.F. Jonsson, T. Cavanna, D. Zicha and P. A. Bates: BMC Bioinformatics 7, 2 (2006)
• A system of mobile agents to model social networks M.C. Gonzalez, P.G. Lind and H.J. Herrmann: Phys. Rev. Lett. 96, 088702 (2006)
• Emergence of communities in weighted networks J.M. Kumpula, J.-P. Onnela, J. Saramaki, K. Kaski and J. Kertész: Phys. Rev. Lett. 99, 228701 (2007)
• A Model for Social Networks R. Toivonen, J.-P. Onnela, J. Saramäki, J. Hyvönen and K. Kaski: Physica A-Statistical Mechanics and its Applications 370, 851–860 (2006)
• Community structure and ethnic preferences in school friendship networks M. C. Gonzalez, H. J. Herrmann, J. Kertesz and T. Vicsek: Physica A-Statistical Mechenics and its Applications 379, 307–316 (2007)
• Natural Document Clustering by Clique Percolation in Random Graphs W. Gao and K.-F. Wong: Lect. Notes in Comp. Sci. 4182, 119–131, (2006)
• Spectral and network methods in the analysis of correlation matrices of stock returns T. Heimo, J. Saramaki, J.-P. Onnela and K. Kaski: Physica A-Statistical Mechenics and its Applications 383, 147–151 (2007)
• Percolation Computation in Complex Networks Fergal Reid, Aaron McDaid, Neil Hurley: ASONAM 2012, (2012)
• Sequential algorithm for fast clique percolation Jussi M. Kumpula, Mikko Kivelä, Kimmo Kaski, and Jari Saramäki: Phys. Rev. E 78, 026109 (2008) (2008)
• Parallel k-Clique Community Detection on Large-Scale Networks Enrico Gregori, Luciano Lenzini and Simone Mainardi: IEEE Transactions on Parallel and Distributed Systems, 31 Aug. 2012.
• k-clique Communities in the Internet AS-level Topology Graph Enrico Gregori, Luciano Lenzini and Chiara Orsini: International Conference on Distributed Computing Systems Workshops (ICDCSW), 2011.