What Is a Network Community?
A Novel Quality Function and Detection Algorithms
宮内 敦史

河瀬 康志

東京工業大学

ERATO 感謝祭 Season III

Kawarabayashi Large Graph Project

1 / 27

CIKM 2015
The 24th ACM International Conference on Information andKnowledge Management• 期間: 10 月 19 日から 23 日
• 場所: Melbourne Convention and Exhibition Centre

2 / 27

CIKM 2015 の採択率
3 つのトラックに分かれて論文を募集• Database• Long: 35/129 = 27%• Short: 6/37 = 16%• Information Retrieval• Long: 43/171 = 25%• Short: 27/101 = 27%• Knowledge Management• Long: 87/346 = 25% ← 本研究• Short: 36/138 = 26%(Long paper: 10 ページ，Short paper: 4 ページ)
3 / 27

はじめに4 / 27

コミュニティ検出
ネットワーク上の “まとまりらしい部分” をコミュニティと呼ぶ

様々なネットワークに存在• ソーシャルネットワーク• Web グラフ
• タンパク質ネットワーク• etc.

ネットワーク解析における基本的かつ重要な操作

5 / 27

評価関数“コミュニティらしさ” を数値で返す関数
頂点集合の分割に対して頂点部分集合に対して

C3

S

C1
C2

f (C) = ???

f (S) = ???

頂点部分集合に対する評価関数に着目• 多くのコミュニティ検出法で用いられている• クラスタリング結果の整理のためにも利用できる
6 / 27

評価関数
記号• e[S] := S 内の枝数
• cut[S] := S のカット枝の本数• D[S] := S 内の頂点の次数和S e[S] = 6cut[S] = 2
D[S] = 14

既存の評価関数• DS(S) =2e[S]|S|平均次数)|S|• OQC(S) = e[S] − α2
• COND(S) =(OQC 関数 (Tsourakakis et al. ’13)

cut[S]
min{D[S], D[V \ S]}

コンダクタンス

標準的な評価関数として定着しているものはない
7 / 27

本研究の成果

頂点部分集合に対する評価関数コミュニチュードを提案• コミュニチュード最大化問題• 線形時間ヒューリスティック• 実験的評価

8 / 27

コミュニチュード

9 / 27

コミュニチュードの考え方
モジュラリティ(Newman & Girvan ’04) という評価関数を参考にする
頂点集合の分割 C = {C1 , . . . , Ck } に対して()∑ e[C] ( D[C] )2
Q(C) =−m2mC∈CC3C1(m: グラフの枝数)

C2• モジュラリティの値が高い ≈ コミュニティらしく分かれている• 頂点集合の分割に対する標準的な評価関数

モジュラリティの “頂点部分集合バージョン” を作る
10 / 27

コミュニチュードの考え方
単純な関数はすでに存在 (Leskovec et al. ’10)

e[S]Q(S) =−m(D[S]2m)2S• モジュラリティから一つの項を抜き出した• S ⊆ V 内の枝の割合がランダムと比べてどれだけ大きいかを評価優れている点e[S] だけでなく cut[S] の大きさも間接的に考慮
問題点
多くの実ネットワークでは，S ⊆ V を |S| ≈ |V |/2 まで大きくしていくと，関数値がほぼ単調に増加 (Leskovec et al. ’10)

Leskovec の関数 Q(S) を適切に修正する
11 / 27

コミュニチュードの考え方
枝の生成過程次数分布に従って，頂点集合 V 上に N 本の枝をランダムに生成
枝を 1 本生成するとき，その枝が S ⊆ V 内に生成される確率は)(D[S] 2p=2mS ⊆ V 内に生成される枝の割合が従う確率分布を観察
X : 上記の過程で S ⊆ V 内に生成される枝の本数を表す確率変数• X ∼ B(N, p)• 中心極限定理より，X ∼ N (Np, Np(1 − p))• よって，X /N ∼ N (p, p(1 − p)/N)

S ⊆ V 内の実際の枝の割合がランダムと比べてどれだけ大きいか？
12 / 27

コミュニチュード
コミュニチュードは，分散も考慮して評価
e[S]−mcom(S) =√(D[S]2m(D[S]2m)2Leskovec の関数 Q(S))2 (()2 )D[S]1 − 2m

標準偏差• S ⊆ V 内の実際の枝の割合 e[S]m の Z 値を計算
• com(S) が高いほど，S ⊆ V はコミュニティらしいコミュニチュードは，重み付きグラフに対しても同様に定義できる

13 / 27コミュニチュード最大化問題• 入力: G = (V , E)
• 出力: S ⊆ V that maximizes com(S)応用を考慮して，制約付き問題も定義
サイズ制約付き• 入力: G = (V , E) & kmin , kmax ∈ Z>0• 出力: S ⊆ V that maximizes com(S) under kmin ≤ |S| ≤ kmax

クエリノード付き• 入力: G = (V , E) & Q ⊆ V• 出力: S ⊆ V that maximizes com(S) under Q ⊆ S
14 / 27

アルゴリズム

15 / 27線形時間ヒューリスティック
1st Phase: Greedy peeling + 2nd Phase: Local search
1st Phase: Greedy peeling1: 次数最小の頂点を逐次除去し，頂点部分集合の列を得る
2: そのなかで目的関数値が最大の S ⊆ V を出力
コミュニティ検出や密グラフ抽出において有用
精度保証

実行時間

平均次数1/2 (Charikar ’00)

O(m + n)OQC 関数

加法的 (Tsourakakis et al. ’13)

O(m + n)(n: グラフの頂点数)
コミュニチュード最大化問題に対しても，実行時間は O(m + n)
16 / 27線形時間ヒューリスティック
Greedy peeling で得た解 S ⊆ V を改善
2nd Phase: Local search
1: すべての頂点をランダムに並べ，それを順に見ていく
各頂点 v について，目的関数値が改善されるならば，
v を S 内へ移動 (あるいは S 外へ移動)
2: 以下のどちらかを満たすまで，上記の操作を繰り返す(i) 局所最適解が得られる(ii) 繰り返し回数が Tmax を超える
3: 全体の操作を Rmax 回繰り返し，最良解を出力
実行時間は O((m + n) · Tmax · Rmax )計算機実験では，Tmax = ∞, Rmax = 10 と設定
17 / 27

制約付き問題に対するアルゴリズム

線形時間ヒューリスティックを改造
サイズ制約付き

1st Phase: 制約 kmin ≤ |S| ≤ kmax を満たす初期解 S ⊆ V を得る
2nd Phase: サイズ制約を破る移動はスキップ
クエリノード付き

1st Phase: Greedy peeling は行わず，クエリノードを初期解に設定
2nd Phase: クエリノードに関する移動はスキップ

18 / 27

計算機実験

19 / 27

単一コミュニティモデル
コミュニティが 1 個埋め込まれている疎なグラフ

Parameters:• n: 頂点数 ← 1000
• c: コミュニティサイズ ← 50 or 100• pin : コミュニティ内の枝の生起確率 ← 0.2 or 0.4• pout : コミュニティ外の枝の生起確率 ← 0.01, . . .

S∗

G = (V , E)

Algorithms:
各評価関数を目的関数として，Greedy peeling + Local search

Evaluation: Jaccard 係数
J(S, S ∗ ) =|S ∩ S ∗ ||S ∪ S ∗ |20 / 27

単一コミュニティモデル
1COMQDSOQC
COND

0.8
0.60.4

Jaccard index

0.2(a) n=1000, c=50 pin=0.2(b) n=1000, c=50, pin=0.4

00.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2

1
0.8
0.6
0.4
0.2
(c) n=1000, c=100, pin=0.2(d) n=1000, c=100, pin=0.4

00.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1

0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2

Probability pout

• ほとんどの場合で，COM が最も正確に S ∗ を検出• OQC も健闘しているが，パラメータ pin に強く依存

21 / 27

LFR ベンチマーク
サイズが異なる複数のコミュニティをもつグラフ

Parameters:• n: 頂点数 ← 1000 or 5000
• γ: 次数分布のべき指数 ← −2
• β: コミュニティサイズの分布のべき指数 ← −1
• d: 平均次数 ← 20
G = (V , E)
• dmax : 最大次数 ← 50
• (cmin , cmax ): コミュニティサイズの下界と上界 ← (10, 50) or (20, 100)
• µ: 混合パラメータ ← 0.05, . . .

Algorithms:
各評価関数を目的関数として，クエリノードに対して Local search

Evaluation:

J(S, S ∗ ) =|S ∩ S ∗ ||S ∪ S ∗ |22 / 27

LFR ベンチマーク
サイズが異なる複数のコミュニティをもつグラフ

Parameters:∗S• n: 頂点数 ← 1000 or 5000
• γ: 次数分布のべき指数 ← −2
• β: コミュニティサイズの分布のべき指数 ← −1
• d: 平均次数 ← 20
G = (V , E)
• dmax : 最大次数 ← 50
• (cmin , cmax ): コミュニティサイズの下界と上界 ← (10, 50) or (20, 100)
• µ: 混合パラメータ ← 0.05, . . .
Algorithms:
各評価関数を目的関数として，クエリノードに対して Local search

Evaluation:

J(S, S ∗ ) =|S ∩ S ∗ ||S ∪ S ∗ |22 / 27

LFR ベンチマーク
10.8
0.60.4

Jaccard index0.2(a) n=1000, cmin=10, cmax=50(b) n=1000, cmin=20, cmax=100

00.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5

0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5

10.8
0.6
0.4
0.2

COMQDSOQC
COND(c) n=5000, cmin=10, cmax=50(d) n=5000, cmin=20, cmax=100

00.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5

0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5

Mixing parameter +• コミュニティが小さいとき，COM と OQC が最良の検出性能• コミュニティが大きいとき，COM が最も正確に S ∗ を検出

23 / 27

実ネットワーク
Algorithm:
コミュニチュードを目的関数として，Greedy peeling + Local search
Networkcom(S)

|S|

e[S]

cut[S]

LesmisPolbooks
Football
Polblogs
AS-22july06
web-Stanford
DBLP
web-Google
AS-Skitter
LiveJournal

0.578
0.579
0.665
0.515
0.569
0.865
0.902
0.939
0.729
0.957

1541
9
500
7,277
5,749
494
184
157,216
9,323

64
176
36
6,904
12,572
227,449
15,3893,172
2,570,493
1,003,448

2320
25
1,333
4,510
11,142
2,765
408
265,258
27,817• ほとんどの場合で e[S] ≫ cut[S] (特に com(S) が高いときに顕著)• 400 万頂点のネットワークに対しても 20 分程度
24 / 27

Les Misérables ネットワーク

S1 : “ABC の友”

S2 : 第 1 章の登場人物
25 / 27

おわりに

26 / 27

まとめと今後の課題

頂点部分集合に対する評価関数コミュニチュードを提案• コミュニチュード最大化問題• 線形時間ヒューリスティック• 実験的評価今後の課題• 計算困難性の解析• コミュニチュードを用いた実ネットワークの解析

27 / 27