Método d'Percolación de Cliques

El món posseïx distints sistemes complexos en la naturalea i la societat que poden aplegar a ser representats en èxit en térmens de rets de captura, realisant les conexions entre les diverses unitats que estan formats.

Per a analisar estos sistemes el método més utilisat és el Método d'Percolación de Cliques (CPM) és utilisat per a l'anàlisis de la superposició de l'estructura comunitària de les rets. El terme comunitat de la ret (també cridat grup de mòduls o clúster) es definix com un grup de varis nodos que estan relacionats entre sí a atres nodos en la ret. Hi ha numerosos métodos alternatius per a la detecció de les comunitats en les rets per eixemple l'algoritme de Giryan-Newman, l'agrupació jeràrquica, modularidad o maximización.

Método d'Percolación de cliques (CPM)

El método de precolación de cliques estudia la superposició de les comunitats, l'evaluació dels canvis dins d'una comunitat i quànt afecten a les regions de les comunitats situades lo més llunt de la principal. El método acumula les comunitats de k-cliques (k-cliques és un subconjunt de vèrtiços C & V de tal manera que per cada dos vèrtiços en C, existix un nodo que conecta els dos, per eixemple un k-clique a on k=3 és equivalent a un triàngul, k=4 és un tetraedre). El método CPM procedix a l'identificació de totes les comunitats, una comunitat es considera com l'unió màxima de tots els k-cliques, que per mig d'una série d'adjacent k-cliques es poden aplegar des de l'u a l'un atre a on adyacencia es definix per l'intercanvi de k-1 entre dos nodos k-cliques fixos. Les comunitats poden interpretar-se com un k-clique plantilla (un gràfic complet de k-nodos), a on tenim un de les seues k-nodos que podem reubicar-ho sempre a on vullgam i els seus adjacents es mantindran fixos complint k-1. Aixina les comunitats d'una ret són tots els subgráficos que poden ser totalment explorats.

Quan estudiem qualsevol comunitat observem que entre comunitats hi ha solapamiento açò és normal. Les comunitats estan codificades per colors i la superposició entre elles es destaca en roig. Les comunitats han de complir els criteris dits anteriorment d'esta manera entre comunitats no hi haurà relació de dependència, lo que implica que cada comunitat serà independent de lo que succeïxca en l'atra part de la ret o comunitat. Pel contrari, si nosatres introduïm un canvi nou en el subgráfico d'una comunitat obliguem a canviar la forma de les comunitats. D'esta manera pot sofrir problema de llímit de resolució, a on el tamany de la comunitat més chicoteta que es puga extraure és depenent del tamany del sistema modificat.

Este método no s'utilisa per a trobar el gran número de k-cliques, sino per a trobar el k-clique màxim d'una comunitat. Seria l'equivalent a utilisar NP-complete busca del màxim clique (a pesar de que tenim un polinomi en un número de k-cliques). El temps de processat del método no depén solament dels millons de k-cliques (nodos) analisar sino també depén del tamany del sistema.

Les generalisacions del Grafo Clique

El método d'percolación pot ser generalisat per mig de diferents cantitats de solapamiento entre els diversos k-cliques. Contant cada solapamiento entre les diferents comunitats es pot considerar un nou gràfic de k-cliques, a on cada k-clique està representat en el gràfic original per un vèrtiç en el gràfic nou. Es pot utilisar qualsevol método de detecció de comunitat per a identificar els clústers en el gràfic original a través de l'estructura k-cliques dita abans.

Per eixemple en un gràfic simple, podem definir el solapamiento entre dos k-cliques, el método de prelació de cliques seria l'equivalent a colocar un llindar a este gràfic de cliques, deixant tots els nodos (k-1), en el restant de components conectats formant les comunitats trobats en CPM. Per lo tant per a k=2 serien el gràfic original i el gràfic de k-cliques en este cas és un gràfic de llínees de la ret original.

Si nos parem a observar el número de vèrtiços que posseïxen les diferents comunitats i els prenem com una mida de superposició pot donar mals resultats. Aquelles comunitats que posseïxquen més número de k vèrtiços dins del gràfic dominaren dins del gràfic k-cliques. El problema sorgix perque si un vèrtiç està en n diferents k-cliques que contribuirà a n (n-1)/2 vores en dit gràfic de k-cliques. Una solució senzilla és deixar que cada vèrtiç comú a la superposició de dos k-cliques ha de contribuir en un pes igual 1/n en la medició de la superposició.

En general, el punt de vista gràfic de k-cliques és una manera útil de trobar generalisacions de métodos d'percolación estàndar de k-cliques i també trobar algun problema en els diferents nodos.

Transició d'percolación de el CPM

En el model Edros-Renyi considerem N nodos d'una ret qualsevol enllaçats aleatoriamente entre sí de dos a dos nodos. Els nodos que es troben enllaçats es descarten. Si repetim el procés M voltes elegint un parell de nodos en cada tanda al final haurem establit com a màxim M enllaços entre parelles de nodos. Si M és un valor chicotet sobre el valor total de nodos molts estaran desconectats entre sí, mentres que, pel contrari, atres nodos estaran formant chicotetes comunitats. Pel contrari, si M és gran en comparació a N el número total de nodos, és molt possible que casi tots els nodos estiguen enllaçats entre sí.

El model Erdos-Renyi primer calcula la provabilitat pc de que una parella elegida a l'encert estiga enllaçada entre sí. Per a això es calcula el número total de possibles parelles de N nodos, a un número total denominat NP la seua expressió és: NP=(n 2)= N(N-1)/2

Per lo tant com el número de parelles enllaçades pel model és M, es té, per lo tant, l'expressió analítica de la provabilitat pc com: pc= M/Np= 2M/N(N-1)

Una volta establit la provabilitat pc, s'establix un cert llindar en el qual els k-cliques es poden organisar-se en una comunitat jaganta (el tamany de la comunitat jaganta és comparable en el tamany del sistema).

Esta transició del model és anàloga a la transició d'percolación, un método similar seria observar moltes rets reals, aixina si k és gran, solament observaríem les parts més densament enllaçades ya que eixes són les acceptades com a comunitat, quan k és baixa, tant el número com el tamany de les comunitats no són tan denses com abans podríem parlar de que les comunitats escomencen a créixer. No obstant, en la majoria dels casos, un valor crític de k, per baix del com una comunitat jaganta, esta comunitat pot contindre moltes comunitats menudes.

Método d'Percolación de cliques directe (CPMD)

El CPMD és una extensió natural del método d'percolación Clique (CPM), en esta extensió els blocs de construcció d'una comunitat es definixen com subgrafos complets de tamany k, a on es poden demanar els k nodos de tal manera que entre un parell de nodos existix un enllaç dirigit apuntant des del nodo en el ranc més alt cap al nodo en el ranc més baix. El CPMD definix unes comunitats en ret com els clústers d'percolación dirigides k-cliques.

Vore també

• Model Erdös–Rényi
• Comunitat