Gervan-Njumanov algoritam

Gervan-Njumanov algoritam (nazvan po Mišel Girvan i Marku Njumanu) je jedna od metoda koje se koriste za otkrivanje zajednice u složenim sistemima. Pojam "struktura zajednice" odnosi se na to grupisanje, iako to nije sasvim isto. Zajednica se sastoji od podskupa čvorova u okviru koje čvor-čvor veze su guste, a ivice na čvorovima u drugim sredinama su manje guste. Postoje brojne alternativne metode za otkrivanje zajednice u mrežama. Ovo uključuje hijerarhijsko grupisanje, podela grafova tako da maksimiziraju kvalitetne funkcije, kao što su mreže modularnosti, iznenadna maksimizacija, K - klika filtriranje itd.

Centralna ivica i struktura zajednice

Metod hijerarhijskog grupisanja se zasniva na dodeli težine za svaku ivicu koje se stavljajaju u jednu praznu mrežu u početku, počevši od ivice sa jakim težinama i napreduje prema slabijim. Ivice sa najvećim težinama u okviru zajednice su centralne. Iako se tradicionalno koristi za otkrivanje zajednice, metod ima nedostatke. Jedan od njih, na primer, je nemogućnost da se klasifikuje u zajednici čvor koji je povezan na mrežu sa samo jednom ivicom.

Gervan-Njuman algoritam deluje na suprotan način. Umesto da pokušava da izgradi meru koja nam govori koje su ivice centralne u zajednici, on se fokusira na tim ivicama koje su najudaljenije od centralne, ivice koje su najviše "između" zajednica. Zajednice se otkrivaju postepenim uklanjanjem ivica od originalnog grafa, a ne dodavanjem najjače ivice na početku prazne mreže.

"Centralna tačka" je proučavana u prošlosti kao mera centralnosti i uticaja čvorova u mreži. Za svaki čvor , "Centralna tačka" se definiše kao broj najkraćih puteva između parova čvorova koji prolaze kroz nju. To je mera uticaja čvora nad protokom informacija između ostalih čvorova, posebno u slučajevima u kojima protok informacija preko mreže, pre svega sledi najkraći put na raspolaganju. Girvan-Njuman algoritam proširuje ovu definiciju u slučaju ivica, definisanje "ivica između" od ivice kao broj najkraćih puteva između parova čvorova koji se pokreću uz njega. Ako postoji više od jednog najkraćeg puta između para čvorova, svaki put je dobio jednaku težinu takav da je ukupna masa svih staza iznosi jedinstvu. Ako mreža sadrži zajednice ili grupe koje su samo labavo povezane sa nekoliko unutrašnjih ivica, onda su svi najkraći putevi između različitih zajednica morali da idu duž jednog od ovih nekoliko ivica. Dakle, ivice koje povezuju zajednice će imati veliki broj "ivica između" (bar jedanu od njih). Uklanjanjem ove ivice, grupe su odvojene jedna od druge i tako osnovna zajednica strukture mreže je otkrivena.

Koraci algoritma za detekciju zajednice su u sledećoj tabeli

1. Prvo se računa središnjost svih postojećih ivica u mreži.
2. Srednja ivica se uklanja.
3. Ponovo se računa središnjost svih ivica na koje je uticalo uklanjanje.
4. Koraci 2 i 3 se ponavljaju sve dok se ne uklone preostale ivice.

Činjenica da se jedino ispituje središnjost za ivice na koje je uticalo uklanjanje, mogu smanjiti vreme rada simulacije procesa na računarima. Međutim, centralna središnjost mora biti izračunata pri svakom koraku, ili se javljaju ozbiljne greške. Razlog je u tome što se mreža prilagođava novim uslovima nakon uklanjanja ivica. Na primer, ako su dve zajednice povezane sa više od jedne ivice, onda ne postoji garancija da sve ove ivice imati visoku središnjost. Po metodu, mi znamo da će je bar jedna od njih će imati, ali ništa više od toga nije poznato. Pomoću preračunavanja središnjosti posle uklanjanja svake ivice, obezbeđeno je da će bar jedan od preostalih ivica između dve zajednice uvek imaju veliku vrednost.

Krajnji rezultat Gervan-njumanovog algoritma je dendrogram. Kako Gervan-Njumanov algoritam radi, dendrogram se proizvodi od vrha nadole (tj. mrežu deli na različite zajednice sa sukcesivnim uklanjanjem linkova). Lišće dendrograma su pojedinačni čvorovi.