R：igraph、コミュニティ検出、edge.betweennessメソッド、各コミュニティのカウント/リストメンバー？

Question

私は実際の取引のVertices：524 Edges：1125という比較的大きなグラフを持っています。エッジは方向付けられており、ウェイトを持っています（包含はオプションです）。 私は、グラフ内の様々なコミュニティを調査しようと、本質的に方法を必要としていた：

-Calculates可能なすべてのコミュニティ

-Calculatesコミュニティ

の最適な数

-Returnsのメンバー/＃ （最適な）コミュニティのメンバー

これまで私は、さまざまなコミュニティに対応する色分けされたグラフをプロットする次のコードをまとめることができましたが、コミュニティの数をどのように制御するかはわかりません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を表します。サンプルデータの場合は、合計586クラスタのIDが0〜585のクラスタがあるようです。

各クラスタの頂点の数を確認するには、clustersも返されたcsizeのコンポーネントを見ることができます（これは、現在使用している色付けスキームを使用して非常に正確に表示できません）。 。この場合、それは長さ586のベクトルであり、計算された各クラスタに対して1つのサイズを記憶する。したがって、あなたのクラスタのサイズのリストを取得するには

clusters(all2)$csize 

を使用することができます。前述のように、clusterIDは0（「ゼロインデックス」）から始まり、Rベクトルは1（「1インデックス」）から開始するので、これらのインデックスを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を使用して作成するクラスタの数を管理する方法はわかりませんが、誰かがそれを行うことができるパッケージを指すことができます。別の質問として、ここまたは別の会場に投稿することで、より多くの成功を収めることができます。

すべての可能性のあるコミュニティを反復したいという最初の点については、大きなサイズのグラフでは実行できないことがわかります。 5つの異なるクラスタに対するmembershipベクトルの可能な配置の数は、5^nであり、nはグラフのサイズである。あなたが "すべての可能なコミュニティ"を探したいなら、私の精神的な計算が正しいなら、その数は実際にはO（n^n）になります。基本的には、大規模な計算リソースを与えられたとしても、合理的な規模のネットワークを網羅的に計算することは不可能です。ですから、clusters関数のように、あなたのグラフに表現されているコミュニティーの数を判断するために、ある種のインテリジェンス/最適化を使う方が良いと思います。

Answer 2

OPの質問の「コミュニティ数の制御」に関しては、コミュニティでcut_at関数を使用して、得られた階層構造を必要な数のグループに分割します。私は誰かが私が何かを正気にしていることを確認できることを願っていますつまり、次の点を考慮してください、それに基づいて

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

カット：今

#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基であるが、我々はそれゆえ粗いカットをしたいことに注意し、系統樹を調べます。私は任意に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