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?
algorithms
graph
cluster
mariosangiorgio
źródło
źródło
Odpowiedzi:
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.
źródło
Hierarchiczne grupowanie
To polecił mi przyjaciel. Według Wikipedii :
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ę.
źródło
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.
źródło