Funktioniert Newmans Netzwerkmodularität für signierte, gewichtete Diagramme?

11

Die Modularität eines Diagramms wird auf seiner Wikipedia-Seite definiert . In einem anderen Beitrag erklärte jemand, dass Modularität für gewichtete Netzwerke leicht berechnet (und maximiert) werden kann, da die Adjazenzmatrix $A_{ij}$ auch wertvolle Bindungen enthalten kann. Ich würde jedoch gerne wissen, ob dies auch mit vorzeichenbehafteten, geschätzten Kanten funktioniert, die beispielsweise zwischen -10 und +10 liegen. Können Sie eine Intuition, einen Beweis oder eine Referenz zu diesem Thema liefern?

clustering data-visualization networks partitioning modularity Philip Leifeld
quelle

13

Die einfache Verallgemeinerung der Modularität für gewichtete Netzwerke funktioniert nicht , wenn diese Gewichte signiert sind. Mit einfach meine ich: nur die Gewichtsmatrix anstelle der Adjazenzmatrix verwenden, wie es Newman beispielsweise in (Newman 2004) tut . Sie benötigen eine bestimmte Version, wie die von Benjamin Lind oder die von (Gomez et al. 2009) .

In beiden Artikeln erklären sie den Grund dafür. Zusammenfassend: Die Modularität beruht auf der Tatsache, dass einige normalisierte Grade (oder Stärken bei gewichteten Netzwerken) als Wahrscheinlichkeiten betrachtet werden können. Die Wahrscheinlichkeit, dass eine Verbindung zwischen den Knoten und besteht, wird unter Verwendung von geschätzt $i$ $j$ , wobei und die jeweiligen Stärken der Knoten und und $p_ip_j=w_iw_j/(2w)^2$ $w_i$ $w_j$ $i$ $j$ $w$ ist die Gesamtstärke über alle Netzwerkknoten. Wenn einige Gewichte negativ sind, garantiert die ursprüngliche Normalisierung keine Werte in mehr, so dass die obige -Größe nicht als Wahrscheinlichkeit betrachtet werden kann. $[0,1]$ $p_ip_j$

Um dieses Problem zu lösen, haben Gomez et al . Betrachten Sie positive und negative Links getrennt. Sie erhalten zwei unterschiedliche Modularitätswerte: einen für positive Links und einen für negative. Sie subtrahieren die letzteren von den ersteren, um die Gesamtmodularität zu erhalten.

Vincent Labatut
quelle

Danke, das sieht vielversprechend aus. Ich werde einen Blick auf Gomez et al. Artikel. Gibt es eine Implementierung?

Philip Leifeld

1

Ja, ich denke, Sie finden den Quellcode hier: deim.urv.cat/~sgomez/radatools.php

Vincent Labatut

Der Code sieht in EXE-Dateien wie eine Blackbox aus. Wenn Sie jedoch nur Modularität für positive und negative Gewichte benötigen, konvertieren Sie Ihre Matrix einfach in eine gewichtete Kantenliste, (2) teilen Sie die Liste in positiv und negativ vorzeichenbehaftete Gewichte auf und und (3) Berechnen Sie die Modularität unter igraphVerwendung absoluter Gewichte in jeder Partition?

Fr.

Das ist eine gute Idee, aber die für negative Gewichte verarbeitete Modularität muss minimiert werden, und die Methoden in igraph maximieren nur (soweit ich weiß). Was den Quellcode betrifft, denke ich, dass Sie Recht haben. Vielleicht können Sie sich direkt an einen der Autoren wenden?

Vincent Labatut

6

Ja, kann es. Spin-Glass-Modelle zur Community-Erkennung können die Modularität aus gewichteten, signierten Diagrammen berechnen. Sie möchten Traag und Bruggeman "Community-Erkennung in Netzwerken mit positiven und negativen Links" als Referenz. Die Funktion "spinglass.community ()" in igraph kann die Communitys finden und die Modularität des Diagramms zurückgeben.

BenjaminLind
quelle

Vielen Dank. Ich interessiere mich nicht wirklich für die Gemeinschaften, sondern für die Tendenz des signierten Netzwerks, in Gemeinschaften polarisiert / fragmentiert zu werden. Soweit ich sehen kann, kann die Modularität communitiesmithilfe der modularityFunktion aus dem resultierenden Objekt abgerufen werden. Ich werde mir auf jeden Fall den Artikel von Traag und Bruggeman ansehen. Da die Implementierung auf simuliertem Tempern zu basieren scheint: Wie gut funktioniert sie? Kann ich tatsächlich sicherstellen, dass der Algorithmus wirklich die optimale Modularität zurückgibt (da ich Polarisation / Fragmentierung messen möchte)?

Philip Leifeld

3

Wir haben in diesem Artikel auf das Problem der Modularitätsfunktionen mit signierten Netzwerken hingewiesen . Sie neigen dazu, die positive Dichte von Communities mehr zu ignorieren, wenn die absolute Anzahl negativer Links im Netzwerk zunimmt.

Auch hier ist unsere Open-Source-Java-Projekt für gewichtete signierte Netzwerke, das auf dem Constant Potts-Modell (ähnlich der Modularität), dem schnellen Louvain-Algorithmus und der Community-Bewertung basierend auf einer Erweiterung der Kartengleichung basiert .

Esmailian, P. und Jalili, M., 2015. Community-Erkennung in signierten Netzwerken: Die Rolle negativer Bindungen in verschiedenen Maßstäben. Wissenschaftliche Berichte, 5, S.14339

Esmailian
quelle

Funktioniert Newmans Netzwerkmodularität für signierte, gewichtete Diagramme?

Antworten: