被覆中心性 - Researchmap

Almost Linear-Time Algorithms for
Adaptive Betweenness Centrality
using Hypergraph Sketches
KDD 2014, to appear
𠮷田悠一
国立情報学研究所
ERATO河原林巨大グラフプロジェクト・
感謝際Summer 2014/8/8
中心性
• 頂点の中心性 ≈ その頂点がどれだけ重要か？
ネットワーク科学で非常に重要な概念
• 最短路に基づいた中心性
沢山の最短路が通る ⇒ その頂点は重要
– 被覆中心性
– 媒介中心性
– 近接中心性
被覆中心性
頂点vの被覆中心性C(v):
何割のペアの最短路中にvが含まれるか
v
被覆中心性
頂点vの被覆中心性C(v):
何割のペアの最短路中にvが含まれるか
t
v
s
被覆中心性
頂点vの被覆中心性C(v):
何割のペアの最短路中にvが含まれるか
v
t
s
被覆中心性
頂点vの被覆中心性C(v):
何割のペアの最短路中にvが含まれるか
v
t
s
C(v) = #{(s, t) : s-t間の最短路がvを通る} / n2
媒介中心性
頂点vの媒介中心性B(v)
各ペアについて何割の最短路がvを通るかも考慮
t
v
s
(s, t)は1/2だけ加味される
被覆・媒介中心性の応用
コミュニティ検出 [Girvan-Newmanのアルゴリズム]
• 一番媒介中心性が高い頂点を選ぶ
被覆・媒介中心性の応用
コミュニティ検出 [Girvan-Newmanのアルゴリズム]
• 一番媒介中心性が高い頂点を選ぶ
被覆・媒介中心性の応用
コミュニティ検出 [Girvan-Newmanのアルゴリズム]
• 一番媒介中心性が高い頂点を選ぶ
• その頂点を取り除く
被覆・媒介中心性の応用
コミュニティ検出 [Girvan-Newmanのアルゴリズム]
• 一番媒介中心性が高い頂点を選ぶ
• その頂点を取り除く
• 同じことを(例えばk回)繰り返す
被覆・媒介中心性の応用
コミュニティ検出 [Girvan-Newmanのアルゴリズム]
• 一番媒介中心性が高い頂点を選ぶ
• その頂点を取り除く
• 同じことを(例えばk回)繰り返す
被覆・媒介中心性の応用
コミュニティ検出 [Girvan-Newmanのアルゴリズム]
• 一番媒介中心性が高い頂点を選ぶ
• その頂点を取り除く
• 同じことを(例えばk回)繰り返す
被覆・媒介中心性の応用
• ワクチン投与
• グラフ上の二点間の最短距離を答える為のイン
デクシング手法
– PLL (秋葉さんの講演･動画を参照)
適応的中心性
最初に全頂点の中心性を計算するのでは駄目
頂点の影響を取り除きながら中心性を適応的に再
計算したい！
既存手法は遅い
被覆中心性
厳密手法
O(kn2m)
近似手法
Õ(knm/ε2)
媒介中心性
O(knm) [Bra01]
Õ(knm/ε2) [BP08]
近似：毎回中心性を±εで近似する
我々の貢献
適応的中心性に基づく頂点順番を
ほぼ線形時間で求める！
計算量
任意のkに対して
• 被覆中心性: O((n + m)log n /ε2)
• 媒介中心性: 実用上O((n + m)log n/ε2)
(ε : error parameter)
我々の貢献
適応的中心性に基づく頂点順番を
ほぼ線形時間で求める！
理論保証
得られる頂点順番は関連する最適化問題に対する
(1-1/e -ε)-近似解となっている
実験による確認
• 厳密手法に”近い”頂点順番を求める
• 素朴な近似手法の1000倍以上高速になることも
頂点集合の被覆中心性
• 頂点集合S ⊆ Vの被覆中心性C(S)
= S中の何れかの頂点に被覆されたペアの割合
t
t’
s
s’
(s, t)も(s’, t’)も加味される
問題の言い換え
以下の手順で得られる頂点順を計算したい
for i = 1 to k:
vi ← argmaxv C(v, v1,…,vi -1) – C(v1,…,vi -1).
貪欲に被覆中心性を大きくする頂点を選んでいる
⇒ 最も良い大きさkの頂点集合の(1-1/e)倍の被覆中
心性が得られる (劣モジュラ性より)
提案手法：ハイパーグラフによるスケッチ
以下の手順でハイパーグラフHを作成
for i = 1 to M = O(log n/ε2):
ペア (s, t)をランダムに選ぶ
s-t間の最短路(DAG)を計算しHに加える
計算量: O((n+m)M).
提案手法：適応的被覆中心性の計算
以下の手順で頂点順番を求める
for i = 1 to k :
vi ← argmaxv dH-{v1,…,vi-1}(v).
v2
v1
ハイパーグラフ中の次数を保持するだけで良い！
⇒ 計算量: O((n+m)M).
正しさ
dH(v): 頂点vのハイパーグラフHにおける次数
1. E[dH(v) / M] = C(v)
2. E[dH-S(v) / M] = C(S + v) – C(S)
証明
1. Pr[dH(v)が+1される確率] = C(v)
2. Pr[dH-S(v)が+1される確率] = C(S+v) - C(S)
1.よりC(v)はdH(v)/Mで近似できる。
2.よりC(S+v)-C(S)もHからSを削除すれば近似できる
実験
厳密手法に対する中心性の大きさ
データセット: p2p-Gnutella
k vs 被覆中心性
M = 4K or 16Kで十分
k vs 媒介中心性
小さいグラフに対する計算時間の比較
枝数<20Kまでのグラフで実験
k = nでは既存の(近似)手法と比べて1000倍以上高速
Intel Xeon E5-2690 (2.90 GHz) processor and 256 GB
大きいグラフに対する計算時間
• 枝数<10Mまでのグラフで実験
• もう少し速く出来ると良い？
道路ネットワークの距離クエリへの応用
• PLL[AIY’13]は道路ネットワークが非常に苦手
頂点順番を次数順にしているから
• 頂点順番を変えるだけで性能改善するか？
適応的被覆中心性で大幅に索引構築時間・サイズ
が改善された
まとめ
「被覆・媒介中心性の高い頂点を適応的に
選ぶことで得られる頂点順」・・・(*)
をほぼ線形時間で求める手法を提案
• 精度に対して理論保証
• k = nの時は1000倍以上の高速化
• 大規模なグラフでの(*)の有用性の確認

Download Report