Algoritmus Girvan – Newman - Girvan–Newman algorithm

The Algoritmus Girvan – Newman (pojmenoval podle Michelle Girvan a Mark Newman ) je hierarchická metoda používaná k detekci komunity v složité systémy.^[1]

Hranice mezi vztahem a strukturou komunity

Algoritmus Girvan – Newman detekuje komunity postupným odstraňováním hran z původní sítě. Připojenými komponentami zbývající sítě jsou komunity. Namísto pokusu o konstrukci opatření, které nám říká, které hrany jsou pro komunity nejdůležitější, se algoritmus Girvan – Newman zaměřuje na hrany, které jsou s největší pravděpodobností „mezi“ komunitami.

Vrchol mezi je ukazatelem vysoce centrální uzly v sítích. Pro libovolný uzel ${displaystyle i}$, vrchol mezi je definován jako počet nejkratších cest mezi dvojicemi uzlů, které jím procházejí. Je relevantní pro modely, kde síť moduluje přepravu zboží mezi známými počátečními a koncovými body, za předpokladu, že takový převod hledá nejkratší dostupnou trasu.

Algoritmus Girvan – Newman rozšiřuje tuto definici na případ hran, přičemž definuje „hraniční mezi“ hranu jako počet nejkratších cest mezi dvojicemi uzlů, které podél ní probíhají. Pokud je mezi dvojicí uzlů více než jedna nejkratší cesta, je každé cestě přiřazena stejná váha, takže celková váha všech cest se rovná jednotce. Pokud síť obsahuje komunity nebo skupiny, které jsou volně spojeny pouze několika hranicemi mezi skupinami, pak všechny nejkratší cesty mezi různými komunitami musí jít podél jedné z těchto několika hran. Okraje spojující komunity tedy budou mít vysoký okraj mezi (alespoň jeden z nich). Odstraněním těchto okrajů jsou skupiny od sebe odděleny, a tak je odhalena základní komunitní struktura sítě.

Kroky algoritmu pro detekci komunity jsou shrnuty níže

1. Nejprve se počítá mezi všemi existujícími hranami v síti.
2. Okraje s nejvyšší přesností jsou odstraněny.
3. Přepočte se vzájemnost mezi všemi hranami ovlivněnými odstraněním.
4. Kroky 2 a 3 se opakují, dokud nezůstanou žádné hrany.

Skutečnost, že jediné přepočítávané rozdíly jsou pouze ty, které jsou ovlivněny odstraněním, může snížit dobu běhu simulace procesu v počítačích. Centrálnost mezi směry však musí být přepočítána s každým krokem, jinak dojde k závažným chybám. Důvodem je, že se síť přizpůsobuje novým podmínkám nastaveným po odstranění hrany. Například pokud jsou dvě komunity propojeny více než jednou hranou, pak to neexistuje žádná záruka Všechno těchto okrajů bude mít vysokou mezi. Podle metody to víme aspoň jeden z nich bude mít, ale není známo nic víc. Přepočítáním rozpětí po odstranění každého okraje je zajištěno, že alespoň jeden ze zbývajících okrajů mezi dvěma komunitami bude mít vždy vysokou hodnotu.

Konečným výsledkem algoritmu Girvan – Newman je a dendrogram. Jak běží algoritmus Girvan – Newman, dendrogram se vytváří shora dolů (tj. Síť se rozděluje do různých komunit s postupným odstraňováním odkazů). Listy dendrogramu jsou jednotlivé uzly.

Viz také

• Blízkost
• Hierarchické shlukování
• Modularita

Reference