Wydajny algorytm grupowania grafów

20

Szukam wydajnego algorytmu do znajdowania klastrów na dużym wykresie (ma około 5000 wierzchołków i 10000 krawędzi).

Do tej pory korzystam z algorytmu Girvan – Newman zaimplementowanego w bibliotece JUNG Javy, ale próbuję usunąć wiele krawędzi.

Czy możesz zasugerować mi lepszą alternatywę dla dużych wykresów?

mariosangiorgio
źródło
Czy spojrzałeś na k-średnich?
Oded
Czy możesz podać mi odniesienie, aby dowiedzieć się, jak używać go na wykresie?
mariosangiorgio
Przeszedłem do implementacji JUNG VoltageClusterer i jest to zdecydowanie szybkie. jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/…
mariosangiorgio
1
Czy nie jest to bardziej odpowiednie dla < cs.stackexchange.com >, ponieważ bardziej dotyczy informatyki niż inżyniera oprogramowania?
Oeufcoque Penteano

Odpowiedzi:

13

Osobiście sugeruję grupowanie Markowa . Używałem go kilka razy w przeszłości z dobrymi wynikami.

Propagacja powinowactwa jest inną realną opcją, ale wydaje się mniej spójna niż grupowanie Markowa.

Istnieją różne inne opcje, ale te dwa są dobre od razu i dobrze pasują do specyficznego problemu grafów klastrowych (które można wyświetlić jako rzadkie macierze). Rozważany jest również pomiar odległości. Twoje życie będzie łatwiejsze, jeśli użyjesz odpowiednich wskaźników.

Znalazłem ten artykuł , szukając wzorców wydajności, jest to dobra ankieta na ten temat.

Nathan Rice
źródło
Dzięki, przyjrzę się wszystkim algorytmom, które zasugerowałeś.
mariosangiorgio
Korekta: algorytmy te muszą być wagami wejściowymi odzwierciedlającymi podobieństwo, a nie odległość. Właściwość metryczna (nierówność trójkąta) nie wchodzi w nią. Przydatne może być przekształcenie wag, aby mieściły się w naturalnym zakresie, np. Dla korelacji (Pearsona), jak opisano tutaj ( micans.org/mcl/man/clmprotocols.html#array ), oraz dla wartości E BLAST, jak opisano tutaj ( micans.org/mcl/man/clmprotocols.html#blast ).
micans
10

Hierarchiczne grupowanie

To polecił mi przyjaciel. Według Wikipedii :

W tej metodzie definiuje się miarę podobieństwa określającą ilościowo (zwykle topologicznie) rodzaj podobieństwa między parami węzłów. Powszechnie stosowane miary obejmują podobieństwo cosinus, wskaźnik Jaccard i odległość Hamminga między rzędami macierzy przylegania. Następnie grupuje się podobne węzły w społeczności zgodnie z tą miarą. Istnieje kilka typowych schematów przeprowadzania grupowania, przy czym dwie najprostsze to grupowanie z pojedynczym łączeniem, w której dwie grupy są uważane za osobne wspólnoty tylko wtedy, gdy wszystkie pary węzłów w różnych grupach mają podobieństwo niższe niż podany próg, oraz pełne grupowanie wiązań , w którym wszystkie węzły w każdej grupie mają podobieństwo większe niż próg.

Klaster Markowa

Tego używam w twojej sytuacji. Jest to bardzo przydatny algorytm. Znalazłem link do ładnego pliku PDF na temat algorytmu. Jest to świetny algorytm i, z braku lepszego terminu, niezwykle „potężny”. Wypróbuj i przekonaj się.

Dynamiczny
źródło
5

W przypadku twojego problemu, myślę, że powinieneś pomyśleć o sposobie mapowania krawędzi wierzchołków do zestawu współrzędnych dla każdego wierzchołka. Nie jestem pewien, czy jest na to lepszy sposób. Myślę jednak, że możesz zacząć od przedstawienia każdego wierzchołka jako wymiaru, a następnie wartość krawędzi dla określonego wierzchołka stałaby się wartością, z którą musisz pracować dla tego konkretnego wymiaru. Następnie możesz zrobić prosty dystans Euclida i pracować z tym.

viki.omega9
źródło
1
Po lekkim przeczytaniu znalazłem to tutaj i myślę, że powinieneś rzucić okiem.
viki.omega9,