2016/08/10 ERATO 感謝祭 Season III

Dynamic Influence Analysis
in Evolving Networks
42nd International Conference on Very Large Data Bases
Proceedings of the VLDB Endowment, 9(12):1077–1088, 2016

大坂 直人 (東京大学)
秋葉 拓哉 (PFN)𠮷田 悠一 (NII & PFI)
河原林 健一 (NII)1

VLDBについて

42nd International Conference on
本部がインドVery Large Data Bases▶ 2016/9/5～9/9 @ ニューデリー，インド▶ 採択論文数: 104※41stの採択率＝20%

利用サービス：Wordle http://www.wordle.net/

http://vldb2016.persistent.com/ より転載

2

はじめに

ネットワーク上の拡散
噂・口コミ
意見
感染症
イノベーション
汚染

オンラインソーシャルネットワークの台頭
2000年～ 膨大な個人単位の履歴が直ぐに手に入る
人々の過程と活動を理解・予測・制御したい！
モデル化
パラメタ学習ネットワーク推定
拡散の将来予測
デマ拡大防止[Rodriguez-Balduzzi-Schölkopf. ICML'11][Goyal-Bonchi-Lakshmanan. WSDM'10][Rodriguez-Leskovec-Krause. KDD'10][Cheng-Adamic-Dow-Kleinberg-Leskovec. WWW'14][Budak-Agrawal-Abbadi. WWW'11]

我々: グラフアルゴリズム的問題に焦点

3

はじめに取り組む2つの問題

試供品

試供品

影響最大化
[Kempe-Kleinberg-Tardos. KDD'03]

Q. 拡散が最も広がる集団はどれ？
バイラルマーケティングへの応用[Domingos-Richardson. KDD'01]

試供品

影響力推定
Q. この集団の拡散力はどれくらい？

今回の話：

巨大・動的グラフ上の計算効率への挑戦

4

はじめに計算効率の観点での挑戦
使用データセット

1. グラフが巨大

YouTube 320万点 1,880万辺
Flickr 230万点 3,310万辺百万点超 ⇝ 𝓞(点数2)時間は✘
私の取組 [Ohsaka-Akiba-Yoshida-Kawarabayashi. AAAI'14] (感謝祭'14)
友達関係の成立・解消

2. グラフが動的・成長

最新の解析結果を追跡したい
静的手法の逐次適用 ⇝ 線形時間以上[Hayashi-Akiba-Yoshida. VLDB'16] 媒介中心性[Ohsaka-Maehara-Kawarabayashi. KDD'15] PageRank (感謝祭'15)[Akiba-Iwata-Yoshida. WWW'14] 最短経路クエリ (感謝祭'14)
5

はじめに

これまでの状況
1. グラフが巨大
 およそ解決

ほぼ線形時間近似手法の登場[Borgs-Brautbar-Chayes-Lucier. SODA'14]

2. グラフが動的・成長
 ほぼ未開拓[Zhuang-Sun-Tang-Zhang-Sun. ICDM'13] グラフ変化の検知[Chen-Song-He-Xie. SDM'15] 限られた状況のみ

6はじめに本研究の貢献成長するグラフ上の影響解析をサポートする
完全動的索引手法の提案
aabb

索引構築

ab

索引更新

数千万辺

I0追加+削除
1秒未満

I1I2bの影響力は3bの影響力は2

解析クエリ
精度保証
影響力最大はa7

予備知識
問題定義と既存のアプローチ

8

予備知識

扱う拡散モデル 独立カスケード[Goldenberg-Libai-Muller. Market. Lett.'01]

辺確率つきグラフ 𝐺 = (𝑉, 𝐸, 𝑝)
シード集合 𝑆 ⊆ 𝑉
活性uから非活性v (一回きり)頂点の状態を初期化▶ 𝑆内の頂点は活性▶ 𝑆外の頂点は非活性0.6

cea0.3▶ 成功 w.p. 𝑝uv▶ 失敗 w.p. 1 − 𝑝uv

0.10.40.80.2b 0.5dcfeabdcfeabdf9

予備知識

扱う拡散モデル 独立カスケード[Goldenberg-Libai-Muller. Market. Lett.'01]

辺確率つきグラフ 𝐺 = (𝑉, 𝐸, 𝑝)
シード集合 𝑆 ⊆ 𝑉
影響力𝜎 𝑆 ≔ 𝐄[𝑆がシード時の活性頂点数]0.6cea0.3

0.10.40.80.2b 0.5dcfeabdcfeabdf10

予備知識

問題定義
影響力推定
入力 頂点集合 𝑆
出力 𝜎 𝑆

厳密計算は#P-hard[Chen-Wang-Wang. KDD'10]

Monte-Carloで良近似

入力 整数 𝑘厳密計算はNP-hard [Kempe+'03]
貪欲アルゴリズムで𝟏 − 𝐞−𝟏 ≈ 63% 近似

出力 𝑆: 𝑆 =𝑘𝜎 ⋅ は単調・劣モジュラ [Kempe+'03]

影響最大化[Kempe-Kleinberg-Tardos. KDD'03]

argmax 𝜎 𝑆[Nemhauser-Wolsey-Fisher. Math. Program.'78]

劣モジュラ性 (限界効用逓減性)∀𝑋 ⊆ 𝑌, 𝑣 ∉ 𝑌, 𝜎 𝑋 + 𝑣 − 𝜎 𝑋 ≥ 𝜎 𝑌 + 𝑣 − 𝜎 𝑌𝜎(⋅)を高速・精確に評価したい！

11

予備知識

スケッチ手法 RIS[Borgs-Brautbar-Chayes-Lucier. SODA'14]

繰り返し：▶ ターゲット頂点 z を無作為に選択▶ スケッチ＝( z に影響する頂点集合)

逆向き
シミュレーション

12

予備知識

スケッチ手法 RIS[Borgs-Brautbar-Chayes-Lucier. SODA'14]

繰り返し：▶ ターゲット頂点 z を無作為に選択▶ スケッチ＝( z に影響する頂点集合)

ceab

逆向き
シミュレーション

df13

予備知識

スケッチ手法 RIS[Borgs-Brautbar-Chayes-Lucier. SODA'14]

繰り返し：▶ ターゲット頂点 z を無作為に選択▶ スケッチ＝( z に影響する頂点集合)

ceabdcfeab

逆向き
シミュレーション

df14

予備知識

スケッチ手法 RIS[Borgs-Brautbar-Chayes-Lucier. SODA'14]

繰り返し：▶ ターゲット頂点 z を無作為に選択▶ スケッチ＝( z に影響する頂点集合)

ceabdcfeab

逆向き
シミュレーション

dcfeabdf15

予備知識

スケッチ手法 RIS[Borgs-Brautbar-Chayes-Lucier. SODA'14]

繰り返し：▶ ターゲット頂点 z を無作為に選択▶ スケッチ＝( z に影響する頂点集合)

ceabdcfeab

逆向き
シミュレーション

dcfeabdf16

予備知識

スケッチ手法 RIS[Borgs-Brautbar-Chayes-Lucier. SODA'14]

ceabdcfeabdcfeabdf

スケッチに多く現れる頂点は影響力が高そう

𝜎(𝑆) ∝ 𝐄[𝑆と交差するスケッチ数]
影響力推定 ⇝ Unionのサイズ
影響最大化 ⇝ Maximum Coverage
ほぼ線形サイズのスケッチで十分

我々の目標＝このスケッチを動的に更新

提案手法
必要なもの
① 更新できる索引構造② 索引更新手法③ 影響解析クエリ手法

提案手法 ①索引構造更新できる索引構造
RISの素朴な適用

dezf

完全な情報

c0.50.3

e0.9

a0.20.1z

d0.6

f0.2

索引更新 難情報過少
拡散経路が分からない

消費空間 多300GB

19提案手法 ①索引構造更新できる索引構造
RISの素朴な適用

提案手法

完全な情報

乱数は振直す

adezf

dezf

c0.50.3

e0.90.20.1z

d0.6

f0.2

索引更新 難索引更新 易情報過少
拡散経路が分からない

消費空間 少消費空間 多30GB

300GB20

提案手法 ②更新手法

索引更新手法の概要
I1＝

czaaz・・・b

辺追加・辺削除・辺確率変更・頂点追加・頂点削除
z に影響 (到達) する頂点集合を更新

I2＝

czaaz・・・b

辺削除のみ説明します
簡単のため，辺確率＝1 ＆ 単一スケッチ21

提案手法 ②更新手法

辺削除の例1Q.「 z に到達可能な頂点」が減る？
http://www.cise.ufl.edu/research/spar
se/matrices/SNAP/soc-Epinions1.html

uv

z22

提案手法 ②更新手法

辺削除の例1Q.「 z に到達可能な頂点」が減る？
A. 減らないuvz23

提案手法 ②更新手法

辺削除の例2Q.「 z に到達可能な頂点」が減る？
http://www.cise.ufl.edu/research/sparse/matrices/SNAP/soc-Epinions1.html

uv

z24

提案手法 ②更新手法

辺削除の例2Q.「 z に到達可能な頂点」が減る？
A. 少し減るuv

z25

提案手法 ②更新手法

辺削除の素朴な更新方法
z から逆幅優先探索で良いのでは？
を消すため全uを見る

v＼遅い／z26

提案手法 ②更新手法

辺削除の高速な反映：到達可能木の導入

z を根とするスケッチの部分有向木
 迂回路の存在判定 逆幅優先探索の範囲抑制※ 頂点削除もOK

1,700ミリ秒

2ミリ秒

z27

提案手法 ②更新手法

辺削除の高速な反映：迂回路の存在判定
uv ∉ 到達可能木 ⇒ u から z へ迂回路が有る※逆は成立しない

uuvの削除：何もしなくてOK

z28

提案手法 ②更新手法

辺削除の高速な反映：探索範囲の抑制
u を根とする部分木Tuだけ調査 & 木を更新

疑惑のTu
高々数頂点uvz29

提案手法 ②更新手法

辺削除の高速な反映：探索範囲の抑制
u を根とする部分木Tuだけ調査 & 木を更新

uvz30

提案手法 ③クエリアルゴリズム

影響解析のクエリアルゴリズム
RIS [Borgs-Brautbar-Chayes-Lucier. SODA'14] をベースに索引再構築不要を活かし効率化▶ ハッシュテーブルによる動的管理▶ Lazy greedyの適用 [Minoux. Optimization Techniques'78]

精度保証 索引サイズ = Θ 𝜖 −3 𝑉 + 𝐸log 𝑉▶ 影響力推定の精度
𝜎 𝑆 ± 𝜖 𝑉 w.h.p. (定理 5.9)
▶ 影響最大化の近似比
1 − e−1 − 𝜖 w.h.p. (定理 5.10)▶ 索引更新手法の非退化性 (定理5.8) ⇝ 再構築の必要無31

実験
索引構築
索引更新
影響力推定
影響最大化の効率▶ データ：Koblenz Network Collection http://konect.uni-koblenz.de/
辺の作成時刻付き▶ 計算機：Intel Xeon E5-2690 2.90GHz CPU + 256GB RAM▶ コンパイラ：g++v4.6.3 (-O2)▶ 索引サイズ = 32 𝑉 + |𝐸| log 𝑉

実験

索引構築
実験設定
ネットワーク𝒑①
Epinions
13万点 84万辺 ②①
YouTube
322万点 1,875万辺 ②①Flickr
230万点 3,314万辺 ②

索引構築
時間 サイズ

完全な情報

89 s 1 GB
62 s 1 GB
5,000 s 45 GB
1,986 s 4 GB
5,468 s 31 GB
4,254 s 12 GB

6 GB
7 GB
250 GB180 GB≈ 282 GB≈ 292 GBサイズ

▶ 数時間だが一度きり① 辺uvの確率 = 0.1, 0.01, 0.001から無作為に選択② 辺uvの確率 = 入次数(v)-133実験

グラフ変化による索引更新
実験設定
ネットワーク

単一辺操作追加
削除 確率変更

単一頂点操作追加
削除

𝒑① 4.1 ms 1.0 ms
5.8 ms 0.8 ms 14.8 ms
Epinions
13万点 84万辺 ② 1.0 ms 1.8 ms
1.7 ms 0.7 ms
8.3 ms
① 31.8 ms 0.3 ms 236.2 ms 0.0 ms 92.2 ms
YouTube
322万点 1,875万辺 ② 0.1 ms 0.0 ms
1.5 ms 0.7 ms
5.7 ms
① 89.6 ms 2.4 ms 125.2 ms 0.0 ms 459.0 ms
Flickr
230万点 3,314万辺 ② 0.2 ms 0.1 ms
4.8 ms 2.1 ms 53.8 ms▶ (更新時間) ≪ (構築時間)▶ 頂点削除が最遅 ∵多量の辺削除を伴う
但し，頻度は少ないと思われる① 辺uvの確率 = 0.1, 0.01, 0.001から無作為に選択② 辺uvの確率 = 入次数(v)-134

実験

単一頂点の影響力推定の時間
実験設定

ネットワーク

本研究

𝒑 索引構築 クエリ①13万点 84万辺②①
YouTube
322万点 1,875万辺 ②①Flickr
230万点 3,314万辺 ②
Epinions

89 s
62 s
5,000 s
1,986 s5,468 s4,254 s0.97 μs
0.96 μs
1.79 μs
1.68 μs
1.83 μs
1.74 μs

静的手法

MCRIS

6s
0.01 s> 100 s0.02 s> 100 s0.05 s

9s
9s
519 s
447 s
350 s
473 s

[Kempe+'03] [Borgs+'14]▶ 100万点／秒の追跡可能▶ 実は，表引きしてるだけ① 辺uvの確率 = 0.1, 0.01, 0.001から無作為に選択② 辺uvの確率 = 入次数(v)-135

実験

影響最大化の時間 (シードサイズ 𝑘 = 100)
実験設定

ネットワーク

本研究

RIS
IMM
PMC
IRIE
𝒑 クエリ [Borgs+'14][Tang+'15] [Ohsaka+'14] [Jung+'12]①13万点 84万辺 ②①
YouTube
322万点 1,875万辺 ②①Flickr
230万点 3,314万辺 ②Epinions

静的手法

0.5 s
0.4 s
23 s
1s
16 s
3s

10 s
39 s
12 s
0.3 s
508 s メモリ不足
535 s
8s
361 s メモリ不足
617 s
6s

▶ スケッチが既にある効果

11 s
21 s
284 s
922 s
173 s
932 s

13 s
13 s
250 s
239 s
497 s
457 s

本研究と同精度設定① 辺uvの確率 = 0.1, 0.01, 0.001から無作為に選択② 辺uvの確率 = 入次数(v)-136実際にできること
Flixster (映画レビューサイト)
頂点の影響力の遷移

100頂点集合の最大影響力の遷移
最新結果
使い回し

データセット http://www.cs.ubc.ca/~jamalim/datasets/37おわりにまとめ完全動的索引手法を提案▶ 動的グラフ上の影響解析クエリを実現

aabb

索引構築

索引更新

数千万辺I0研究を通じ感じた今後▶ 索引の省スペース化圧縮できるか？

追加+削除
1秒未満

I1

解析クエリ
精度保証
影響力最大はabの影響力は3▶ 影響最大化クエリの高速化
動的な設定でMaximum Coverage
劣線形時間でできるか？

38