Metoda Louvaina

Metoda Louvain do wykrywania społeczności to metoda wyodrębniania społeczności z dużych sieci stworzonych przez Blondela i in . z Uniwersytetu w Louvain (stąd nazwa tej metody). $węzłów$ $,$ optymalizacji która wydaje się działać w czasie w

Optymalizacja modułowości

Inspiracją dla tej metody wykrywania społeczności jest optymalizacja modułowości w miarę postępu algorytmu. Modułowość to wartość skali od -0,5 (grupowanie niemodułowe) do 1 (klastrowanie w pełni modułowe), która mierzy względną gęstość krawędzi wewnątrz społeczności w stosunku do krawędzi poza społecznościami. Optymalizacja tej wartości teoretycznie skutkuje jak najlepszym pogrupowaniem węzłów danej sieci. Ponieważ jednak przechodzenie przez wszystkie możliwe iteracje węzłów w grupy jest niepraktyczne, stosowane są algorytmy heurystyczne.

W metodzie wykrywania społeczności Louvaina najpierw znajdują się małe społeczności poprzez lokalną optymalizację modułowości we wszystkich węzłach, następnie każda mała społeczność jest grupowana w jeden węzeł i pierwszy krok jest powtarzany. Metoda jest podobna do wcześniejszej metody Clauseta, Newmana i Moore'a, która łączy społeczności, których połączenie powoduje największy wzrost modułowości.

Algorytm

Wartością, która ma zostać zoptymalizowana, jest $.$ wartość zakresu która mierzy gęstość powiązań wewnątrz społeczności w porównaniu z powiązaniami W przypadku wykresu ważonego modułowość definiuje się jako:

${\ Displaystyle Q = {\ Frac {1} {2m}} \ suma \ granice _ { ij}{\bigg [}A_{ij}-{\frac {k_{i}k_{j}}{2m}}{\bigg ]}\delta (c_{i},c_{j}),}$

Gdzie

${\ Displaystyle A_ {ij}}$ reprezentuje wagę krawędzi między węzłami $Displaystyle$ jot $j}$ ;
${\ Displaystyle k_ {i}}$ $i$ są wag krawędzi dołączonych odpowiednio do węzłów $\$ jot { $}$ ;
${\ displaystyle m}$ jest sumą wszystkich wag krawędzi na wykresie;
${\ Displaystyle c_ {i}}$ i ${\ Displaystyle c_ {j}}$ to społeczności węzłów; I
${\ Displaystyle \ delta}$ to funkcja delta Kroneckera ( ${\ Displaystyle \ delta (x, y) = 1}$ jeśli ${\ Displaystyle x = y}$ , ${\ Displaystyle 0}$ W przeciwnym razie).

Na podstawie powyższego równania modułowość społeczności ${\ displaystyle c}$ obliczyć jako: do

${\ Displaystyle Q_ {c} = {\ Frac {\ Sigma _ {w}} {2m}} - ({\ Frac {\ Sigma _{tot}}{2m}})^{2},}$

Gdzie

${\ Displaystyle \ Sigma _ {w}}$ jest sumą wag krawędzi między węzłami w społeczności $;$ każda krawędź jest rozpatrywana dwukrotnie) I
${\ displaystyle \ Sigma _ {tot}}$ jest sumą wszystkich wag krawędzi dla węzłów w społeczności (w tym krawędzi, które łączą się z innymi społecznościami).

Aby skutecznie zmaksymalizować modułowość, Metoda Louvaina składa się z dwóch faz, które są powtarzane iteracyjnie.

Po pierwsze, każdy węzeł w sieci jest przypisany do własnej społeczności. Następnie dla każdego węzła $ja$ jest zmiana modułowości w celu usunięcia $\ displaystyle$ własnej społeczności i przeniesienia jej do społeczności każdego sąsiada $i}$ ja $\ displaystyle i} }$ . Wartość tę można łatwo $obliczyć ,$ $wykonując$ dwa kroki: (1) usunięcie pierwotnej społeczności i (2) wstawienie społeczności ${\ displaystyle j}$ . Te dwa równania są dość podobne, a równanie dla kroku (2) to:

${\ Displaystyle \ Delta Q = {\ bigg [} {\ Frac {\ Sigma _ {in} + 2k_ {i, in}} {2m}} - {\ bigg (} {\ Frac {\ Sigma _ {tot}+k_{i}}{2m}}{\bigg )}^{2}{\bigg ]}-{\bigg [}{\frac {\Sigma _{w}}{2m}}-{ \bigg (}{\frac {\Sigma _{tot}}{2m}}{\bigg )}^{2}-{\bigg (}{\frac {k_{i}}{2m}}{\bigg )}^{2}{\bigg ]}}$

Gdzie ${\ displaystyle \ Sigma _ {w}}$ jest sumą wszystkich wag powiązań wewnątrz społeczności, do której się przenosi, ${\ displaystyle i}$ ${\ displaystyle \ Sigma _ {tot}}$ jest sumą wszystkich wag linków do węzłów w społeczności, do której się przenosi, $displaystyle k_ {i}}$ $\$ jest ważonym stopniem ja $\ displaystyle i}$ , ${\ displaystyle k_ {i, in}}$ to suma wag powiązań między $}$ $w$ społeczności, do której się przenosi, i $}$ ${\ displaystyle i$ to suma wag wszystkich łączy w sieci. Następnie, po obliczeniu tej wartości dla wszystkich społeczności, $z$ $ją$ jest połączona, w społeczności, która spowodowała największy wzrost modułowości. Jeżeli zwiększenie nie jest możliwe, ${\ displaystyle i}$ pozostaje w swojej pierwotnej społeczności. Ten proces jest stosowany wielokrotnie i sekwencyjnie do wszystkich węzłów, dopóki nie może wystąpić żaden wzrost modułowości. Po osiągnięciu tego lokalnego maksimum modułowości pierwsza faza dobiegła końca.

W drugiej fazie algorytmu grupuje wszystkie węzły w tej samej społeczności i buduje nową sieć, w której węzły są społecznościami z poprzedniej fazy. Wszelkie połączenia między węzłami tej samej społeczności są teraz reprezentowane przez pętle własne w nowym węźle społeczności, a łącza z wielu węzłów w tej samej społeczności do węzła w innej społeczności są reprezentowane przez ważone krawędzie między społecznościami. Po utworzeniu nowej sieci druga faza dobiegła końca i pierwsza faza może zostać ponownie zastosowana w nowej sieci.

Poprzednie zastosowania

Sieć społecznościowa Twitter (2,4 miliona węzłów, 38 milionów linków) Josep Pujol, Vijay Erramilli i Pablo Rodriguez: Autorzy badają problem partycjonowania internetowych sieci społecznościowych na różnych komputerach.
Sieć telefonii komórkowej (4 miliony węzłów, 100 milionów łączy) autorstwa Dereka Greene'a, Donala Doyle'a i Padraiga Cunninghama: Strategie śledzenia społeczności w celu identyfikacji dynamicznych społeczności różnych dynamicznych sieci społecznościowych.
Wykrywanie gatunków w sieciowym modelu dynamicznym.

Porównanie z innymi metodami

Porównując metody optymalizacji modułowości, dwie ważne miary to szybkość i wynikowa wartość modułowości. Wyższa prędkość jest lepsza, ponieważ pokazuje, że metoda jest bardziej wydajna niż inne, a wyższa wartość modułowości jest pożądana, ponieważ wskazuje na posiadanie lepiej zdefiniowanych społeczności. Porównywane metody to algorytm Clauseta, Newmana i Moore'a, Ponsa i Latapy'ego oraz Wakita i Tsurumi.

Porównanie optymalizacji modułowości
	Karate	Arxiv	Internet	Internet nd.edu	Telefon	Web UK-2005	WebBase 2001
Węzły/linki	34/77	9 tys./24 tys	70 tys./351 tys	325 tys./1 mln	2,6 mln/6,3 mln	39M/783M	118M/1B
Clauseta, Newmana i Moore'a	.38/0s	0,772/3,6 s	.692/799s	.927/5034s	-/-	-/-	-/-
Ponsa i Latapy	.42/0s	0,757/3,3 s	.729/575s	.895/6666s	-/-	-/-	-/-
Wakita i Tsurumi	.42/0s	0,761/0,7 s	.667/62s	.898/248s	.56/464s	-/-	-/-
Metoda Louvaina	.42/0s	.813/0s	.781/1s	.935/3s	.769/134s	.979/738s	0,984/152 min

-/- w tabeli odnosi się do metody, której uruchomienie zajęło ponad 24 godziny. Ta tabela (z) pokazuje, że metoda Louvaina przewyższa wiele podobnych metod optymalizacji modułowości zarówno w kategoriach modułowości, jak i czasu.

Zobacz też

„Metoda Louvaina do wykrywania społeczności w dużych sieciach” Vincent Blondel http://perso.uclouvain.be/vincent.blondel/research/louvain.html