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