R: igraph, community detection, edge.betweenness-Methode, Anzahl/Liste Mitglieder der jeweiligen Gemeinschaft?

Question

Ich habe eine relativ große Grafik mit Vertices: 524 Edges: 1125, der realen Welt Transaktionen. Die Kanten sind gerichtet und haben ein Gewicht (Aufnahme ist optional). Ich versuche, die verschiedenen Gemeinschaften innerhalb der grafischen Darstellung untersuchen und müssen im Wesentlichen ein Verfahren, das:

: Berechnet alle möglichen Gemeinden

: Berechnet die optimale Anzahl von Gemeinden

-Gibt die Mitglieder/Anzahl der Mitglieder jeder (optimalen) Gemeinschaft

Bis jetzt habe ich es geschafft, den folgenden Code zusammenzufassen, der eine farbkodierte Grafik entsprechend den verschiedenen Communities aufträgt, aber ich habe keine Ahnung, wie ich die Anzahl der Communities kontrollieren kann plotten Sie die Top 5 Gemeinden mit dem h höchste Mitgliedschaft) oder führen Sie die Mitglieder einer bestimmten Gemeinschaft auf.

library(igraph) 
edges <- read.csv('http://dl.dropbox.com/u/23776534/Facebook%20%5BEdges%5D.csv') 
all<-graph.data.frame(edges) 
summary(all) 

all_eb <- edge.betweenness.community(all) 
mods <- sapply(0:ecount(all), function(i) { 
all2 <- delete.edges(all, all_eb$removed.edges[seq(length=i)]) 
cl <- clusters(all2)$membership 
modularity(all, cl) 
}) 


plot(mods, type="l") 

all2<-delete.edges(all, all_eb$removed.edges[seq(length=which.max(mods)-1)]) 

V(all)$color=clusters(all2)$membership 

all$layout <- layout.fruchterman.reingold(all,weight=V(all)$weigth) 

plot(all, vertex.size=4, vertex.label=NA, vertex.frame.color="black", edge.color="grey", 
edge.arrow.size=0.1,rescale=TRUE,vertex.label=NA, edge.width=.1,vertex.label.font=NA) 

---

Da die Kante Between Verfahren so durchgeführt schlecht ich wieder versucht, die walktrap Methode:

all_wt<- walktrap.community(all, steps=6,modularity=TRUE,labels=TRUE) 
all_wt_memb <- community.to.membership(all, all_wt$merges, steps=which.max(all_wt$modularity)-1) 


colbar <- rainbow(20) 
col_wt<- colbar[all_wt_memb$membership+1] 

l <- layout.fruchterman.reingold(all, niter=100) 
plot(all, layout=l, vertex.size=3, vertex.color=col_wt, vertex.label=NA,edge.arrow.size=0.01, 
        main="Walktrap Method") 
all_wt_memb$csize 
[1] 176 13 204 24 9 263 16 2 8 4 12 8 9 19 15 3 6 2 1 

19 Cluster - Viel besser!

Jetzt sagen, ich hatte einen "bekannten Cluster" mit einer Liste seiner Mitglieder und und wollte jeden der beobachteten Cluster auf die Anwesenheit von Mitgliedern aus dem "bekannten Cluster" überprüfen. Rückgabe des Prozentsatzes der gefundenen Mitglieder. Kann das folgende nicht beenden ??

Answer 1

Ein paar dieser Fragen können Sie herausfinden, indem Sie sich die Dokumentation der von Ihnen verwendeten Funktionen genau anschauen. Zum Beispiel beschreibt die Dokumentation von clusters im Abschnitt "Werte", was von der Funktion zurückgegeben wird, von denen einige Ihre Fragen beantworten. Dokumentation beiseite, können Sie immer die str Funktion verwenden, um das Make-up eines bestimmten Objekts zu analysieren.

Das gesagt, um die Mitglieder oder die Anzahl der Mitglieder in einer bestimmten Gemeinschaft zu erhalten, können Sie das Objekt membership von der clusters Funktion zurückgegeben (die Sie bereits verwenden, um Farbe zuzuweisen). So etwas wie:

summary(clusters(all2)$membership) 

würde die IDs der Cluster, die verwendet werden, beschreiben. Im Fall Ihrer Beispieldaten sieht es so aus, als ob Sie Cluster mit den IDs von 0 bis 585 für insgesamt 586 Cluster haben. (Beachten Sie, dass Sie nicht in der Lage sein wird, diejenigen angezeigt werden sehr genau das Farbschema verwenden Sie derzeit verwenden.)

Um die Anzahl der Knoten in jedem Cluster zu bestimmen, Sie an der csize Komponente aussehen kann auch durch clusters zurück . In diesem Fall ist es ein Vektor der Länge 586, der für jeden berechneten Cluster eine Größe speichert. So können Sie

verwenden

clusters(all2)$csize 

die Liste der Größen Ihrer Cluster zu erhalten. Seien Sie gewarnt, dass Ihre clusterIDs, wie bereits erwähnt, bei 0 ("null-indiziert") beginnen, während R-Vektoren bei 1 ("ein-indexiert") beginnen. Sie müssen diese Indizes also um eins verschieben. Zum Beispiel gibt clusters(all2)$csize[5] die Größe des Clusters mit der ID 4 zurück.

Um die Scheitelpunkte in einem Cluster aufzulisten, möchten Sie nur herausfinden, welche IDs in der zuvor genannten membership-Komponente mit dem betreffenden Cluster übereinstimmen. Also, wenn ich will (sind 21 von diesen gibt, nach clusters(all2)$csize[129]) die Eckpunkte in Cluster # 128 finden, konnte ich verwenden:

which(clusters(all2)$membership == 128) 
length(which(clusters(all2)$membership == 128)) #21 

und die Eckpunkte in diesem Cluster abzurufen, kann ich die V Funktion und übergeben Sie in den Indizes, die ich gerade berechnet, die ein Mitglied des Clusters:

> V(all2)[clusters(all2)$membership == 128] 
Vertex sequence: 
[1] "625591221 - Clare Clancy"   
[2] "100000283016052 - Podge Mooney"  
[3] "100000036003966 - Jennifer Cleary" 
[4] "100000248002190 - Sarah Dowd"  
[5] "100001269231766 - LirChild Surfwear" 
[6] "100000112732723 - Stephen Howard" 
[7] "100000136545396 - Ciaran O Hanlon" 
[8] "1666181940 - Evion Grizewald"  
[9] "100000079324233 - Johanna Delaney" 
[10] "100000097126561 - Órlaith Murphy" 
[11] "100000130390840 - Julieann Evans" 
[12] "100000216769732 - Steffan Ashe"  
[13] "100000245018012 - Tom Feehan"  
[14] "100000004970313 - Rob Sheahan"  
[15] "1841747558 - Laura Comber"   
[16] "1846686377 - Karen Ni Fhailliun"  
[17] "100000312579635 - Anne Rutherford" 
[18] "100000572764945 - Lit Đ Jsociety" 
[19] "100003033618584 - Fall Ball"   
[20] "100000293776067 - James O'Sullivan" 
[21] "100000104657411 - David Conway" 

, dass die grundlegenden IGRAPH Fragen abdecken würde Sie hatten. Die anderen Fragen sind eher graphentheoretisch. Ich kenne keine Möglichkeit, die Anzahl der Cluster zu überwachen, die mit iGraph erstellt werden, aber jemand kann Sie auf ein Paket aufmerksam machen, das das kann. Vielleicht haben Sie mehr Erfolg, wenn Sie das als separate Frage hier oder an einem anderen Ort veröffentlichen.

In Bezug auf Ihre ersten Punkte des Wunsches, durch alle möglichen Gemeinschaften zu durchlaufen, denke ich, dass Sie finden, dass für ein Diagramm von beträchtlicher Größe undurchführbar sein. Die Anzahl der möglichen Anordnungen des Vektors membership für 5 verschiedene Cluster wäre 5^n, wobei n die Größe des Graphen ist. Wenn du "alle möglichen Gemeinschaften" finden willst, ist diese Zahl tatsächlich O (n^n), wenn meine mentale Mathematik korrekt ist. Im Wesentlichen wäre es unmöglich, dies über ein Netzwerk mit vernünftiger Größe erschöpfend zu berechnen, selbst bei massiven Rechenressourcen. Also denke ich, dass es besser ist, eine Art Intelligenz/Optimierung zu verwenden, um die Anzahl der in Ihrem Diagramm dargestellten Communities zu bestimmen, wie es die clusters-Funktion tut.

Answer 2

In Bezug auf "wie die Anzahl der Communities zu steuern" in OP-Frage, verwende ich die Cut_at-Funktion auf den Communities, um die resultierende hierarchische Struktur in eine gewünschte Anzahl von Gruppen zu schneiden. Ich hoffe, dass jemand bestätigen kann, dass ich etwas Sinnvolles tue. Das heißt, sollten Sie Folgendes beachten:

#Generate graph 
adj.mat<- matrix(,nrow=200, ncol=200) #empty matrix 
set.seed(2) 

##populate adjacency matrix 
for(i in 1:200){adj.mat[i,sample(rep(1:200), runif(1,1,100))]<-1} 
adj.mat[which(is.na(adj.mat))] <-0 

for(i in 1:200){ 
    adj.mat[i,i]<-0 
} 

G<-graph.adjacency(adj.mat, mode='undirected') 
plot(G, vertex.label=NA) 

##Find clusters 
walktrap.comms<- cluster_walktrap(G, steps=10) 
max(walktrap.comms$membership) #43 

    [1] 6 34 13 1 19 19 3 9 20 29 12 26 9 28 9 9 2 14 13 14 27 9 33 17 22 23 23 10 17 31 9 21 2 1 
[35] 33 23 3 26 22 29 4 16 24 22 25 31 23 23 13 30 35 27 25 15 6 14 9 2 16 7 23 4 18 10 10 22 27 27 
[69] 23 31 27 32 36 8 23 6 23 14 19 22 19 37 27 6 27 22 9 14 4 22 14 32 33 27 26 14 21 27 22 12 20 7 
[103] 14 26 38 39 26 3 14 23 22 14 40 9 5 19 29 31 26 26 2 19 6 9 1 9 23 4 14 11 9 22 23 41 10 27 
[137] 22 18 26 14 8 15 27 10 5 33 21 28 23 22 13 1 22 24 14 18 8 2 18 1 27 12 22 34 13 27 3 5 27 25 
[171] 1 27 13 34 8 10 13 5 17 17 25 6 19 42 31 13 30 32 15 30 5 11 9 25 6 33 18 33 43 10 

nun beachten, dass es 43 Gruppen, aber wir wollen gröbere Schnitte daher untersuchen die dendrogram:

plot(as.hclust(walktrap.comms), label=F) 

und schneiden auf ihr basiert. Ich wählte willkürlich 6 Schnitte aber dennoch, Sie haben jetzt gröber Cluster

cut_at(walktrap.comms, no=6) 

    [1] 4 2 5 4 5 5 3 5 3 4 3 5 5 3 5 5 3 1 5 1 1 5 1 6 1 1 1 4 6 5 5 2 3 4 1 1 3 5 1 4 6 6 3 1 5 5 1 1 5 4 3 1 
[53] 5 2 4 1 5 3 6 3 1 6 6 4 4 1 1 1 1 5 1 4 3 3 1 4 1 1 5 1 5 2 1 4 1 1 5 1 6 1 1 4 1 1 5 1 2 1 1 3 3 3 1 5 
[105] 3 3 5 3 1 1 1 1 3 5 2 5 4 5 5 5 3 5 4 5 4 5 1 6 1 3 5 1 1 1 4 1 1 6 5 1 3 2 1 4 2 1 2 3 1 1 5 4 1 3 1 6 
[157] 3 3 6 4 1 3 1 2 5 1 3 2 1 5 4 1 5 2 3 4 5 2 6 6 5 4 5 3 5 5 4 4 2 4 2 3 5 5 4 1 6 1 2 4