R：igraph，社区检测，edge.betweenness方法，如何计算/列出每个社区的成员？

Question

R：igraph，社区检测，edge.betweenness方法，如何计算/列出每个社区的成员？

rigraphmodularity

10

我有一个相对较大的图，其中顶点数为524，边数为1125，包含真实世界的交易。这些边是有向的，具有权重（可选）。

我正在尝试探索图中的各种社区，并需要一种方法来：

- 计算所有可能的社区

- 计算最佳社区数量

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

到目前为止，我已经成功编写了以下代码，可以绘制颜色编码图，对应不同的社区，但是我不知道如何控制社区的数量（即绘制具有最高成员资格的前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)

由于边介数法表现不佳，我试着再次使用走陷法方法：

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)

}

- Sean Mc

你能提供创建 all 对象的代码吗？如果太大的话，至少提供一个小版本的代码也行。我很难重新创建这个问题。 - Jeff Allen

@JeffAllen，抱歉我添加了一些Facebook数据样本，实际上我正在处理的数据大小是这个样本的50倍..谢谢。 - Sean Mc

@JeffAllen，非常感谢您的帮助。您会注意到我已经更改了社区检测方法以提高性能。您有什么建议可以解决我的匹配问题吗？ - Sean Mc

当然没问题。我开始对修改后的问题和目标感到有些困惑了。我建议将所有内容缩减为一个或两个明确的问题，并提出一个新的问题。 - Jeff Allen

@JeffAllen，没问题链接谢谢！ - Sean Mc

2个回答

1

关于OP问题中“如何控制社区数量”的问题，我使用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

- Gene Burinsky

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jeff Allen · Accepted Answer

一些问题可以通过仔细查看您正在使用的函数的文档来发现。例如，clusters 的文档中的“Values”部分描述了该函数将返回什么，其中有几个回答了您的问题。除了文档之外，您始终可以使用str函数来分析任何特定对象的构成。

话虽如此，要获取特定社区的成员或成员数量，您可以查看由clusters函数返回的membership对象（您已经使用它来分配颜色）。所以像这样：

summary(clusters(all2)$membership)

这段内容描述正在使用的聚类ID。对于您的示例数据，看起来您有的聚类ID范围从0到585，总共有586个聚类。（请注意，您目前使用的着色方案可能无法准确显示它们。）

要确定每个聚类中顶点的数量，可以查看由clusters返回的组件。在这种情况下，它是长度为586的向量，存储每个计算出的聚类大小。因此，您可以使用以下方法：

clusters(all2)$csize

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

要列出任何集群中的顶点，您只需要找到先前提到的membership组件中与所讨论的集群相匹配的ID。因此，如果我想查找第128个集群中的顶点（根据clusters(all2)$csize[129]有21个），我可以使用：

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监督要创建的簇数，但是也许有人能够指出一个能够实现这一点的软件包。您可以尝试在此处或其他场所发布这个作为单独的问题，或许会有更好的结果。

关于您想要遍历所有可能社区的第一个要点，我认为您会发现对于规模显著的图形来说这是不可行的。针对五个不同簇的membership向量的可能安排数量将是5 ^ n，其中n是图形的大小。如果您要查找“所有可能的社区”，那么该数字实际上将是O（n ^ n），如果我的心算正确的话。从本质上讲，即使在具有大量计算资源的情况下，在任何合理的大小网络上都无法详尽地计算它。因此，我认为您最好使用某种智能/优化来确定图形中表示的社区数量，如clusters函数所做的那样。