ネットワーク構造の分析 - コミュニティの抽出
ある程度の規模のネットワークでは、内部にサブネットワーク(コミュニティ)が形成されることがある
例えば、大学のネットワーク図を描くと、何となく学部だったりサークルのグループが見えてくる
このよなコミュニティの抽出方法として、辺の媒介中心性を用いた方法があるので、その方法とRでの実行を紹介する
データの入力と描画
g <- graph(c( 1,2, 1,3, 1,4, 1,5, 1,9, 2,3, 2,4, 3,4, 5,6, 5,7, 5,9, 6,7, 6,8, 7,8) - 1, n = 9, directed = FALSE)
plot(g,layout=layout.lgl)
何となく、以下のようなコミュニティがありそう
辺の媒介中心性
[R][ネットワーク分析] ネットワークにおいてどれくらい中心的かの指標 - yokkunsの日記の媒介中心性を、エッジに適用したもの。
ある人とある人のつながりを除外すると、コミュニティ間のつながりがなくなったり、遠くなるようなつながりのスコアが高くなる
Rでは、igraphパッケージのedge.betweenness関数で計算出来る
(g.edge.betweenness <- edge.betweenness(g, directed=FALSE)) [1] 6 6 6 16 4 1 1 1 9 9 4 1 4 4
エッジに媒介中心性の値を入れると以下のような感じ
plot(g,layout=layout.fruchterman.reingold,edge.label=g.edge.betweenness)
辺の媒介中心性による分割
媒介中心性が最大になるエッジを取り除いて分割、というのを繰り返す
> (eb <- edge.betweenness.community(g)) $removed.edges [1] 3 4 10 8 9 0 1 2 5 6 7 11 12 13 $edge.betweenness [1] 16.0 20.0 4.0 1.5 3.0 1.0 1.5 3.0 1.0 2.0 1.0 1.0 2.0 1.0 $merges [,1] [,2] [1,] 6 7 [2,] 5 9 [3,] 2 3 [4,] 1 11 [5,] 0 12 [6,] 4 10 [7,] 14 8 [8,] 13 15 $bridges [1] 14 13 11 10 8 5 3 2 attr(,"class") [1] "igraph.ebc"
eb$mergeは各ノードが合同してコミュニティを形成してく過程を示している。
最初は各ノードが1つのコミュニティの状態からはじまり、6と7がつながって9というコミュニティを生成、次に、5とそのコミュニティが合同して・・・という流れ。
この様子は、デンドログラムの方が分かりやすい
dend <- as.dendrogram(eb) plot(dend)
デンドログラムを任意のステップ数で切れば、いくつかのコミュニティが形成される
見方としては以下のような感じで、各ステップ数でのコミュニティが分かる
モジュラリティQ
辺の媒介中心性を用いることで、任意のコミュニティ抽出が出来る事が分かったが、どのステップ数が最適なのかは分からない
何をもって最適とするかは難しいが、一つの手がかりとして、分割されたコミュニティ内のつながり具合と、コミュニティ間のつながり具合を比較するモジュラリティQという指標がある
とりあえず、モジュラリティQが最大になる分割
# モジュラリティQが最大になる分割 wt <- walktrap.community(g,modularity=T) memb <- community.to.membership(g, wt$merges, steps=which.max(wt$modularity)-1) # コミュニティ毎に色を設定 V(g)$color <- rainbow(length(memb$csize))[memb$membership+1] # ネットワーク図の描画 plot(g, layout=layout.fruchterman.reingold, edge.arrow.size=0.5)
任意の数で分割
モジュラリティQは、一つの手がかりにはなるが、普遍的な妥当性を持っている訳でない
今回の例では、ネットワーク図やデンドログラムを見ると、8番は別のコミュニティ(1人だけど)として見た方が自然だと思われる
# 6ステップでコミュニティ分割 memb2 <- community.to.membership(g, eb$merges, steps=6) # コミュニティ毎に色を設定 V(g)$color <- rainbow(length(memb2$csize))[memb2$membership+1] # ネットワーク図の描画 plot(g, layout=layout.fruchterman.reingold, edge.arrow.size=0.5)