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

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:

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.

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)

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.

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.

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