Método de Percolación de Cliques
El mundo posee distintos sistema complejos en la naturaleza y la sociedad que pueden llegar a ser representados con éxito en términos de redes de captura, realizando las conexiones entre las diversas unidades que están formados.
Para analizar estos sistemas el método más utilizado es el Método de Percolación de Cliques (CPM)[1] es utilizado para el análisis de la superposición de la estructura comunitaria de las redes. El término comunidad de la red (también llamado grupo de módulos o cluster) se define como un grupo de varios nodos que están relacionados entre sí a otros nodos en la red. Hay numerosos métodos alternativos para la detección de las comunidades en las redes por ejemplo el algoritmo de Giryan-Newman, la agrupación jerárquica, modularidad o maximización.
Método de Percolación de cliques (CPM)
El método de precolación de cliques estudia la superposición[2]de las comunidades, la evaluación de los cambios dentro de una comunidad y cuánto afectan a las regiones de las comunidades situadas lo más lejos de la principal. El método acumula las comunidades de k-cliques (k-cliques es un subconjunto de vértices C & V de tal manera que por cada dos vértices en C, existe un nodo que conecta los dos, por ejemplo un k-clique donde k=3 es equivalente a un triángulo, k=4 es un tetraedro). El método CPM procede a la identificación de todas las comunidades, una comunidad se considera como la unión máxima de todos los k-cliques, que mediante una serie de adyacente k-cliques se pueden llegar desde el uno al otro donde adyacencia se define por el intercambio de k-1 entre dos nodos k-cliques fijos. Las comunidades pueden interpretarse como un k-clique plantilla (un gráfico completo de k-nodos), donde tenemos uno de sus k-nodos que podemos reubicarlo siempre donde queramos y sus adyacentes se mantendrán fijos cumpliendo k-1. Así las comunidades de una red son todos los sub-gráficos que pueden ser totalmente explorados.
Cuando estudiamos cualquier comunidad observamos que entre comunidades hay solapamiento esto es normal.[3] Las comunidades están codificadas por colores y la superposición entre ellas se destaca en rojo. Las comunidades han de cumplir los criterios dichos anteriormente de esta manera entre comunidades no habrá relación de dependencia, lo que implica que cada comunidad será independiente de lo que suceda en la otra parte de la red o comunidad. Por el contrario si nosotros introducimos un cambio nuevo en el sub-gráfico de una comunidad obligamos a cambiar la forma de las comunidades. De esta manera puede sufrir problema de límite de resolución, donde el tamaño de la comunidad más pequeña que se pueda extraer es dependiente del tamaño del sistema modificado.
Este método no se utiliza para encontrar el gran número de k-cliques, sino para encontrar el k-clique máximo de una comunidad. Sería el equivalente a utilizar NP-complete búsqueda del máximo clique (a pesar de que tenemos un polinomio con un número de k-cliques).[4] El tiempo de procesado del método no depende solo de los millones de k-cliques (nodos) analizar sino también depende del tamaño del sistema.
Las generalizaciones del Gráfico Clique
El método de percolación puede ser generalizado mediante diferentes cantidades de solapamiento entre los diversos k-cliques.[5] Contando cada solapamiento entre las diferentes comunidades se puede considerar un nuevo gráfico de k-cliques, donde cada k-clique está representado en el gráfico original por un vértice en el gráfico nuevo. Se puede utilizar cualquier método de detección de comunidad para identificar los clúster en el gráfico original a través de la estructura k-cliques dicha antes.
Por ejemplo en un gráfico simple, podemos definir el solapamiento entre dos k-cliques, el método de prelación de cliques sería el equivalente a colocar un umbral a este gráfico de cliques, dejando todos los nodos (k-1), con el resto de componentes conectados formando las comunidades encontrados en CPM. Por lo tanto para k=2 serían el gráfico original y el gráfico de k-cliques en este caso es un gráfico de líneas de la red original.[6]
Si nos paramos a observar el número de vértices que poseen las diferentes comunidades y los tomamos como una medida de superposición puede dar malos resultados. Aquellas comunidades que posean más número de k vértices dentro del gráfico dominaran dentro del gráfico k-cliques. El problema surge porque si un vértice esta en n diferentes k-cliques que contribuirá a n (n-1)/2 bordes en dicho gráfico de k-cliques. Una solución sencilla es dejar que cada vértice común a la superposición de dos k-cliques ha de contribuir con un peso igual 1/n en la medición de la superposición.
En general, el punto de vista gráfico de k-cliques es una manera útil de encontrar generalizaciones de métodos de percolación estándar de k-cliques y también encontrar algún problema en los diferentes nodos.
Transición de percolación del CPM
En el modelo Edros-Renyi consideramos N nodos de una red cualquiera enlazados aleatoriamente entre sí de dos a dos nodos. Los nodos que se encuentren enlazados se descartan. Si repetimos el proceso M veces eligiendo un par de nodos en cada turno al final habremos establecido como máximo M enlaces entre parejas de nodos. Si M es un valor pequeño con respecto al valor total de nodos muchos estarán desconectados entre sí, mientras que por el contrario otros nodos estarán formando pequeñas comunidades. Por el contrario, si M es grande en comparación con N el número total de nodos, es muy posible que casi todos los nodos estén enlazados entre sí.
El modelo Erdos-Renyi primero calcula la probabilidad pc de que una pareja elegida al azar esté enlazada entre sí. Para ello se calcula el número total de posibles parejas de N nodos, a un número total denominado NP su expresión es: NP=(n 2)= N(N-1)/2
Por lo tanto como el número de parejas enlazadas por el modelo es M, se tiene por lo tanto la expresión analítica de la probabilidad pc como: pc= M/Np= 2M/N(N-1)
Una vez establecido la probabilidad pc, se establece un cierto umbral en el cual los k-cliques se pueden organizarse en una comunidad gigante (el tamaño de la comunidad gigante es comparable con el tamaño del sistema).
Esta transición del modelo es análoga a la transición de percolación, un método similar sería observar muchas redes reales, así si k es grande, solo observaríamos las partes más densamente enlazadas dado que esas son las aceptadas como comunidad, cuando k es baja, tanto el número como el tamaño de las comunidades no son tan densas como antes podríamos hablar de que las comunidades empiezan a crecer. Sin embargo, en la mayoría de los casos, un valor crítico de k, por debajo del cual una comunidad gigante, esta comunidad puede contener muchas comunidades pequeñas.[7]
Método de Percolación de cliques directo (CPMD)
El CPMD es una extensión natural del método de percolación Clique (CPM), en esta extensión los bloques de construcción de una comunidad se definen como sub-grafos completos de tamaño k, donde se pueden pedir los k nodos de tal manera que entre un par de nodos existe un enlace dirigido apuntando desde el nodo con el rango más alto hacia el nodo con el rango más bajo. El CPMD define unas comunidades en red como los clúster de percolación dirigidas k-cliques.
Método de Percolación de cliques ponderado (CPMW)
El CPMW es una extensión natural del método de percolación Clique (CPM), en esta extensión busca los módulos mediante la eliminación de enlaces más débiles que un umbral con valor fijo W, teniendo en cuenta las conexiones restantes sin ponderar. Esta extensión define las comunidades ponderadas de la red como los clúster de percolación de ponderación k-cliques. La media geométrica de los valores de los enlaces dentro de un sub-grafo se denomina intensidad del sub-grafo.
Algoritmos y software
Hay un número de implementaciones de percolación de k-cliques. El CPM fue implementado por primera vez y popularizado por CFinder (software gratuito para uso no comercial) para la detección y visualización de comunidades superpuestas en las redes. El programa permite la visualización personalizable y permite un fácil paseo a través de las comunidades que se encuentran.[8]
Aplicaciones
- Estudio de la metástasis del cáncer
- Redes económicas
- Clúster de documentos
Véase también
Referencias
- Fergal, Reid. «Percolation Computation in Complex Networks» (en inglés). Consultado el 30 de abril de 2012.
- Viale, S.Severo. «Community detection in graphs» (en inglés). Consultado el 25 de enero de 2010.
- Gergely, Palla. «The Critical Point of k-Clique Percolation in the Erdos–Renyi Graph» (en inglés). Consultado el 12 de julio de 1997.
- Gergely, Palla. «k-clique percolation and clustering in directed and weighted networks» (en inglés). Consultado el 12 de marzo de 2008.
- «Posts Tagged ‘clique percolation method’» (en inglés). Consultado el 1 de abril de 2012.
- Polner, Peter. «Centrality properties of directed module members in social networks» (en inglés). Consultado el 1 de junio de 2012.
- M. Kumpula, Jussi. «Sequential algorithm for fast clique percolation» (en inglés). Consultado el 21 de mayo de 2010.
- «CFinder» (en inglés). Consultado el 11 de enero de 2010.