Mètode de percolació de cliques
 |
Aquest article o secció necessita millorar una traducció deficient. |
El Mètode de Percolació de cliques (conegut com a CPM, de l'anglès Clique percolation method) és el mètode més utilitzat per l'anàlisi de superposició de l'estructura comunitària de les xarxes. El terme comunitat de la xarxa (també anomenat grup de mòduls o clúster) es defineix com un grup de diversos nodes en la xarxa. Hi ha diversos mètodes alternatius per a la detecció de les comunitats en les xarxes per exemple l'algoritme de Giryan-Newman, l'agrupació jeràrquica, modularitat o maximització. El món posseeix diversos sistemes complexos en la naturalesa i la societat que poden arribar a ser representats amb èxit en termes de xarxes de captura, realitzant les connexions entre les diverses unitats que estan formades.[1]
El mètode de percolació de cliques estudia la superposició de les comunitats, l'avaluació dels canvis dins d'una comunitat i quan afecten les regions de les comunitats situades el més lluny possible de la principal.[2] El mètode acumula les comunitats de k-cliques (k-cliques és un subconjunt de vèrtex C & V de tal manera que per cada dos vèrtexs en C, existeix un node que connecta els dos, per exemple un k-clique on k=3 és equivalent a un triangle, k=4 és un tetraedre). El mètode CPM procedeix a la identificació de totes les comunitats. Una comunitat es considera com la unió màxima de tots els k-cliques, mitjançant una sèrie d'adjacents k-cliques es pot arribar des d'un a l'altre on es defineix adjacència com l'intercanvi de k-1 entre dos nodes k-cliques fixos. Les comunitats poden interpretar-se com un k-clique plantilla (un graf complet de k-nodes), on tenim un dels seus k-nodes que es pot recol·locar sempre on es desitgi i els seus adjacents es mantenen fixes complint k-1. Així les comunitats d'una xarxa són tots els subgràfics que poden ser totalment explorats.
Quant estudiem qualsevol comunitat observem que entre comunitats es produeix un solapament això és normal. Les comunitats estan codificades per colors i la superposició entre elles es destaca amb vermell. Les comunitats han de complir els criteris esmentats anteriorment d'aquesta manera entre les comunitats no hi haurà relació de dependència, el que implica que cada comunitat serà independent del que succeeix en l'altra part de la xarxa o comunitat. Per contra, si introduïm un canvi noi en el subgràfic d'una comunitat obliguem a canviar la forma de les comunitats. D'aquesta manera poden sofrir problema de límit de resolució, on la mida de la comunitat més petita es pot extreure és dependent de la mida del sistema modificat.
Aquest mètode no s'utilitza per trobar el gran nombre de k-cliques, sinó per trobar el k-clique màxim d'una comunitat. Seria l'equivalent a utilitzar el NP-complete[Cal aclariment] busqueda del màxim clique (a pesar d'aquest tenim un polinomi amb un nombre de k-cliques). El temps de processament del mètode no depèn només dels milions de k-cliques (nodes) a analitzar sinó també depèn del mida del sistema.[3]
Generalitzacions del gràfic clique[modifica]
El mètode de percolació pot ser generalitzat mitjançant diferents quantitats de solapament entre diversos k-cliques. Contant cada solapament entre les diferents comunitats es poden considerar un nou gràfic de k-cliques, on cada k-clique està representat en el gràfic original per un vèrtex en el gràfic nou. Es pot utilitzar qualsevol mètode de detecció de comunitat per identificar els clústers en el gràfic original a través de l'estructura k-cliques dita abans.[4]
Per exemple un gràfic simple, podem definir el solapament entre dos k-cliques, el mètode de percolació de cliques seria l'equivalent a col·locar un Umbral, deixant tots els nodes (k-1), amb la resta de components connectats formant les comunitats trobades en CPM. Per tant per k=2 serien el gràfic original i el gràfic de k-cliques en aquest cas és un gràfic de línies de la xarxa original.[5]
Si ens parem a observar el nombre de vèrtexs que posseeix les diferents comunitats i els prenem com una mesura de superposició pot donar resultats dolents. Aquelles comunitats que posseeixen un nombre més gran de k vèrtexs dins del gràfic dominarà dins del gràfic k-cliques. El problema sorgeix perquè si un vèrtex està en n diferents k-cliques contribuirà a n (n-1)/2 marcs en dit gràfic de k-cliques. Una solució fàcil és deixar que cada vèrtex en comú a la superposició de dos k-cliques ha de contribuir amb un valor igual 1/n en la mesura de la superposició.[6]
En general, el punt de vista gràfic de k-cliques és una manera útil de trobar generalitzacions de mètodes de percolació estàndard de k-cliques i també trobar algun problema en diferents nodes.
Transició de percolació del CPM[modifica]
En el model Edros_renyi considerem N nodes d'una xarxa qualsevol enllaçats aleatòriament entre si de dos a dos nodes. Els nodes es troben enllaçats es descarten. Es repeteix el procés M vegades escollint un parell de nodes en cada torn al final haurem establert com a màxim M enllaços entre parelles de nodes. Si M és un valor petit respecte al valor total de nodes molts estaran desconnectats entre si, en canvi els altres nodes estaran formant petites comunitats. Per contra, si M és gran en comparació amb N el nombre total de nodes, és molt possible que quasi tots els nodes estén enllaçats entre si.
El model Erdros-Renyi primer calcula la probabilitat pc d'una parella escollida a l'atzar este enllaçades entre si. Per això es calcula el nombre total de possibles parelles de N nodes, a un nombre total anomenat NP la seva expressió és la següent:
Per tant com el nombre de parelles enllaçades pel model és M, es manté l'expressió analítica de la probabilitat pc com a: pc= M/Np= 2M/N(N-1)
Un cop establerta la probabilitat pc, s'estableix un cert llindar el qual els k-cliques es poden organitzar en una comunitat gegant (la mida de la comunitat gegant és comparable amb la mida del sistema).[7]
Aquesta transició del model és anàloga a la transició de percolació, un mètode similar seria observar moltes xarxes reals, així si k és gran, només observaríem les parts més densament enllaçades perquè aquestes són les acceptades com a comunitat. Quan k és baix, tant el nombre com la mida de les comunitats no són tan denses com abans podríem parlar d'aquestes comunitats començant a créixer. Però en la majoria dels casos, un valor crític de k, per sota del qual una comunitat gegant, aquesta comunitat pot contenir moltes comunitats petites.[8]
Mètode de percolació de cliques directe (CPMD)[modifica]
El CPMD és una extensió natural del mètode de percolació clique (CPM), en aquesta extensió els blocs de construcció d'una comunitat aquesta es defineix com a sub-graf complets de mida k, on es poden demanar els k nodes de tal manera que entre un parell de nodes existeix un enllaç dirigint apuntant des del node amb el rang més alt fins al node amb el rang més baix. El CPMD defineix unes comunitats en la xarxa com els clústers de percolació dirigides k-cliques.
Mètode de percolació de cliques ponderats (CPMD)[modifica]
El CPMW és una extensió natural del mètode de percolació Clique (CPM), en aquesta extensió troba els mòduls mitjançant l'eliminació d'enllaços més febles que un Umbral amb valor fixe W, tenint en compte les connexions restants sense ponderar. Aquesta extensió defineix les comunitats ponderades de la xarxa amb els clústers de percolació de ponderació k-cliques. La mesura geomètrica dels valors dels enllaços dins d'un sub-graf anomenat intensitat del sub-graf.
Algoritmes i programari[modifica]
Hi ha un nombre d'implementacions de percolació de k-cliques. El CPM va ser implementat per primer cop i popularitzat per CFinder (programari gratuït per a ús no comercial) per la detecció i visualització de comunitats superposades en les xarxes. El programa permet la visualització personalitzable i permet un fàcil passeig a través de les comunitats que es troben.
Aplicacions[modifica]
- Estudi de la metàstasi del càncer
- Xarxes econòmiques
- Clústers de documents
Referències[modifica]
- ↑ Fergal, Reid. «Percolation Computation in Complex Networks» (en anglès). [Consulta: 30 abril 2012].
- ↑ Viale, S.Severo. «Community detection in graphs» (en anglès).
- ↑ Gergely, Palla. «The Critical Point of k-Clique Percolation in the Erdos–Renyi Graph» (en anglés).
- ↑ Gergely, Palla. «k-clique percolation and clustering in directed and weighted networks» (en anglès).
- ↑ «Posts Tagged ‘clique percolation method'» (en anglès).[Enllaç no actiu]
- ↑ Polner, Peter. «Centrality properties of directed module members in social networks» (en anglès).
- ↑ M. Kumpula, Jussi. «Sequential algorithm for fast clique percolation» (en anglés).
- ↑ «CFinder» (en anglés).