Wydajny algorytm grupowania grafów

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?

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.

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ę.

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.