yokkunsの日記

< [R][ネットワーク分析] ネット... | 第26回TokyoRでData Fusionにつ...>

2012-08-19

ネットワーク構造の分析 - コミュニティの抽出

R, ネットワーク分析

ある程度の規模のネットワークでは、内部にサブネットワーク（コミュニティ）が形成されることがある

例えば、大学のネットワーク図を描くと、何となく学部だったりサークルのグループが見えてくる

このよなコミュニティの抽出方法として、辺の媒介中心性を用いた方法があるので、その方法と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)