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

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)

http://gyazo.com/6e70dbe0863e761c7a5976f11c580827.png

何となく、以下のようなコミュニティがありそう

http://gyazo.com/61d2e70fc24c76063de45a477215efaa.png

辺の媒介中心性

[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)

http://gyazo.com/a5d9129e2f366971bcc45853a3d2d8db.png

辺の媒介中心性による分割

媒介中心性が最大になるエッジを取り除いて分割、というのを繰り返す

> (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)

http://gyazo.com/0e2fe0707e4cc931ddba9acc61f23b49.png

デンドログラムを任意のステップ数で切れば、いくつかのコミュニティが形成される
見方としては以下のような感じで、各ステップ数でのコミュニティが分かる

http://gyazo.com/4d30c11708259a88e8ec0694792fedff.png

モジュラリティ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)

http://gyazo.com/0862ec281480ad1a26a2d5db2d968150.png

任意の数で分割

モジュラリティ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)

http://gyazo.com/2b8f208baae4820c3fa278f67ec4d277.png

参考