Algorytm Girvana-Newmana

Algorytm Girvana-Newmana (nazwany na cześć Michelle Girvan i Marka Newmana ) to hierarchiczna metoda używana do wykrywania społeczności w złożonych systemach .

Krawędź między krawędzią a strukturą społeczności

Algorytm Girvana-Newmana wykrywa społeczności poprzez stopniowe usuwanie krawędzi z oryginalnej sieci. Połączone komponenty pozostałej sieci to społeczności. Zamiast próbować skonstruować miarę, która mówi nam, które krawędzie są najbardziej centralne dla społeczności, algorytm Girvana-Newmana koncentruje się na krawędziach, które najprawdopodobniej znajdują się „między” społecznościami.

Między wierzchołkami jest wskaźnikiem wysoce centralnych węzłów w sieciach. Dla każdego węzła $.$ między wierzchołkami jest definiowany jako ułamek najkrótszych ścieżek między parami węzłów, które przez niego przechodzą Jest to istotne w przypadku modeli, w których sieć moduluje transfer towarów między znanym nonsensem początku i końca, przy założeniu, że taki transfer szuka najkrótszej dostępnej trasy.

Algorytm Girvana – Newmana rozszerza tę definicję na przypadek krawędzi, definiując „między krawędziami” krawędzi jako liczbę najkrótszych ścieżek między parami węzłów biegnących wzdłuż niej. Jeśli istnieje więcej niż jedna najkrótsza ścieżka między parą węzłów, każdej ścieżce przypisuje się taką samą wagę, tak aby całkowita waga wszystkich ścieżek była równa jedności. Jeśli sieć zawiera społeczności lub grupy, które są tylko luźno połączone kilkoma krawędziami między grupami, wówczas wszystkie najkrótsze ścieżki między różnymi społecznościami muszą przebiegać wzdłuż jednej z tych kilku krawędzi. W ten sposób krawędzie łączące społeczności będą miały wysoką krawędź między krawędziami (co najmniej jeden z nich). Usuwając te krawędzie, grupy są oddzielane od siebie, a tym samym ujawnia się podstawowa struktura społeczności sieci.

Kroki algorytmu do wykrywania społeczności są podsumowane poniżej

1. Najpierw obliczana jest odległość pomiędzy wszystkimi istniejącymi krawędziami w sieci.
2. Krawędź (krawędzie) z najwyższym odstępem są usuwane.
3. Podział pomiędzy wszystkimi krawędziami, których dotyczy usunięcie, jest obliczany ponownie.
4. Kroki 2 i 3 są powtarzane, aż nie pozostaną żadne krawędzie.

Fakt, że przeliczane są tylko te, na które ma wpływ usunięcie, może skrócić czas symulacji procesu w komputerach. Jednak centralność pomiędzy elementami musi być ponownie obliczana na każdym kroku, w przeciwnym razie wystąpią poważne błędy. Powodem jest to, że sieć dostosowuje się do nowych warunków ustalonych po usunięciu krawędzi. Na przykład, jeśli dwie społeczności są połączone więcej niż jedną krawędzią, nie ma gwarancji, że wszystkie te krawędzie będą miały wysoki poziom pośrednictwa. Zgodnie z metodą wiemy, że co najmniej jeden z nich będzie miało, ale nic poza tym nie wiadomo. Dzięki ponownemu obliczeniu odległości między dwiema społecznościami po usunięciu każdej krawędzi zapewnia się, że co najmniej jedna z pozostałych krawędzi między dwiema społecznościami będzie zawsze miała wysoką wartość.

Końcowym wynikiem algorytmu Girvana-Newmana jest dendrogram . Podczas działania algorytmu Girvana-Newmana dendrogram jest tworzony od góry do dołu (tj. sieć dzieli się na różne społeczności z sukcesywnym usuwaniem łączy). Liście dendrogramu to pojedyncze węzły.

Zobacz też

• Bliskość
• Grupowanie hierarchiczne
• Modułowość