2017/08/03 ERATO感謝祭 SeasonIVRandom-Radius Ball Method
for Estimating Closeness Centrality(appeared in AAAI’17)
稲荷場 渉 (東京大学)
秋葉 拓哉 (PFN)
吉田 悠一 (NII & PFI)

中心性 (Centrality)
複雑ネットワークの解析でしばしば気になるのが:Q. どの頂点がより中心的（重要）な役割を持っているか?
Q. ある頂点の影響力は?

頂点の重要性を測る指標を中心性と呼ぶ[https://twitter.com/katyperry]中心性 (Centrality)
複雑ネットワークの解析でしばしば気になるのが:Q. どの頂点がより中心的（重要）な役割を持っているか?
Q. ある頂点の影響力は?

頂点の重要性を測る指標を中心性と呼ぶ► Classic closeness centrality[Bavelas J. Acoust. Soc. Am. ‘50]

► Kats centrality[Kats Psychometrika ‘54]
► Betweenness centrality[Anthonisse ‘71] [Freeman Sociometry ‘77]

► PageRank[Brin-Page Comput. Networks ISDN ‘98]

► Harmonic centrality[Opsahl-Agneessens-Skvoretz Soc. Networks ‘10]
[Boldi-Vigna Internet Math. ‘14]

[http://www.cise.ufl.edu/research/sparse/
matrices/SNAP/soc-LiveJournal1.html]

中心性 (Centrality)
複雑ネットワークの解析でしばしば気になるのが:Q. どの頂点がより中心的（重要）な役割を持っているか?
Q. ある頂点の影響力は?

頂点の重要性を測る指標を中心性と呼ぶ► Classic closeness centrality[Bavelas J. Acoust. Soc. Am. ‘50]

► Kats centrality[Kats Psychometrika ‘54]
► Betweenness centrality[Anthonisse ‘71] [Freeman Sociometry ‘77]

► PageRank[Brin-Page Comput. Networks ISDN ‘98]

► Harmonic centrality[Opsahl-Agneessens-Skvoretz Soc. Networks ‘10]
[Boldi-Vigna Internet Math. ‘14]

1
𝐶𝐶𝑐𝑐𝑐𝑐 𝑣𝑣 ≔∑𝑢𝑢 𝑑𝑑 𝑢𝑢, 𝑣𝑣

他のすべての頂点からの距離の総和(強)連結でないグラフの扱い…?
𝒅𝒅 𝒖𝒖, 𝒗𝒗 ≔ 𝒖𝒖 から 𝒗𝒗 への距離

中心性 (Centrality)
複雑ネットワークの解析でしばしば気になるのが:Q. どの頂点がより中心的（重要）な役割を持っているか?
Q. ある頂点の影響力は?

頂点の重要性を測る指標を中心性と呼ぶ► Classic closeness centrality[Bavelas J. Acoust. Soc. Am. ‘50]

► Kats centrality[Kats Psychometrika ‘54]
► Betweenness centrality[Anthonisse ‘71] [Freeman Sociometry ‘77]

► PageRank[Brin-Page Comput. Networks ISDN ‘98]

► Harmonic centrality[Opsahl-Agneessens-Skvoretz Soc. Networks ‘10]
[Boldi-Vigna Internet Math. ‘14]

1𝐶𝐶𝑐𝑐𝑐𝑐 𝑣𝑣 ≔∑𝑢𝑢 𝑑𝑑 𝑢𝑢, 𝑣𝑣

より洗練された定義

𝟏𝟏
𝑪𝑪 𝒗𝒗 ≔ �𝒖𝒖 𝒅𝒅(𝒖𝒖, 𝒗𝒗)

𝒅𝒅 𝒖𝒖, 𝒗𝒗 ≔ 𝒖𝒖 から 𝒗𝒗 への距離問題定義1
∑𝑢𝑢 12⁄𝑑𝑑 𝑣𝑣𝑣𝑣 ≔ �
調和中心性 (Harmonic centrality): 𝐶𝐶𝐶𝐶(𝑣𝑣)𝑢𝑢 𝑑𝑑(𝑢𝑢, 𝑣𝑣)

Goal: 全頂点の 𝑪𝑪(𝒗𝒗) の計算

全頂点の 𝐶𝐶(𝑣𝑣) が得られれば, 次は容易に計算可能► 頂点ランキングの作成 (または top-𝑘𝑘 頂点の検出)► 各頂点に対する中心性クエリへの応答

ところが… ナイーブな実装は 𝑂𝑂(𝑛𝑛𝑛𝑛)-時間 を要する
► 今日の巨大ネットワークでは動作しない高速な近似アルゴリズムが求められる

𝒏𝒏: 頂点数, 𝒎𝒎: 辺数

貢献
Random-Radius Ball (RRB) 法► 調和中心性に対する新たな近似アルゴリズムを提案
RRB法の基本部

ブートストラップ

精度パラメータを明示的に指定できない指定の精度を満たすまでRRB法の基本部を繰り返す► 理論的解析: 計算量および近似に関する誤差保証► 実データを用いた実験
𝐶𝐶𝛼𝛼 𝑣𝑣 ≔ � 𝛼𝛼 𝑑𝑑 𝑢𝑢, 𝑣𝑣𝑢𝑢

𝛼𝛼 𝑥𝑥 ≥ 0 かつ 𝛼𝛼 ∞ = 0 を満たす単調減少関数

調和中心性以外の指標にも適用可能:► 𝛼𝛼 𝑥𝑥 = 1⁄𝑥𝑥: 調和中心性► 𝛼𝛼 1 = 1, 𝛼𝛼 2 = 0: 頂点の次数既存手法との比較
調和中心性の推定が行える既存手法は2つ:HyperBall [Boldi-Vigna ICDMW ’13]
► 実験的に高速 / HyperLogLog データ構造を利用[Flajolet et al. AofA ’07]

All-Distances Sketches (ADS) [Cohen TKDE ’15]
► さまざまな指標を理論保証付きで推定可能低い
誤差に関する実装の容易さ
メモリ使用量理論保証

RRB法 (提案手法)-HyperBall
All-Distances Sketches--

Random-Radius Ball (RRB) 法
入力: グラフ 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸), パラメータ 0 < 𝑡𝑡 ≤ 1.
foreach vertex 𝑢𝑢 ∈ 𝑉𝑉 do𝜏𝜏 ←𝑡𝑡.
rand()(rand() は 0, 1 の一様な乱数を返すものとする)

頂点 𝑢𝑢 から深さ 𝜏𝜏 の BFS を行い, 訪れた頂点をマーク.

𝒖𝒖 からの BFS が 𝒗𝒗 を訪れる確率が𝒕𝒕となるように設定
𝒅𝒅 𝒖𝒖,𝒗𝒗► rand() ∈ (0,𝑡𝑡] のとき 𝜏𝜏 ≥ 𝑑𝑑(𝑢𝑢, 𝑣𝑣).
𝑑𝑑 𝑢𝑢, 𝑣𝑣

なぜBFSを途中で打ち切るのか?

近い頂点の個数を正確に推定したい
遠い頂点の個数の見積もりは雑でも良いRandom-Radius Ball (RRB) 法
入力: グラフ 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸), パラメータ 0 < 𝑡𝑡 ≤ 1.
foreach vertex 𝑢𝑢 ∈ 𝑉𝑉 do𝜏𝜏 ←𝑡𝑡.
rand()(rand() は 0, 1 の一様な乱数を返すものとする)

頂点 𝑢𝑢 から深さ 𝜏𝜏 の BFS を行い, 訪れた頂点をマーク.

𝒖𝒖 からの BFS が 𝒗𝒗 を訪れる確率が𝒕𝒕となるように設定
𝒅𝒅 𝒖𝒖,𝒗𝒗

例:
左下の赤い頂点からのBFSは► 確率 𝑡𝑡 で青色の領域に到達► 確率 𝑡𝑡⁄2 で橙色の領域に到達► 確率 𝑡𝑡⁄3 で黄色の領域に到達

Random-Radius Ball (RRB) 法
入力: グラフ 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸), パラメータ 0 < 𝑡𝑡 ≤ 1.
foreach vertex 𝑢𝑢 ∈ 𝑉𝑉 do𝜏𝜏 ←𝑡𝑡.
rand()(rand() は 0, 1 の一様な乱数を返すものとする)

頂点 𝑢𝑢 から深さ 𝜏𝜏 の BFS を行い, 訪れた頂点をマーク.

最終的に, ある頂点 𝒗𝒗 がマークされた回数は?
𝑡𝑡= 𝑡𝑡 ⋅ 𝐶𝐶(𝑣𝑣)
𝐄𝐄 𝑣𝑣 のマーク回数 = �𝑢𝑢 𝑑𝑑(𝑢𝑢, 𝑣𝑣)のマーク回数
𝑣𝑣𝑣𝑣のマーク回数̂► 𝐶𝐶 𝑣𝑣 ≔が 𝐶𝐶(𝑣𝑣) の不偏推定量となる!
𝑡𝑡 𝑡𝑡

RRB法の基本部: 解析
𝐶𝐶𝑎𝑎𝑎𝑎𝑎𝑎 を中心性の平均値, また 𝑘𝑘𝑡𝑡 ≔ 𝑡𝑡 ⋅ 𝐶𝐶𝑎𝑎𝑎𝑎𝑎𝑎 と定める.
計算量:► RRB法は 𝑂𝑂 𝑛𝑛 の (追加の) 空間計算量を要する.
max 𝐶𝐶(𝑣𝑣)► 時間計算量は 𝑂𝑂 𝑅𝑅𝑘𝑘𝑡𝑡 𝑚𝑚 , ただし 𝑅𝑅 =.
𝐶𝐶𝑎𝑎𝑎𝑎𝑎𝑎

誤差保証:

グラフがスモールワールドなら𝑹𝑹 は定数► 頂点 𝑣𝑣 が 𝐶𝐶 𝑣𝑣 ≥ 𝐶𝐶𝑎𝑎𝑎𝑎𝑎𝑎 を満たすものとする. このとき,相対誤差の標準偏差=(変動係数; CV)𝜎𝜎 𝐶𝐶̂ 𝑣𝑣

𝐶𝐶(𝑣𝑣)≤1𝑘𝑘𝑡𝑡.

RRB法の基本部: 解析
𝐶𝐶𝑎𝑎𝑎𝑎𝑎𝑎 を中心性の平均値, また 𝒌𝒌𝒕𝒕 ≔ 𝒕𝒕 ⋅ 𝑪𝑪𝒂𝒂𝒂𝒂𝒂𝒂 と定める.
値は一般に分からない

𝒌𝒌𝒕𝒕 が指定できない!

計算量:► RRB法は 𝑂𝑂 𝑛𝑛 の (追加の) 空間計算量を要する.
► 時間計算量は 𝑂𝑂 𝑅𝑅𝒌𝒌𝒕𝒕 𝑚𝑚 , ただし 𝑅𝑅 =max 𝐶𝐶(𝑣𝑣).
𝐶𝐶𝑎𝑎𝑎𝑎𝑎𝑎

パラメータ 𝒌𝒌𝒕𝒕 が計算量と精度の両方を定める誤差保証:► 頂点 𝑣𝑣 が 𝐶𝐶 𝑣𝑣 ≥ 𝐶𝐶𝑎𝑎𝑎𝑎𝑎𝑎 を満たすものとする. このとき,相対誤差の標準偏差=(変動係数; CV)𝜎𝜎 𝐶𝐶̂ 𝑣𝑣

𝐶𝐶(𝑣𝑣)≤1𝒌𝒌𝒕𝒕.

“ブートストラップ” 法
問題: パラメータ 𝑘𝑘𝑡𝑡 を制御する方法はあるか?

解決策: RRB法を実行した結果を基に 𝑘𝑘𝑡𝑡 を “推定” する“ブートストラップ” の枠組み

精度パラメータ 𝑘𝑘 ∗ を選択
𝑡𝑡 を十分小さな値で初期化
RRB法の基本部を実行どう判定する?

𝐶𝐶𝑎𝑎𝑎𝑎𝑎𝑎 と 𝑘𝑘𝑡𝑡 を推定

𝑘𝑘𝑡𝑡𝒕𝒕 が 𝑘𝑘𝒌𝒌𝒌𝒌∗ より十分大きそうか?

NoYes𝒕𝒕 ← 𝟐𝟐𝟐𝟐
終了

“ブートストラップ” 法: 解析
𝑘𝑘𝑡𝑡 の推定値
�𝒕𝒕 ≥ 𝒌𝒌∗ + 𝒔𝒔 𝒌𝒌∗ のとき, 𝑘𝑘𝑡𝑡 が 𝑘𝑘 ∗ より大きそうと判断
基準: 𝒌𝒌ブートストラップ法のパラメータ

時間計算量:► 𝑂𝑂 𝑅𝑅 𝑘𝑘 ∗ + 𝟐𝟐 + 𝒔𝒔
誤差保証:𝒌𝒌∗ 𝑚𝑚 -時間 で動作. (Thm. 10)

時間計算量はほぼ増加しない► 頂点 𝑣𝑣 が 𝐶𝐶 𝑣𝑣 ≥ 𝐶𝐶𝑎𝑎𝑎𝑎𝑎𝑎 を満たすものとする. このとき,
𝜎𝜎 𝐶𝐶̂ 𝑣𝑣

𝐶𝐶(𝑣𝑣)≤

1

𝑘𝑘 ∗が 確率 𝟏𝟏 − 𝟒𝟒⁄𝒌𝒌∗ − 𝟏𝟏⁄𝒔𝒔𝟐𝟐 以上で 成り立つ. (Thm. 9)

わずかなオーバーヘッドで精度の制御が可能に実験: 既存手法との比較
計算時間と精度のトレードオフ
soc-Slashdot0902 (Social)
𝑛𝑛 = 82,168 𝑚𝑚 = 948,464

web-NotreDame (Web)𝑛𝑛 = 325,729 𝑚𝑚 = 1,497,134

約10倍高速► RRB法は既存手法より優れた性能► Permutation-rank 法 (PR) を用いると実験的な精度は改善 (理論保証は無し)(Intel Xeon E5540 processors (2.53GHz), 48GiB RAM, single-threaded)実験: スケーラビリティ
ブートストラップ法 (𝒌𝒌∗ = 𝟏𝟏𝟏𝟏𝟏𝟏, 𝒔𝒔 = 𝟑𝟑)
データセット

種別

頂点数

辺数

時間 (秒)

web-Google

Web876 K

5.1 M

24.69

3.90%

com-youtube

Social

1.1 M

6.0 M

20.99

2.38%

dblp-2001

Social

933 K

6.7 M

29.65

2.92%

ego-Gplus

Social

108 K

14 M

10.10

4.83%

in-2004

Web

1.4 M

17 M

27.49

5.84%

soc-Pokec

Social

1.6 M

31 M

107.93

3.67%

soc-LiveJournal1

Social

4.8 M

69 M

278.03

2.54%

enwiki-2013

Social

4.2 M

101 M

223.64

1.72%► 1億辺規模のネットワークも取り扱える► 理論保証の 10% (= 1⁄ 100) よりも実際の誤差は小さい(Intel Xeon E5540 processors (2.53GHz), 48GiB RAM, single-threaded)

誤差実験: スケーラビリティ
ブートストラップ法 (𝒌𝒌∗ = 𝟏𝟏𝟏𝟏𝟏𝟏, 𝒔𝒔 = 𝟑𝟑)
データセット

種別

頂点数

辺数

時間 (秒)

web-Google

Web876 K

5.1 M

24.69

3.90%

com-youtube

Social

1.1 M

6.0 M

20.99

2.38%

dblp-2001

Social

933 K

6.7 M

29.65

2.92%

ego-Gplus

Social

108 K

14 M

10.10

4.83%

in-2004

Web

1.4 M

17 M

27.49

5.84%

soc-Pokec

Social

1.6 M

31 M

107.93

3.67%

soc-LiveJournal1

Social

4.8 M

69 M

278.03

2.54%

enwiki-2013

Social

4.2 M

101 M

223.64

1.72%► 1億辺規模のネットワークも取り扱える► 理論保証の 10% (= 1⁄ 100) よりも実際の誤差は小さい(Intel Xeon E5540 processors (2.53GHz), 48GiB RAM, single-threaded)

誤差

厳密な計算には24スレッド×2日半を要した

まとめ
距離に基づく中心性の推定が高速に行える
random-radius ball (RRB) 法 を提案► 特に頂点ランキングの上位を求めるような応用に適する
今後の可能性► RRB法の応用範囲は中心性に限らない:
少しの変更で closeness similarity (近接類似性) も推定可能[Cohen et al. COSN ‘13]

詳細な比較 𝑘𝑘, 𝑠𝑠: 計算量と精度のトレードオフパラメータ
時間計算量

RRB法
HyperBallADS𝑂𝑂

𝑘𝑘 + 2 + 𝑠𝑠

𝑘𝑘 𝑚𝑚 ⋅max 𝐶𝐶 𝑣𝑣
𝐶𝐶𝑎𝑎𝑎𝑎𝑎𝑎

𝑂𝑂 𝑘𝑘𝑘𝑘 ⋅ diam 𝐺𝐺

𝑂𝑂 𝑘𝑘 𝑚𝑚 + 𝑛𝑛 log 𝑘𝑘 log 𝑛𝑛

空間

誤差保証 (CV)𝑂𝑂(𝑛𝑛)≤ 1⁄ 𝑘𝑘 ∀𝑣𝑣 s.t. 𝐶𝐶 𝑣𝑣 ≥ 𝐶𝐶𝑎𝑎𝑎𝑎𝑎𝑎

𝑂𝑂 𝑘𝑘𝑘𝑘
𝑂𝑂 𝑘𝑘𝑘𝑘with prob. 1 − 4⁄𝑘𝑘 − 1⁄𝑠𝑠 2≤ 𝑂𝑂 1⁄ 𝑘𝑘

ただし実験的にのみ≤ 1⁄ 2 𝑘𝑘 − 1