Was sind die Unterschiede zwischen Community-Erkennungsalgorithmen in igraph?

Ich habe eine Liste von ungefähr 100 Igraph-Objekten mit einem typischen Objekt mit ungefähr 700 Eckpunkten und 3500 Kanten.

Ich möchte Gruppen von Eckpunkten identifizieren, innerhalb derer Bindungen wahrscheinlicher sind. Mein Plan ist es, dann ein gemischtes Modell zu verwenden, um mithilfe von Scheitelpunkt- und Gruppenattributen vorherzusagen, wie viele Scheitelpunkte innerhalb der Gruppe Verbindungen haben.

Einige Leute möchten vielleicht auf andere Aspekte meines Projekts reagieren, was großartig wäre, aber das, was mich am meisten interessiert, sind Informationen über Funktionen in igraph zum Gruppieren von Scheitelpunkten. Ich bin auf diese Community-Erkennungsalgorithmen gestoßen , bin mir aber nicht sicher, welche Vor- und Nachteile sie haben oder ob eine andere Funktion für meinen Fall besser wäre. Ich habe die Links auch hier gesehen , aber sie sind nicht spezifisch für igraph. Danke für deinen Rat.

Hier ist eine kurze Zusammenfassung der Community-Erkennungsalgorithmen, die derzeit in igraph implementiert sind:

• edge.betweenness.communityist ein hierarchischer Zerlegungsprozess, bei dem Kanten in absteigender Reihenfolge ihrer Kanten-Zwischenwerte entfernt werden (dh der Anzahl der kürzesten Pfade, die durch eine bestimmte Kante verlaufen). Dies ist durch die Tatsache motiviert, dass Kanten, die verschiedene Gruppen verbinden, eher in mehreren kürzesten Pfaden enthalten sind, einfach weil sie in vielen Fällen die einzige Möglichkeit sind, von einer Gruppe zur anderen zu wechseln. Diese Methode liefert gute Ergebnisse, ist jedoch aufgrund der rechnerischen Komplexität der Kanten-Zwischenberechnungen sehr langsam und weil die Zwischen-Werte nach jeder Kantenentfernung neu berechnet werden müssen. Ihre Diagramme mit ~ 700 Eckpunkten und ~ 3500 Kanten liegen um die obere Größengrenze von Diagrammen, die mit diesem Ansatz analysiert werden können. Ein weiterer Nachteil ist dasedge.betweenness.communityErstellt ein vollständiges Dendrogramm und gibt Ihnen keine Anleitung, wo das Dendrogramm geschnitten werden muss, um die endgültigen Gruppen zu erhalten. Daher müssen Sie eine andere Maßnahme verwenden, um dies zu entscheiden (z. B. die Modularitätsbewertung der Partitionen auf jeder Ebene der Dendrogramm).

• fastgreedy.communityist ein anderer hierarchischer Ansatz, der jedoch von unten nach oben statt von oben nach unten erfolgt. Es wird versucht, eine Qualitätsfunktion namens Modularität auf gierige Weise zu optimieren. Anfänglich gehört jeder Scheitelpunkt zu einer separaten Community, und Communitys werden iterativ zusammengeführt, sodass jede Zusammenführung lokal optimal ist (dh den größten Anstieg des aktuellen Werts der Modularität ergibt). Der Algorithmus stoppt, wenn die Modularität nicht mehr erhöht werden kann, sodass Sie sowohl eine Gruppierung als auch ein Dendrogramm erhalten. Die Methode ist schnell und wird normalerweise als erste Annäherung versucht, da keine Parameter zum Einstellen vorhanden sind. Es ist jedoch bekannt, dass es unter einer Auflösungsgrenze leidet, dh Communitys unterhalb eines bestimmten Größenschwellenwerts (abhängig von der Anzahl der Knoten und Kanten, wenn ich mich richtig erinnere) werden immer mit benachbarten Communitys zusammengeführt.

• walktrap.communityist ein Ansatz, der auf zufälligen Spaziergängen basiert. Die allgemeine Idee ist, dass, wenn Sie zufällige Spaziergänge in der Grafik ausführen, die Spaziergänge eher innerhalb derselben Community bleiben, da nur wenige Kanten außerhalb einer bestimmten Community führen. Walktrap führt kurze zufällige Spaziergänge mit 3-4-5 Schritten aus (abhängig von einem seiner Parameter) und verwendet die Ergebnisse dieser zufälligen Spaziergänge, um separate Communities wie von unten nach oben zusammenzuführen fastgreedy.community. Auch hier können Sie mithilfe der Modularitätsbewertung auswählen, wo das Dendrogramm geschnitten werden soll. Es ist etwas langsamer als der schnelle gierige Ansatz, aber auch etwas genauer (laut Originalveröffentlichung).

• spinglass.communityist ein Ansatz aus der statistischen Physik, der auf dem sogenannten Potts-Modell basiert. In diesem Modell kann sich jedes Partikel (dh der Scheitelpunkt) in einem von c Spinzuständen befinden, und die Wechselwirkungen zwischen den Partikeln (dh den Kanten des Diagramms) geben an, welche Scheitelpunktpaare es vorziehen würden, im selben Spinzustand zu bleiben und welche bevorzugen unterschiedliche Spinzustände. Das Modell wird dann für eine bestimmte Anzahl von Schritten simuliert, und die Spinzustände der Partikel am Ende definieren die Gemeinschaften. Die Konsequenzen sind wie folgt: 1) Am Ende wird es nie mehr als c Communities geben, obwohl Sie c auf bis zu 200 setzen können, was wahrscheinlich für Ihre Zwecke ausreicht. 2) Es kann weniger als c gebenGemeinschaften am Ende, da einige der Spin-Zustände leer werden können. 3) Es kann nicht garantiert werden, dass Knoten in vollständig entfernten (oder nicht verbundenen) Teilen des Netzwerks unterschiedliche Spinzustände aufweisen. Dies ist eher ein Problem nur für nicht verbundene Diagramme, daher würde ich mir darüber keine Sorgen machen. Die Methode ist nicht besonders schnell und nicht deterministisch (aufgrund der Simulation selbst), verfügt jedoch über einen einstellbaren Auflösungsparameter, der die Clustergrößen bestimmt. Eine Variante der Spinglass-Methode kann auch negative Links berücksichtigen (dh Links, deren Endpunkte sich lieber in verschiedenen Communities befinden).

• leading.eigenvector.communityist ein hierarchischer Top-Down-Ansatz, der die Modularitätsfunktion erneut optimiert. In jedem Schritt wird der Graph in zwei Teile geteilt, so dass die Trennung selbst eine signifikante Erhöhung der Modularität ergibt. Die Aufteilung wird durch Auswertung des führenden Eigenvektors der sogenannten Modularitätsmatrix bestimmt, und es gibt auch eine Stoppbedingung, die verhindert, dass eng verbundene Gruppen weiter aufgeteilt werden. Aufgrund der Eigenvektorberechnungen funktioniert es möglicherweise nicht bei entarteten Graphen, bei denen der ARPACK-Eigenvektorlöser instabil ist. Bei nicht entarteten Graphen ergibt sich wahrscheinlich ein höherer Modularitätswert als bei der Fast-Greedy-Methode, obwohl sie etwas langsamer ist.

• label.propagation.communityist ein einfacher Ansatz, bei dem jedem Knoten eine von k Bezeichnungen zugewiesen wird . Das Verfahren fährt dann iterativ fort und weist den Knoten Beschriftungen neu zu, so dass jeder Knoten synchron die häufigste Beschriftung seiner Nachbarn nimmt. Die Methode wird beendet, wenn die Beschriftung jedes Knotens eine der häufigsten Beschriftungen in seiner Nachbarschaft ist. Es ist sehr schnell, liefert jedoch unterschiedliche Ergebnisse basierend auf der anfänglichen Konfiguration (die zufällig festgelegt wird). Daher sollte die Methode eine große Anzahl von Malen ausgeführt werden (z. B. 1000-mal für ein Diagramm) und dann eine Konsenskennzeichnung erstellt werden langweilig.

igraph 0.6 wird auch den neuesten Infomap-Community-Erkennungsalgorithmus enthalten, der auf informationstheoretischen Prinzipien basiert. Es wird versucht, eine Gruppierung zu erstellen, die die kürzeste Beschreibungslänge für einen zufälligen Spaziergang im Diagramm bereitstellt, wobei die Beschreibungslänge anhand der erwarteten Anzahl von Bits pro Scheitelpunkt gemessen wird, die zum Codieren des Pfades eines zufälligen Spaziergangs erforderlich sind.

Wie auch immer, ich würde wahrscheinlich mit fastgreedy.communityoder walktrap.communityals erste Annäherung gehen und dann andere Methoden bewerten, wenn sich herausstellt, dass diese beiden aus irgendeinem Grund nicht für ein bestimmtes Problem geeignet sind.

Eine Zusammenfassung der verschiedenen Community-Erkennungsalgorithmen finden Sie hier: http://www.r-bloggers.com/summary-of-community-detection-algorithms-in-igraph-0-6/

Insbesondere der InfoMAP-Algorithmus ist ein neuer Neuling, der nützlich sein könnte (er unterstützt auch gerichtete Grafiken).