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

Mam listę około 100 obiektów igraph, przy czym typowy obiekt ma około 700 wierzchołków i 3500 krawędzi.

Chciałbym zidentyfikować grupy wierzchołków, w których powiązania są bardziej prawdopodobne. Planuję następnie użyć modelu mieszanego do przewidywania, ile wierzchołków wiązań wewnątrzgrupowych ma przy użyciu atrybutów wierzchołków i grup.

Niektórzy ludzie mogą chcieć odpowiedzieć na inne aspekty mojego projektu, co byłoby świetne, ale najbardziej interesują mnie informacje o funkcjach w igraph do grupowania wierzchołków. Natknąłem się na te algorytmy wykrywania społeczności, ale nie jestem pewien ich zalet i wad ani czy jakaś inna funkcja byłaby lepsza w moim przypadku. Widziałem tutaj również linki , ale nie są one specyficzne dla igraph. Dzięki za radę.

Oto krótkie podsumowanie algorytmów wykrywania społeczności aktualnie zaimplementowanych w igraph:

• edge.betweenness.communityjest hierarchicznym procesem dekompozycji, w którym krawędzie są usuwane w kolejności malejącej ich wyników między krawędziami (tj. liczba najkrótszych ścieżek przechodzących przez daną krawędź). Jest to motywowane faktem, że krawędzie łączące różne grupy z większym prawdopodobieństwem znajdują się na wielu najkrótszych ścieżkach, po prostu dlatego, że w wielu przypadkach są jedyną opcją przejścia z jednej grupy do drugiej. Ta metoda daje dobre wyniki, ale jest bardzo powolna ze względu na złożoność obliczeniową obliczeń między krawędziami oraz ponieważ wyniki między nimi muszą być ponownie obliczane po każdym usunięciu krawędzi. Twoje wykresy z ~ 700 wierzchołkami i ~ 3500 krawędziami znajdują się w pobliżu górnej granicy rozmiaru wykresów, które można przeanalizować za pomocą tego podejścia. Inną wadą jest toedge.betweenness.communitybuduje pełny dendrogram i nie daje żadnych wskazówek, gdzie wyciąć dendrogram, aby uzyskać końcowe grupy, więc będziesz musiał użyć innej miary, aby to zdecydować (np. wynik modułowości partycji na każdym poziomie dendrogram).

• fastgreedy.communityto kolejne podejście hierarchiczne, ale jest ono oddolne zamiast odgórne. Próbuje optymalizować funkcję jakości zwaną modułowością w chciwy sposób. Początkowo każdy wierzchołek należy do oddzielnej społeczności, a społeczności są scalane iteracyjnie w taki sposób, że każde scalenie jest lokalnie optymalne (tj. Daje największy wzrost aktualnej wartości modułowości). Algorytm zatrzymuje się, gdy nie jest już możliwe zwiększenie modularności, więc daje ci zarówno grupowanie, jak i dendrogram. Metoda jest szybka i jest to metoda, która jest zwykle stosowana jako pierwsze przybliżenie, ponieważ nie ma parametrów do dostrojenia. Wiadomo jednak, że cierpi z powodu granicy 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 dobrze pamiętam) zawsze będą scalane z sąsiednimi społecznościami.

• walktrap.communityto podejście oparte na przypadkowych spacerach. Ogólna idea jest taka, że ​​jeśli wykonujesz spacery losowe na wykresie, to z większym prawdopodobieństwem pozostaną one w tej samej społeczności, ponieważ istnieje tylko kilka krawędzi, które prowadzą poza daną społeczność. Walktrap prowadzi krótkie, losowe spacery o długości 3-4-5 kroków (w zależności od jednego z parametrów) i wykorzystuje wyniki tych przypadkowych spacerów do łączenia oddzielnych społeczności w sposób oddolny fastgreedy.community. Ponownie, możesz użyć wyniku modułowości, aby wybrać miejsce cięcia dendrogramu. Jest nieco wolniejszy niż szybkie, chciwe podejście, ale także nieco dokładniejszy (zgodnie z oryginalną publikacją).

• spinglass.communityjest podejściem z fizyki statystycznej, opartym na tzw. modelu Pottsa. W tym modelu każda cząstka (tj. Wierzchołek) może znajdować się w jednym ze stanów spinowych c , a interakcje między cząstkami (tj. Krawędziami grafu) określają, które pary wierzchołków wolałyby pozostać w tym samym stanie spinowym, a które wolą mieć różne stany spinu. Model jest następnie symulowany dla określonej liczby kroków, a stany spinowe cząstek ostatecznie określają zbiorowości. Konsekwencje są następujące: 1) Ostatecznie nigdy nie będzie więcej społeczności niż c , chociaż możesz ustawić c nawet na 200, co prawdopodobnie wystarczy do twoich celów. 2) Może być mniej niż cspołeczności w końcu, ponieważ niektóre stany spinowe mogą stać się puste. 3) Nie ma gwarancji, że węzły w całkowicie odległych (lub odłączonych) częściach sieci mają różne stany spinu. Jest to bardziej prawdopodobne, że będzie to problem tylko dla odłączonych wykresów, więc nie martwiłbym się tym. Metoda nie jest szczególnie szybka i nie deterministyczna (z powodu samej symulacji), ale ma dostrajany parametr rozdzielczości, który określa rozmiary klastrów. Odmiana metody spinglass może również uwzględniać powiązania negatywne (tj. Połączenia, których punkty końcowe wolą znajdować się w różnych społecznościach).

• leading.eigenvector.communityto hierarchiczne podejście odgórne, które ponownie optymalizuje funkcję modułowości. Na każdym etapie wykres jest dzielony na dwie części w taki sposób, że samo rozdzielenie skutkuje znacznym wzrostem modułowości. Podział jest określany przez ocenę wiodącego wektora własnego tak zwanej macierzy modularności, a także występuje warunek zatrzymania, który zapobiega dalszemu podziałowi ściśle połączonych grup. Ze względu na zastosowane obliczenia wektora własnego może nie działać na zdegenerowanych grafach, w których solver wektora własnego ARPACK jest niestabilny. Na grafach niezdegenerowanych prawdopodobnie da wyższy wynik modułowości niż metoda szybkiej zachłanności, chociaż jest nieco wolniejsza.

• label.propagation.communityto proste podejście, w którym do każdego węzła jest przypisana jedna z k etykiet. Następnie metoda przechodzi iteracyjnie i ponownie przypisuje etykiety do węzłów w taki sposób, że każdy węzeł przyjmuje w sposób synchroniczny najczęściej używaną etykietę swoich sąsiadów. Metoda kończy się, gdy etykieta każdego węzła jest jedną z najczęściej występujących etykiet w jego sąsiedztwie. Jest bardzo szybka, ale daje różne wyniki w zależności od konfiguracji początkowej (która jest ustalana losowo), dlatego należy uruchomić metodę dużą liczbę razy (powiedzmy 1000 razy dla wykresu), a następnie zbudować etykietę konsensusową, którą można nudny.

igraph 0.6 będzie również zawierał najnowocześniejszy algorytm wykrywania społeczności Infomap, oparty na zasadach teorii informacji; próbuje zbudować zgrupowanie, które zapewni najkrótszą długość opisu dla losowego spaceru na grafie, gdzie długość opisu jest mierzona przez oczekiwaną liczbę bitów na wierzchołek potrzebną do zakodowania ścieżki losowego spaceru.

W każdym razie, prawdopodobnie wybrałbym pierwsze przybliżenie fastgreedy.communitylub walktrap.communityjako pierwsze, a następnie oceniłbym inne metody, gdy okaże się, że te dwie z jakiegoś powodu nie nadają się do konkretnego problemu.

Podsumowanie różnych algorytmów wykrywania społeczności można znaleźć tutaj: http://www.r-bloggers.com/summary-of-community-detection-algorithms-in-igraph-0-6/

Warto zauważyć, że algorytm InfoMAP jest nowością, która może być przydatna (obsługuje również ukierunkowane wykresy).