Ich verwende den InfoMap-Algorithmus im Paket igraph , um eine Community-Erkennung in einem gerichteten und nicht gewichteten Diagramm durchzuführen (34943 Scheitelpunkte, 206366 Kanten). In der Grafik stellen Scheitelpunkte Websites dar und Kanten stellen das Vorhandensein eines Hyperlinks zwischen Websites dar.
Ein Problem, auf das ich nach dem Ausführen des Algorithmus gestoßen bin, ist, dass die Mehrheit der Knoten eine Mitgliedschaft in einer einzigen großen Gemeinschaft hat (32920 oder 94%). Der Rest der Ecken ist in Hunderten anderer kleiner Gemeinschaften verteilt.
Ich habe verschiedene Einstellungen mit dem Parameter nb.trials (d. h. 50, 100 und jetzt 500) versucht. Dies scheint jedoch das Ergebnis nicht viel zu verändern.
Ich fühle mich ziemlich verärgert, weil die Laufzeit des Algorithmus ziemlich hoch ist, also muss ich jedes Mal auf die Ergebnisse warten (bisher noch kein Glück !!).
Vielen Dank.
Danke für all die ausgezeichneten Kommentare. Am Ende funktionierte es, indem ich den Quellcode für Infomap herunterlade und ausführte, der verfügbar ist unter: Ссылка .
Aufgrund von Lizenzproblemen wurde der neueste Code nicht in igraph integriert.
Dies löste das Problem, dass zu viele Knoten in einer einzigen massiven Gemeinschaft zusammengefasst wurden.
Insbesondere habe ich die folgenden Optionen von der Befehlszeile aus verwendet: -N 10 --directed --two-level --map
Ein großes Lob an Martin Rosvall vom Infomap-Projekt, das mir detaillierte Hilfe bei der Lösung dieses Problems gegeben hat.
Für den interessierten Leser gibt es hier mehr Informationen zu diesem Thema:
Wenn ein Netzwerk in einen Hauptcluster kollabiert, liegt es meistens an einer sehr dichten und zufälligen Verbindungsstruktur ... Im Code für gerichtete Netzwerke, die in iGraph implementiert sind, wird Teleportation kodiert. Wenn viele Knoten keine Verknüpfungen haben, kann der Effekt der Teleportation signifikant sein, da Knoten zufällig miteinander verbunden sind. Wir haben hier einen neuen Code zur Verfügung gestellt: Ссылка , der das Netzwerk clustern kann, ohne die zufällige Teleportation zu kodieren, die notwendig ist, um die Dynamik ergodisch zu machen. Weitere Informationen finden Sie in diesem Dokument: Ссылка
Ich wollte dies in einen Kommentar schreiben, aber es endete damit, dass es in diesem Format zu lang und schwer zu lesen war, also ist dies eine tangential verwandte Antwort.
Eine Sache, die Sie tun sollten, ist zu beurteilen, ob der Algorithmus eine gute Arbeit bei der Suche nach einer Gemeinschaftsstruktur leistet. Sie können versuchen, Ihr Netzwerk zu veranschaulichen:
Dies hilft Ihnen bei den nächsten Schritten. Vielleicht erfordert die Struktur des Netzwerks einen anderen Algorithmus?
Eine Sache, die ich für große Netzwerke nützlich finde, ist das Zeichnen Ihrer Kanten als Heatmap. Dies ist einfach zu tun, wenn Sie Ihre Kanten in einer Adjazenzmatrix gespeichert haben.
Dafür können Sie die Funktion image verwenden und Ihre Kantenmatrix als Argument z übergeben. Hoffentlich ermöglicht es Ihnen, die Gemeinschaftsstruktur mit dem Auge zu sehen.
Sie möchten aber auch die Korrektheit Ihres Algorithmus beurteilen, also wollen Sie die Knoten (Zeilen und Spalten Ihrer Adjazenzmatrix) nach der Community sortieren, der sie zugeordnet sind.
Eine weitere Sache, die Sie beachten sollten, ist, dass wenn Ihre Kanten gerichtet sind, es schwieriger sein kann, mit dem Auge zu beurteilen, da Kanten auf jeder Seite der Diagonalen der Heatmap erscheinen können. Eine Sache, die Sie tun können, ist stattdessen die underlying graph - das ist die Adjacency-Matrix plotten unter der Annahme, dass Ihre Kanten ungerichtet sind.
Wenn Ihr Algorithmus eine gute Arbeit leistet, würden Sie quadratische Blöcke entlang der Diagonalen erwarten, eine für jede erkannte Gemeinschaft.