Ansatz und Beispiel für das Clustering von Graphen in „R“

10

Ich möchte Knoten in einem Diagramm mithilfe von Diagrammclustern in 'r' gruppieren / zusammenführen.

Hier ist eine erstaunlich spielerische Variante meines Problems.

  • Es gibt zwei "Cluster"
  • Es gibt eine "Brücke", die die Cluster verbindet

Hier ist ein Kandidatennetzwerk:
Geben Sie hier die Bildbeschreibung ein

Wenn ich mir die Verbindungsentfernung ansehe, die "Hopcount", wenn Sie so wollen, dann kann ich die folgende Matrix erhalten:

 mymatrix <- rbind(
     c(1,1,2,3,3,3,2,1,1,1),
     c(1,1,1,2,2,2,1,1,1,1),
     c(2,1,1,1,1,1,1,1,2,2),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,2,2),
     c(2,1,1,1,1,1,1,1,2,2),
     c(1,1,1,2,2,2,1,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1))

Gedanken hier:

  • Zum Glück oder aufgrund der Einfachheit des Spielzeugs weist die Matrix offensichtliche Flecken auf. Dies wird in der (sehr großen) Matrix nicht der Fall sein. Wenn ich die Beziehung zwischen Punkt und Zeile zufällig wählen würde, wäre sie nicht so sauber.
  • Ich habe möglicherweise einen Fehler gemacht. Wenn ich also einen Tippfehler habe, lass es mich wissen.
  • Die Anzahl der Sprünge ist hier die kürzeste Anzahl von Sprüngen, um den Punkt in Zeile i mit dem Punkt in Spalte j zu verbinden. Ein Self-Hop ist immer noch ein Hop, also ist die Diagonale alles.

In dieser Matrix hat also eine größere Entfernung (Hopfen) eine höhere Zahl. Wenn ich eine Matrix mit "Konnektivität" anstelle der Entfernung haben wollte, könnte ich eine Punktumkehrung durchführen, bei der jede Zelle der Matrix durch ihre multiplikative Umkehrung ersetzt wird.

Fragen:

Um mir zu helfen, meinen eigenen Weg zu finden:

  • Was sind die Begriffe, um die Anzahl der Knoten in einem Diagramm durch Kombinieren zu verringern? Ist es Clustering, Zusammenführen, Munging - was sind die Wörter, die ich verwenden sollte?
  • Was sind die bewährten Techniken? Gibt es ein Lehrbuch zum Thema? Können Sie auf Artikel oder Websites verweisen?
  • Jetzt habe ich zuerst versucht, hier nachzuschauen - es ist ein großartiger Ort für die erste Überprüfung. Ich habe nicht gefunden, wonach ich gesucht habe. Wenn ich es verpasst habe (nicht unwahrscheinlich), können Sie mich auf eine oder zwei beantwortete Fragen zum Thema hier im Lebenslauf verweisen?

Um mich dahin zu bringen, wohin ich gehe:

  • Gibt es ein 'R'-Paket, das die Knoten im Netzwerk ordnungsgemäß gruppiert?
  • Könnten Sie mich auf Beispielcode verweisen, um dies zu tun?
  • Gibt es ein 'R'-Paket, das das resultierende reduzierte Netzwerk grafisch darstellt?
  • Könnten Sie mich auf Beispielcode verweisen, um dies zu tun?

Danke im Voraus.

EngrStudent
quelle
2
Bitte beachten Sie, dass das Nachfragen nach (R) Paketen oder Code hier nicht zum Thema gehört. Möglicherweise möchten Sie den Teil "Finden" stärker hervorheben und den Teil "Erhalten" weniger.
Gung - Reinstate Monica
3
Ich werde versuchen, irgendwann eine vollständige Antwort zu geben, wenn ich eine Chance @gung bekomme. Für eine schnelle Antwort hier ist jedoch die Community-Erkennung , die mit dem R- igraphPaket auf das Beispieldiagramm von EngrStudent angewendet wird .
Andy W
1
IMHO gibt es nur einen Cluster in diesem Diagramm. Es gibt jedoch drei überlappende Cliquen . Ich weiß nicht, warum Sie die mittlere Clique zerstören wollen - wenn Sie dies nicht formalisieren können, fällt es Ihnen schwer, einen Algorithmus zu finden.
Hat aufgehört - Anony-Mousse
2
Für das, was es wert ist, findet mcl ( micans.org/mcl ) die beiden Cluster (ich stimme der Einschätzung von Anony-Mousse nicht wirklich zu, und ich finde den Ansatz der Cliquenmodellierung für das Clustering von Graphen nicht besonders fruchtbar). Dies ist der Standard für den einzelnen Parameter (Steuerung der Granularität). Dieser Algorithmus (mcl - ich habe ihn veröffentlicht) wird in der Bioinformatik ziemlich häufig verwendet, und (hoch skalierbarer) Quellcode ist verfügbar. Die Anbindung an R erfolgt einfach über Textschnittstellen.
Micans
2
Das Nachfragen nach Code und Paketen war hier im Wesentlichen immer ein Thema. Das Bitten um Hilfe mit vorhandenem Code (dh Sie haben ein reproduzierbares Beispiel ) ist ein Thema zum Thema Stapelüberlauf . Wenn Sie das nicht wussten, ist es Zeit, es zu lernen. Die Idee, dass die Benutzer, die R Qs auf SO beantworten, keine statistische Expertise haben, ist seltsam für mich, aber viele Leute scheinen das anzunehmen; jedenfalls ist es nicht wahr. Dass Ihr Q von einem SO-Post beantwortet wurde, sollte hier etwas aussagen. OTOH, der sagt: "Was für eine Art von Analyse ist das, kann mich jemand auf Ressourcen hinweisen?", Ist hier definitiv ein Thema.
Gung - Reinstate Monica

Antworten:

9

In Ihrem Beispiel wird vorgeschlagen, Communitys innerhalb des Netzwerks zu finden, die mehr Verbindungen zwischen Knoten in der Community und relativ wenige Kanten zwischen Knoten in verschiedenen Communitys aufweisen. Dies unterscheidet sich von der Suche nach isolierten Gemeinschaften , in denen es Untergraphen gibt, die vollständig voneinander getrennt sind.

Hier ist ein Beispiel für die Community-Erkennung in R unter Verwendung des igraphPakets und eines in Clauset et al. (2004) . Um diesen Algorithmus zu verwenden, verwandle ich Ihre "Sprungzahl" in eine binäre Adjazenzmatrix ohne Selbstschleifen. Der Algorithmus benötigt eine ungerichtete Matrix, die mit Ihrem handgeschriebenen Diagramm und den von Ihnen angegebenen Daten übereinstimmt (die Kanten sind symmetrisch).

library(igraph)
mymatrix <- rbind(
     c(1,1,2,3,3,3,2,1,1,1),
     c(1,1,1,2,2,2,1,1,1,1),
     c(2,1,1,1,1,1,1,1,2,2),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,3,3),
     c(3,2,1,1,1,1,1,2,2,2),
     c(2,1,1,1,1,1,1,1,2,2),
     c(1,1,1,2,2,2,1,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1),
     c(1,1,2,3,3,2,2,1,1,1))

#turn this into an adjacency matrix
adjMat <- mymatrix == 1
diag(adjMat) <- 0 #no self loops

g  <- graph.adjacency(adjMat)
plot(g)

#only works for undirected graphs, which this example is fine since symetric
fc <- fastgreedy.community(as.undirected(g))

#make colors for different communities
V(g)$color <- ifelse(membership(fc)==1,"red","blue")
plot(g)

Geben Sie hier die Bildbeschreibung ein

Ich kann nicht sagen, ob es angemessen ist, solche Knoten für die weitere Analyse zu reduzieren, aber eine solche Community-Erkennung ist definitiv nützlich, um das Netzwerk zu erkunden. Es gibt auch viele andere Community-Erkennungsalgorithmen (sowie andere Bibliotheken für die Netzwerkanalyse in R). Dies ist nur ein Beispiel, das zufällig die gewünschte Ausgabe für dieses Spielzeugproblem erzeugt.

Andy W.
quelle
1
Auch die vorherigen Kommentare über die Verwendung einer Graph - Datenbank gegeben, Sie brauchen nicht als Adjazenzmatrix dargestellt um die Grafik zu haben. Eine Tabelle für die Knoten und eine Zeile für jede Kante ist ein typischeres / effizienteres Format, und Sie können daraus ein igraphNetzwerk machen.
Andy W
1

Wenn Sie noch nicht mit einem Repository für Ihre Knoten- und Verbindungsdaten verbunden sind, sehen Sie sich möglicherweise das Rneo4j-Paket an. Dies impliziert jedoch die Verwendung von neo4j (eine Diagrammdatenbank, kein RDBMS) zum Speichern Ihrer Daten. Ich bin hier kein Experte, aber ich denke, dieser Ansatz könnte besonders effektiv sein, wenn a) wie von Anony-Mousse vorgeschlagen, Sie dies nicht formalisieren können oder b) die Anzahl der Knoten und Verbindungen besonders groß ist oder c) Sie wickeln Sie haben zusätzliche Fragen zu Ihrem Netzwerk.

user3123116
quelle
Ich wusste nicht, dass so etwas existiert. Ordentlich! Ist das ein anständiges Beispiel für das Material? nicolewhite.github.io/RNeo4j/examples
EngrStudent
Wie würde man von Daten in neo4j zu Graph-Clustering übergehen? Würde mcl oder igraph damit arbeiten?
EngrStudent
2
Sobald Sie Ihre Daten von neo4j in R gezogen haben, können Sie jedes andere R-Paket (z. B. AndyW schlägt igraph vor) für die Daten verwenden. Alternativ - das Rneo4j-Paket enthält Befehle zum Abrufen von Daten und ermöglicht Ihnen auch das Ausführen der Cypher-Abfragesprache (analog zu SQL, jedoch speziell für das neo4j-Diagramm db entwickelt). In Cypher können Sie anspruchsvolle Abfragen durchführen und einige vordefinierte Algorithmen ausführen (kürzeste Pfade, alle Pfade, alle einfachen Pfade, Dijkstra usw.). Ich bin hier sowohl in Bezug auf die Charaktere als auch in Bezug auf den Inhalt an meine Grenzen gestoßen. Wenn Sie diesen Weg beschreiten möchten (sorry!), Ist die neo4j-Site möglicherweise Ihre nächste Station.
user3123116
1

Für zukünftige Leser,

Hier ist eine Reihe von Funktionen aus den igraph-Paketen und die letzte stammt von MCL:

print("LABEL PROPAGATION")
w<-cluster_label_prop(g)

print("Leading Eigen")
w<-cluster_leading_eigen(g)

print("SpinGlass")
w<-cluster_spinglass(g, stop.temp = 0.05)

print("walktrap")
w<-cluster_walktrap(g, steps=4)

print("MCL")
adj<-get.adjacency(g)
w<-mcl(adj,addLoops=TRUE)

Die Dokumentation finden Sie hier http://igraph.org/r/doc/ und hier https://cran.r-project.org/web/packages/MCL/MCL.pdf

Ich finde Walktrap besonders nützlich

Omar Jaafor
quelle
Obwohl dies mit der Frage zusammenhängt, scheint es keine Antwort zu sein.
Michael R. Chernick
2
Ich habe die beiden Fragen beantwortet: Gibt es ein 'R'-Paket, das die Knoten im Netzwerk richtig gruppiert? Könnten Sie mich auf Beispielcode verweisen, um dies zu tun? Aber ja, es beantwortet nicht alle Fragen.
Omar Jaafor