Jakie są różnice między społecznościowymi algorytmami wykrywania w igraph?

[10]} Oto krótkie podsumowanie na temat algorytmów wykrywania społeczności obecnie zaimplementowanych w igraph:

• edge.betweenness.community jest hierarchicznym procesem rozkładu, w którym krawędzie są usuwane w kolejności malejącej ich krawędzi między punktami (tj. liczbą najkrótszych ścieżek, które przechodzą przez daną krawędź). Jest to motywowane faktem, że krawędzie łączące różne grupy są bardziej prawdopodobne, aby być zawarte w wielu najkrótszych ścieżek po prostu dlatego, że w wielu przypadkach są one jedyna opcja, aby przejść z jednej grupy do drugiej. Metoda ta daje dobre wyniki, ale jest bardzo powolna ze względu na złożoność obliczeniową obliczeń między krawędziami i dlatego, że wyniki między krawędziami muszą być ponownie obliczane po każdym usunięciu krawędzi. Wykresy z ~700 wierzchołkami i ~ 3500 krawędziami są wokół górnej granicy wielkości wykresów, które są możliwe do analizy za pomocą tego podejścia. Inną Wadą jest to, że edge.betweenness.community buduje pełny dendrogram i nie daje żadnych wskazówek na temat gdzie wyciąć dendrogram, aby uzyskać końcowe grupy, więc będziesz musiał użyć innej miary, aby zdecydować, że (np. wynik modułowości partycji na każdym poziomie dendrogramu).

• fastgreedy.community jest kolejnym podejściem hierarchicznym, ale jest oddolne, a nie odgórne. Stara się optymalizować funkcję jakościową zwaną modularnością w chciwy sposób. Początkowo każdy wierzchołek należy do osobnej społeczności, a Społeczności są połączone iteracyjnie tak, że każde połączenie jest lokalnie optymalne (tzn. daje największy wzrost aktualnej wartości modularności). Algorytm zatrzymuje się, gdy nie jest możliwe zwiększenie modułowości, więc daje zarówno grupowanie, jak i dendrogram. Metoda jest szybka i jest to metoda, która jest zwykle wypróbowana jako pierwsze przybliżenie, ponieważ nie ma parametrów do dostrojenia. Wiadomo jednak, że cierpi na limit rozdzielczości, tj. społeczności poniżej określonego progu wielkości (w zależności od liczby węzłów i krawędzi, jeśli I pamiętaj poprawnie) zawsze będą łączone z sąsiednimi społecznościami.

• walktrap.community jest podejściem opartym na losowych spacerach. Ogólna idea jest taka, że jeśli wykonujesz losowe spacery na wykresie, to spacery są bardziej prawdopodobne, aby pozostać w tej samej społeczności, ponieważ istnieje tylko kilka krawędzi, które prowadzą poza daną społeczność. Walktrap uruchamia krótkie losowe spacery 3-4-5 kroków (w zależności od jednego z jego parametrów) i wykorzystuje wyniki tych losowych spacerów do łączenia oddzielnych społeczności w oddolny sposób jak fastgreedy.community. Ponownie możesz użyć wskaźnika modułowości, aby wybrać miejsce cięcia dendrogramu. Jest nieco wolniejszy niż podejście fast greedy, ale też nieco dokładniejszy (według oryginalnej publikacji).

• spinglass.community jest podejściem z fizyki statystycznej, opartym na tzw. modelu Pottsa. W tym modelu każda cząstka (tj. wierzchołek) może być w jednym ze Stanów spinu c, a interakcje między cząstkami (tj. krawędzie grafu) określają, które pary wierzchołków wolą pozostać w tym samym stanie spinu, a które wolą mieć różne stany spinu. Model jest następnie symulowany dla danej liczby kroków, a Stany spin cząstek w końcu definiują wspólnoty. Konsekwencje są następujące: 1) nigdy nie będzie więcej niż C społeczności w końcu, chociaż możesz ustawić c aż do 200, co prawdopodobnie wystarczy dla Twoich celów. 2) może być mniej niż c W końcu, ponieważ niektóre stany spinowe mogą stać się puste. 3) nie jest gwarantowane, że węzły w całkowicie odległych (lub niezaangażowanych) częściach sieci mają różne stany spin. Jest to bardziej prawdopodobne, że będzie to problem tylko dla odłączonych Wykresów, więc nie martwiłbym się o to. Metoda nie jest szczególnie szybka i nie deterministyczna (ze względu na samą symulację), ale ma parametr przestrajalnej rozdzielczości, który określa rozmiary klastrów. Wariant z metoda spinglass może również uwzględniać linki negatywne (tj. linki, których punkty końcowe preferują być w różnych społecznościach).

• leading.eigenvector.community jest odgórnym podejściem hierarchicznym, które ponownie optymalizuje funkcję modułowości. W każdym kroku wykres jest dzielony na dwie części w taki sposób, że samo oddzielenie powoduje znaczny wzrost modułowości. Podział określa się na podstawie oceny czołowego eigenwektora tzw. macierzy modularności. zachodzi też zatrzymanie warunek uniemożliwiający dalsze dzielenie ściśle połączonych grup. Z powodu zastosowanych obliczeń eigenvector, może nie działać na zdegenerowanych wykresach, gdzie solver ARPACK eigenvector jest niestabilny. Na wykresach nie zdegenerowanych prawdopodobnie uzyska wyższy wynik modułowości niż metoda fast greedy, chociaż jest nieco wolniejsza.

• label.propagation.community jest prostym podejściem, w którym każdemu węzłowi przypisana jest jedna z etykiet k . Następnie metoda przebiega iteracyjnie i ponownie przypisuje etykiety węzłom w taki sposób, że każdy węzeł przyjmuje najczęściej używane etykiety sąsiadów w sposób synchroniczny. Metoda zatrzymuje się, gdy etykieta każdego węzła jest jedną z najczęstszych etykiet w jego sąsiedztwie. Jest bardzo szybki, ale daje różne wyniki w oparciu o początkową konfigurację (która jest ustalana losowo), dlatego należy uruchomić metodę dużą liczbę razy (powiedzmy 1000 razy dla wykresu), a następnie zbudować etykietowanie konsensusu, które może być nudne.

Igraph 0.6 będzie również zawierał najnowocześniejszy algorytm wykrywania społeczności Infomap, który opiera się na zasadach teorii informacji; stara się zbudować grupę, która zapewnia najkrótszą długość opisu dla losowego spaceru na wykresie, gdzie Długość opisu jest mierzona przez oczekiwaną liczbę bitów na wierzchołek wymaganych do zakodowania ścieżki losowego spaceru.

W Każdym Razie, prawdopodobnie wybrałbym fastgreedy.community lub walktrap.community jako pierwsze przybliżenie a następnie oceń inne metody, gdy okaże się, że te dwa nie są odpowiednie dla konkretnego problemu z jakiegoś powodu.