Wie berechnet man Zentralitätsmaße in einem 4-Millionen-Edge-Netzwerk mit R?

9

Ich habe eine CSV-Datei mit 4 Millionen Kanten eines gerichteten Netzwerks, das Personen darstellt, die miteinander kommunizieren (z. B. John sendet eine Nachricht an Mary, Mary sendet eine Nachricht an Ann, John sendet eine weitere Nachricht an Mary usw.). Ich möchte zwei Dinge tun:

  1. Finden Sie Grad-, Zwischen- und (vielleicht) Eigenvektor-Zentralitätsmaße für jede Person.

  2. Holen Sie sich eine Visualisierung des Netzwerks.

Ich möchte dies über die Befehlszeile eines Linux-Servers tun, da mein Laptop nicht viel Strom hat. Ich habe R auf diesem Server und der Statnet-Bibliothek installiert. Ich fand diesen Beitrag von 2009 von jemandem kompetenter als ich, der versuchte, dasselbe zu tun und Probleme damit hatte. Ich habe mich also gefragt, ob jemand andere Hinweise dazu hat, vorzugsweise Schritt für Schritt, da ich nur weiß, wie man die CSV-Datei lädt und sonst nichts.

Um Ihnen eine Vorstellung zu geben, sieht meine CSV-Datei folgendermaßen aus:

$ head comments.csv
    "src","dest"
    "6493","139"
    "406705","369798"
$ wc -l comments.csv 
4210369 comments.csv
amh
quelle
Bei einigen dieser Maßnahmen hängt es davon ab, wie viele separate Personen (Knoten) das Netzwerk hat, ob R damit umgehen oder notieren kann. R ist möglicherweise nicht unbedingt das beste Werkzeug für die rechnerischen Aspekte. Es gibt einen Typen mit dem Nachnamen Leskovec, der früher bei Carnegie Mellon war - ich glaube als Student -, der viele Dinge mit beschreibenden Statistiken über große Grafiken gemacht hat. Es gibt viele Dienstprogramme, mit denen Sie Diagramme "visualisieren" können, aber meistens habe ich festgestellt, dass sie ziemlich schwer zu interpretieren sind oder viel Sinn ergeben. Die grafische Darstellung nur der Gradverteilungen könnte ein erster Anfang sein.
Kardinal
Sogar das Plotten von 4 Millionen Punkten kann eine Weile dauern ...
Wok
@wok, nah. Ein Kinderspiel auf den heutigen Computern. Wie auch immer, Sie könnten immer zuerst in ein PNG gehen und das ist wahrscheinlich gut genug für die Gradverteilung. Die Grafik des OP ist wirklich nicht so groß.
Kardinal

Antworten:

7

Sie haben eine Kantenliste, die mithilfe der Netzwerkbibliothek in ein Netzwerkobjekt konvertiert werden kann. Hier ist ein Beispiel mit fiktiven Daten.

library(network)

src <- c("A", "B", "C", "D", "E", "B", "A", "F")
dst <- c("B", "E", "A", "B", "B", "A", "F", "A")

edges <- cbind(src, dst)
Net <- as.network(edges, matrix.type = "edgelist")

summary(Net)
plot(Net)

Eine Warnung ist jedoch angebracht: Sie haben ein sehr großes Netzwerk und ich bin nicht sicher, ob eine Handlung so informativ sein wird. Es wird wahrscheinlich wie ein großer Wollknäuel aussehen. Ich bin mir auch nicht sicher, wie gut diese Bibliotheken mit so großen Datenmengen umgehen. Ich schlage vor, dass Sie sich die Dokumentation für die Netzwerk-, Statnet- und Ergm-Bibliotheken ansehen. Das Journal of Statistical Software (v24 / 3) bietet mehrere Artikel zu diesen Bibliotheken. Das Problem kann hier gefunden werden:

http://www.jstatsoft.org/v24

Jason Morgan
quelle
1
Ich erinnere mich nur schwach an die Weltkarte des Facebook-Netzwerks, die in R erstellt wurde. Ich glaube, der Autor hat seinen Prozess in seinem Blog ausführlich beschrieben. Ich nehme an, dass die Verwendung dieses Ansatzes eine Karte erzeugen würde, die selbst mit 4 Millionen Knoten informativ ist.
Owe Jessen
Entschuldigung für die naive Frage, aber wie konvertiere ich eine Tabelle in das, was Sie als srcund haben dst. Dies ist, was ich normalerweise mache, um die Datei zu laden (jetzt eine durch Tabulatoren getrennte Datei): el <- read.csv("comment-net/comments-ouids.tsv",header=T,sep="\t")
amh
read.csv () sollte einen data.frame erzeugen. as.network () kann dies direkt lesen oder Sie müssen as.matrix (el) ausführen.
Jason Morgan
Ich bin ziemlich skeptisch, dass diese Bibliotheken mit einem Diagramm von Millionen von Knoten viel anfangen können. Haben Sie sie tatsächlich mit vergleichbaren Datensätzen verwendet?
Szabolcs
Das Poster bezog sich auf ein Netzwerk mit 4 Millionen Kanten , nicht auf Knoten. Ich habe die statnetBibliotheksfamilie in einem ungerichteten Netzwerk von mehr als 3500 Knoten (~ 8 Millionen mögliche Kanten) verwendet. Das war durchaus machbar, besonders wenn das Ziel nur darin bestand, Netzwerkstatistiken zu berechnen. Ich habe sogar ERGMs in Netzwerken dieser Größe geschätzt. Aber Ihr Punkt ist gut aufgenommen; Ich bezweifle, dass Netzwerke von Millionen von Knoten leicht analysiert werden können.
Jason Morgan
3

Ich denke nicht, dass R hier die erste Wahl ist (vielleicht irre ich mich). Sie benötigen hier große Arrays, um Ihre Netzwerkdateien im entsprechenden Datenformat zu indizieren und vorzubereiten. Zunächst werde ich versuchen, die SNAP- Bibliothek von Jure (Rob erwähnt ihn im obigen Beitrag) zu verwenden. Es ist in C ++ geschrieben und funktioniert sehr gut in großen Netzwerken.

Andrej
quelle
Vielen Dank, dass Sie SNAP erwähnt haben. Ich schaue hinein. Hast du es benutzt? Das dazugehörige Zentralitätsbeispiel scheint nahe an dem zu liegen, was ich will. Ich habe versucht, es so zu ändern, dass es mit meinen mehrfach gerichteten Diagrammdaten funktioniert, aber es konnte nicht kompiliert werden. Ich bin mir nicht sicher, ob es angebracht ist, hier eine Frage zu stellen, also könnte ich ein neues Q erstellen.
amh
1
@andresmh, Sie könnten versuchen, Ihr Diagramm so zu verkleinern, dass zuerst eine einzige Beobachtung pro gerichtetem Paar erfolgt. Für das Eigenwertmaterial sind Ihre Daten wahrscheinlich ähnlich oder äquivalent zu einem gewichteten Zufallslauf in der Grafik. Ich bin nicht sicher, ob SNAP das unterstützt, aber es ist wahrscheinlich. Wenn alles andere fehlschlägt, senden Sie möglicherweise eine ganz bestimmte E-Mail an Jure. Er ist ein sehr netter Kerl, daher wäre ich nicht überrascht, wenn er eine schnelle Anleitung geben würde.
Kardinal
@cardinal: Ich habe in SNAP einen Beispielcode gefunden, der genau das tut, was ich will, außer für ein ungerichtetes Diagramm. Ich denke, mein Diagramm ist das, was die SNAP-Dokumente als "gerichtetes Multi-Diagramm" bezeichnen. Also habe ich nur eine Zeile centrality.cppvon TUNGraphin geändert TNEGraph(siehe pastebin.com/GHUquJvT Zeile 24). Es wird nicht mehr kompiliert. Ich vermute, es erfordert einen anderen Knotentyp? Der Fehler, den ich bekomme, ist: centrality.cpp:24: error: conversion from ‘TUNGraph::TNodeI’ to non-scalar type ‘TNEGraph::TNodeI’ requested(siehe vollständigen Fehler unter pastebin.com/86mCbByG )
amh
3

Gephi ( http://gephi.org/ ) ist möglicherweise eine einfache Möglichkeit, die Daten zu untersuchen. Sie können es mit ziemlicher Sicherheit visualisieren und einige Berechnungen durchführen (obwohl ich es einige Zeit nicht verwendet habe, sodass ich mich nicht an alle Funktionen erinnern kann).

Celenius
quelle
3

Aus früheren Erfahrungen mit einem Netzwerk von 7 Millionen Knoten denke ich, dass die Visualisierung Ihres gesamten Netzwerks ein nicht interpretierbares Bild ergibt. Ich könnte verschiedene Visualisierungen vorschlagen, die Teilmengen Ihrer Daten verwenden, z. B. nur die Top-10-Knoten mit den meisten eingehenden oder ausgehenden Links. Ich stimme Celenius 'Vorschlag zur Verwendung von Gephi zu.

Zubin
quelle
@andresmh, Maslov und Sneppen ( Science , 2002) haben eine Visualisierung, die in diesem Zusammenhang nützlich sein könnte. Beim Durchsuchen der neuesten Statistiken / comp-sci-bezogenen Zitate dieser Arbeit habe ich dies ebenfalls gefunden. Hier kann eine andere verwandte Arbeit sein.
Kardinal
1

Wenn Sie sich mit der Größe des Netzwerks befassen, können Sie das igraphPaket in R ausprobieren. Wenn dies in R schlecht funktioniert, ist es möglicherweise besser als Python-Modul. Oder sogar das networkxPaket für Python

fioghual
quelle
1

Haben Sie den Verdacht, dass im Netzwerk nur wenige sehr große Komponenten verbunden sind? Wenn nicht, können Sie es in verschiedene Komponenten zerlegen, was die Berechnung von Zentralitätsmaßen erheblich erleichtert.

Michael Bishop
quelle
+1 dazu - wenn es sich um eine vollständig verbundene Komponente handelt, ist das eine Sache, aber wenn Sie das Netzwerk zerlegen können, haben Sie sowohl kleinere Daten als auch mehrere unabhängige Netzwerke, die parallel analysiert werden können.
Fomite
1

Es gibt mehrere R-Softwarepakete, die verwendet werden können, einschließlich "sna" und "network". Eine Sache, auf die ich mich nicht unbedingt verlassen würde, wenn Sie Leistungsprobleme mit sna haben, ist NetworkX. Ich liebe NetworkX zu Tode und verwende es für die meisten meiner Analysen, aber NetworkX ist ziemlich stolz darauf, eine meist rein pythonische Implementierung zu sein. Schneller vorkompilierter Code wird nicht besonders gut genutzt, und sna übertrifft NetworkX häufig erheblich.

Fomite
quelle