R：igraph，社区检测，edge.betweenness方法，每个社区的count/list成员？

Question

我有一个相对较大的图形，顶点：524边缘：1125，真实世界的交易。边缘是指向和有重量（包含是可选的）。 我试图探讨在图形中的各个社区，基本上需要一个方法，其中：

-Calculates所有可能的社区

-Calculates社区

的最佳数量

- 返回成员/＃的每个（最佳）社区的成员

到目前为止，我已经设法将以下代码绘制成对应于各个社区的彩色编码图，但是我不知道如何控制社区数量（即使用h绘制前5个社区最高成员资格）或列出特定社区的成员。

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) 

---

因为边介方法进行这么差我试图再次使用walktrap方法：

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集群 - 好多了！

现在说我有一个“已知群集”，其成员列表并希望检查每个观察群集中是否存在来自“已知群集”的成员。返回找到的成员的百分比。无法完成以下内容？

list<-read.csv("http://dl.dropbox.com/u/23776534/knownlist.csv") 
ength(all_wt_memb$csize) #19 

for(i in 1:length(all_wt_memb$csize)) 
{ 

match((V(all)[all_wt_memb$membership== i]),list) 

} 

Answer 1

通过仔细查看所使用功能的文档，可以发现上述几个问题。例如，clusters的文档中的“值”部分描述了函数返回的内容，其中的几个回答了您的问题。除了文档外，您还可以使用str函数来分析任何特定对象的构成。

也就是说，要获取特定社区中的成员或成员数量，您可以查看clusters函数（您已用于分配颜色）返回的membership对象。因此类似于：

summary(clusters(all2)$membership) 

将描述正在使用的群集的ID。对于您的示例数据，看起来您拥有ID为0到585的群集，共586个群集。 （请注意，您将不能够很准确地显示那些使用您目前使用的配色方案。）

，以确定每个集群的顶点数量，你可以看看csize组件也由clusters返回。在这种情况下，它是一个长度为586的矢量，为每个计算集群存储一个大小。因此，您可以使用

clusters(all2)$csize 

获取您的群集大小的列表。要注意的是，如前所述，您的clusterIDs从0开始（“零索引”），而R向量从1开始（“单索引”），因此您需要将这些索引加1。例如，clusters(all2)$csize[5]返回ID为4的群集的大小。

要列出任何集群中的顶点，只需查找前面提到的membership组件中的哪些ID与正在讨论的集群匹配。所以，如果我想找到集群＃128的顶点（有这些21，根据clusters(all2)$csize[129]），我可以使用：

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

和检索群集中的顶点，我可以使用V功能并通过在我刚刚计算出的指数，其属于该集群的成员：

> 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" 

这将覆盖你有基本的igraph问题。其他问题更多与图论相关。我不知道有一种方法可以监控使用iGraph创建的群集数量，但是有人可能会指出您有能力做到这一点的软件包。作为一个单独的问题，您可能会在这里或另一个场所发布更多成功信息。

关于你想要遍历所有可能的社区的第一点，我认为你会发现对于一个重要大小的图是不可行的。对于5个不同的簇，membership向量的可能布置的数目将是5^n，其中n是图的大小。如果你想找到“所有可能的社区”，那么如果我的心智数学是正确的，那么这个数字实际上就是O（n^n）。从本质上讲，即使给出了大量的计算资源，也不可能在任何合理大小的网络上详尽计算。所以我认为你会更好地使用某种智能/优化来确定图中表示的社区数量，如clusters函数所做的那样。

Answer 2

关于OPs问题中的“如何控制社区数量”，我使用社区的cut_at函数将产生的层次结构切割成所需数量的组。我希望有人能证实我正在做一些理智的事情。也就是说，考虑以下因素：

#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 

现在，请注意，有43个团体，但我们要削减较粗，因此，检查树状图：基于它

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

和剪切。我任意选择了6个剪辑，但是，现在你有更粗糙的簇

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