Jak przeprowadzić wykrywanie społeczności w ważonej sieci / wykresie społecznościowym?

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ć?

Implementacja igraph modułowego klastrowania Newmana (funkcja fastgreedy) może być również używana z ważonymi krawędziami. Wystarczy dodać atrybut wagi do krawędzi i analizować jak zwykle. Z mojego doświadczenia wynika, że ​​działa jeszcze szybciej z ciężarkami, ponieważ jest mniej więzi.

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 .

Gephi implementuje metodę Louvain Modularity: http://wiki.gephi.org/index.php/Modularity

Twoje zdrowie

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.

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:

import community 
partition = community.best_partition(G, weight='weight')

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.

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

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,