Zastanawiam się, czy ktoś mógłby zasugerować, jakie są dobre punkty wyjścia, jeśli chodzi o wykrywanie społeczności / partycjonowanie / grupowanie wykresów na wykresie z ważonymi , nieukierunkowanymi krawędziami. Wykres ma około 3 miliony krawędzi, a każda krawędź wyraża stopień podobieństwa między dwoma połączonymi wierzchołkami. W szczególności w tym zbiorze danych krawędzie są jednostkami, a wierzchołki są miarą podobieństwa ich obserwowanego zachowania.
W przeszłości postępowałem zgodnie z sugestią, którą dostałem na stats.stackexchange.com i korzystałem z implementacji klastrowania modułowości Newmana przez igraph i byłem zadowolony z wyników, ale to było w nieważonym zbiorze danych.
Czy są jakieś specyficzne algorytmy, na które powinienem patrzeć?
źródło
Wiem, że Gephi może przetwarzać niekierowany wykres ważony, ale wydaje mi się, że pamiętam, że musi być przechowywany w GDF , który jest bardzo zbliżony do CSV lub Ucinet DL . Pamiętaj, że wciąż jest to wersja alfa. Teraz, jeśli chodzi o grupowanie wykresu, Gephi wydaje się brakować potoków klastrowania, z wyjątkiem algorytmu MCL, który jest teraz dostępny w najnowszej wersji. W 2009 r. Istniał projekt Google Code , Gephi Network Statistics (obejmujący np. Modułowość Newmana), ale nie wiem, czy coś zostało wydane w tym kierunku. W każdym razie wydaje się, że pozwala to na pewne obliczenia modułowości / klastrowania, ale patrz także Analiza sieci społecznościowych przy użyciu R i Gephi iPrzygotowanie danych do analizy sieci społecznościowych przy użyciu R i Gephi ( wielkie dzięki @Tal).
Jeśli jesteś przyzwyczajony do Pythona, warto wypróbować NetworkX (oto przykład ważonego wykresu z odpowiednim kodem). Masz wiele sposobów przeprowadzenia analizy.
Powinieneś także spojrzeć na INSNA - oprogramowanie do analizy sieci społecznościowych lub na stronę Tima Evansa o złożonych sieciach i złożoności .
źródło
Gephi implementuje metodę Louvain Modularity: http://wiki.gephi.org/index.php/Modularity
Twoje zdrowie
źródło
Algorytm modułowości Louvain jest dostępny w C ++: https://sites.google.com/site/findcommunities/
Zajmuje się ważonymi sieciami milionów węzłów i krawędzi i wykazano, że jest znacznie szybszy niż algorytm Newmana.
źródło
Jeśli używasz Pythona i utworzyłeś wykres ważony za pomocą NetworkX , możesz użyć python-louvain do grupowania. Gdzie G to wykres ważony:
źródło
Właśnie natknąłem się na pakiet tnet dla R. Twórca wydaje się badać odkrycie społeczności na wykresach ważonych i dwustronnych (dwumodowych).
http://opsahl.co.uk/tnet/content/view/15/27/
Jeszcze go nie użyłem.
źródło
SLPA (obecnie nazywany GANXiS) jest szybkim algorytmem zdolnym do wykrywania zarówno rozłącznych, jak i nakładających się społeczności w sieciach społecznościowych (nieukierowane / ukierunkowane i nieważone / ważone). Wykazano, że algorytm daje znaczące wyniki w rzeczywistych sieciach społecznych i sieciach genowych. Jest to jeden z najnowocześniejszych. Jest dostępny pod adresem
https://sites.google.com/site/communitydetectionslpa/
Zobacz miłą recenzję arxiv.org/abs/1110.5813, aby uzyskać więcej informacji
źródło
Mam implementację Java dla nienakładającej się, ważonej / nieważonej sieci, która prawdopodobnie mogłaby obsłużyć 3 miliony węzłów (przetestowałem ją pod kątem zbioru danych o milionie węzłów). Działa jednak jak k-średnie i wymaga, aby liczba partycji została wykryta jako dane wejściowe (k w kmeans). Możesz znaleźć więcej informacji tutaj , a tutaj jest kod , w github
Twoje zdrowie,
źródło