枝刈り探索による大規模グラフ上の高速な影響力推定・影響最大化アルゴリズム

枝刈り探索による大規模グラフ上の

高速な影響力推定・影響最大化アルゴリズム

大坂直人

東京大学 1 2017/2/9 基盤(S)離散構造処理系プロジェクトセミナー@北海道大学

自己紹介

▶ 名前：大坂直人 ▶ 所属：東京大学 大学院 情報理工学系研究科 コンピュータ科学専攻 博士2年 (本郷) ▶ 研究の興味：アルゴリズム全般、理論＋実験 ▶ 趣味：きつね、読書 2 宮城蔵王キツネ村にて

昨今の拡散の研究の背景 (2000s~)

オンラインネットワーク上の拡散現象の威力

▶ explicit／implicitに相互影響、速くて、大きい

3

Social Networking Service _{有名なHotmailの例 (1996)}Eメールサービス

今、データもある、計算資源もある

拡散の過程や人々の活動を理解・予測・制御したい！

“Get a free e-mail account with Hotmail”

中心的な問題＝影響最大化

[Kempe-Kleinberg-Tardos. KDD'03] Informalには … ▶ 目標：最多人数に情報を伝える集団の特定 ▶ 動機：バイラルマーケティングへの応用 4 試供品 試供品

私の研究の主題

大規模？ ▶オンラインソーシャルネットワークが対象 ▶105~108 点=ユーザ、107~1010 辺=友達関係 拡散解析？ ▶例：影響最大化・頂点の影響力推定 ▶最適化・計算する対象の定式化も必須 効率的？ ▶_Ω(点数2_{)時間は遅い ⇝ 高級な操作は✘} ▶_{Ω(辺数)空間も厳しい}かも _{⇝ I/O効率的な手法} 5

大規模グラフの拡散解析の効率的アルゴリズム

やってきた／やっていること

6 高速な影響最大化近似手法 私、秋葉拓哉、𠮷田悠一、河原林健一 AAAI 2014 複数トピックの導入_{私、𠮷田悠一} NIPS 2015 時間減衰要素の導入 私、山口勇太郎、垣村尚徳、河原林健一 ECML-PKDD 2016 ポートフォリオ最適化によるリスク回避 私、𠮷田悠一 WWW 2017 動的グラフ上の実時間索引手法 私、秋葉拓哉、𠮷田悠一、河原林健一 VLDB 2016 効率的アルゴリズム より良い拡散モデル

高速な影響最大化近似手法 私、秋葉拓哉、𠮷田悠一、河原林健一 AAAI 2014 動的グラフ上の実時間索引手法 私、秋葉拓哉、𠮷田悠一、河原林健一 VLDB 2016 効率的アルゴリズム

今回話す研究

7 武器：実グラフの構造的性質の活用 特徴：精度を落とさず、冗長計算を削減 課題：空間使用量は改善せず …辛い！ http://www.cise.ufl.edu/research/sparse/ matrices/SNAP/soc-Epinions1.html

影響最大化問題 (formal)

[Kempe-Kleinberg-Tardos. KDD'03] 入力：グラフ 𝐺 = (𝑉, 𝐸)、辺確率 𝑝: 𝐸 → (0,1]、整数𝑘 出力：𝐴 ⊆ 𝑉 ( 𝐴 = 𝑘) 目標：max Inf(𝐴) 8 影響拡散 _{𝐄[𝐴の影響が伝わった頂点数]}

独立カスケード [Goldenberg-Libai-Muller. Market. Lett.'01]

成否が確率的・独立に決まる ≒感染症のモデル

a

b

d

f

e

c

a

b

d

f

e

c

a

b

d

f

e

c

0.6 0.1 0.3 0.4 0.8 0.2 0.5

研究①

枝刈りシミュレーションを用いた

高速な影響最大化手法

研究①の背景

当時、高速・高精度な手法は無かった 10 既存手法の目標は Inf(⋅)の効率的近似計算 カテゴリ 戦略・特徴 代表的手法 シミュレーション 拡散過程を素朴に実行_{高品質・低速} CELF++ [Goyal+. WWW'11] CELF [Leskovec+. KDD'07] スナップショット ランダムグラフを 標本し再利用 高品質・低速

StaticGreedy [Cheng+. CIKM'13]

高速化したい！

ヒューリスティクス 精度保証無し_{高速・低品質}

IRIE [Jung+. ICDM'12]

SAEDV [Jiang+. AAAI'11]

研究①の貢献

[大坂-秋葉-𠮷田-河原林. AAAI'14] 主な課題 ▶ 様々な頂点集合について 到達可能な頂点数の計算が必要 解決法 ▶ 冗長な幅優先探索を徹底的に削減 ▶ 計算結果に影響無し 実験評価 ▶ 7,000万辺を20分で処理 ▶ 愚直な手法の400倍高速 11

6

3

4

5

2

1

2

影響最大化の高速近似手法の提案

スナップショット手法の概略

12 最適解の厳密計算 NP-困難 単調性・劣モジュラ性貪欲算法が定数近似 目的関数の厳密計算 #P-困難 到達可能頂点数で近似ランダムグラフ上の 貪欲算法×幅優先探索 𝒌 ⋅ 𝑽 ⋅ 𝑬 時間 一筋縄ではいかない…

我々の新技法

障壁

解決法

Inf ⋅ の最大化問題としての性質

▶ NP-困難 _{[Kempe-Kleinberg-Tardos. KDD'03]} Set Coverから帰着 ▶ _{Inf ⋅ は}単調・劣モジュラ _{[Kempe-Kleinberg-Tardos. KDD'03]} 𝑓 𝐴 + 𝑥 − 𝑓 𝐴 ≥ 𝑓 𝐵 + 𝑥 − 𝑓 𝐵 ∀𝐴 ⊆ 𝐵 ⊆ 𝑉, 𝑥 ∈ 𝑉 ∖ 𝐵 ▶ 貪欲算法が _{1 − e}−1 _{≈ 63%-近似}

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

𝑣

Inf 𝐴 + 𝑣 − Inf(𝐴) を選び𝐴に追加❞ × 𝑘回

13

Inf ⋅ の計算問題としての性質

▶ 厳密計算は #P-困難 _{[Chen-Wang-Wang. KDD'10]} s-t連結部分グラフ数え上げ問題から帰着 ※ 初の厳密計算手法 [Maehara-Suzuki-Ishihata. WWW'17] ▶ 近似計算 14 𝐺_𝑖上で𝑆から 到達可能な頂点数 拡散過程 ランダムグラフ上_{の到達可能性}

Coin-flip tech. [Kempe-Kleinberg-Tardos. KDD'03]

Inf 𝑆 ≜ 1 𝑟 1≤𝑖≤𝑟 R_𝐺𝑖 𝑆

=

𝑟個のランダムグラフ 𝐺₁, … , 𝐺_𝑟 を生成 辺𝑒を確率𝑝_𝑒で残す 経験的には 𝑟 ≈ 100 で十分

最終的にしたいこと

&

その難しさ

15 𝐴₀ = ∅ for 𝑗 = 1 to 𝑘 𝑣_𝑗∗ ← argmax 𝑣∈𝑉 1≤𝑖≤𝑟 R_𝐺𝑖 𝐴_𝑗−1 + 𝑣 − R_𝐺𝑖 𝐴_𝑗−1 𝐴_𝑗 ← 𝐴_𝑗−1 + 𝑣_𝑗∗ 簡単では？ ▶ 最初の反復 (𝐴_{0 = ∅) を考えてみると…} R_𝐺1 𝑣₁ ⋯ R_𝐺1 𝑣_𝑛 ⋮ ⋱ ⋮ R_𝐺𝑟 𝑣₁ ⋯ R_𝐺𝑟 𝑣_𝑛 𝑟 ⋅ 𝑉 回の幅優先探索(BFS)は遅すぎ 計算対象 各𝑂(|𝐸|)時間 6 3 4 5 2 1 2

提案手法：枝刈りシミュレーション

技法Ⅰ = 枝刈りBFSによる超高速な子孫数え上げ ▶ 最初の反復に有効 技法Ⅱ = 不要なBFSの検知・回避 ▶ 最初以降の反復に有効 特徴 ▶ ソーシャルネットワークの構造的性質を活用 ▶ 計算結果に影響無し ▶ 最悪時間計算量はおそらく改善しない ▶ 空間計算量 = 𝑂 𝑟( 𝑉 + |𝐸|) ※ 説明は 𝑟 = 1 ₁₆

技法Ⅰ：枝刈りBFS

計算対象：R_𝐺 𝑣₁ , R_𝐺 𝑣₂ , … , R_𝐺 𝑣_𝑛 ※簡単のため𝐺はDAG (前処理で強連結成分分解) 17 ▶ 前処理：次数最大のハブℎの子孫・先祖を計算 ① 𝑏 ∈ ℎの先祖 ▶ _ℎの子孫を無視してBFS ▶ 答＝(#探索点)+(#ℎの子孫) ② 𝑎 ∉ ℎの先祖 ▶ そのままBFS ▶ 答＝(#探索点)

𝑏

𝑎

ℎ

𝑐

𝑑

𝑒

𝑓

𝑏

𝑎

ℎ

𝑐

𝑑

𝑒

𝑓

技法Ⅰ：枝刈りBFS

計算対象：R_𝐺 𝑣₁ , R_𝐺 𝑣₂ , … , R_𝐺 𝑣_𝑛 ※簡単のため𝐺はDAG (前処理で強連結成分分解) 18 ▶ 前処理：次数最大のハブℎの子孫・先祖を計算 ① 𝑏 ∈ ℎの先祖 ▶ _ℎの子孫を無視してBFS ▶ 答＝(#探索点)+(#ℎの子孫) ② 𝑎 ∉ ℎの先祖 ▶ そのままBFS ▶ 答＝(#探索点)

𝑏

𝑎

ℎ

𝑐

𝑑

𝑒

𝑓

𝑏

𝑎

ℎ

𝑐

𝑑

𝑒

𝑓

技法Ⅰ：枝刈りBFS

計算対象：R_𝐺 𝑣₁ , R_𝐺 𝑣₂ , … , R_𝐺 𝑣_𝑛 ※簡単のため𝐺はDAG (前処理で強連結成分分解) 19 ▶ 前処理：次数最大のハブℎの子孫・先祖を計算 ① 𝑏 ∈ ℎの先祖 ▶ _ℎの子孫を無視してBFS ▶ 答＝(#探索点)+(#ℎの子孫) ② 𝑎 ∉ ℎの先祖 ▶ そのままBFS ▶ 答＝(#探索点)

𝑏

𝑎

ℎ

𝑐

𝑑

𝑒

𝑓

𝑏

𝑎

ℎ

𝑐

𝑑

𝑒

𝑓

技法Ⅰ：Q. 枝刈りBFSは効果的ですか？

▶ パスグラフでは 計_{Θ 𝑉} 2 時間 ▶ でも、ソーシャルネットワークなら… 20 複雑ネットワーク ソーシャル・ウェブ・共著 http://www.cise.ufl.edu/research/sparse /matrices/SNAP/soc-Epinions1.html ランダムグラフ _DAG Core Fringe

ℎ

巨大成分 高次数

技法Ⅰ：A. 枝刈りBFSは効果的でした！

▶ 平均探索頂点数：400,000 ⇨ 6 21 探索頂点数の分布 普通のBFS 枝刈り BF S

ℎ

データセット：LiveJournal, 𝑉 = 4.8M, 𝐸 = 69M, 𝑝_𝑒 = 0.1 ∀𝑒

技法Ⅱ：不要なBFSの検出・回避

▶ 計算対象：R_{𝐺 {𝑣1}∗_{, 𝑣} − R𝐺 𝑣1}∗ _∀𝑣 ▶ 計算済み：R_{𝐺 𝑣 ∀𝑣 By 枝刈りBFS} 回避条件 (𝑣の子孫) ∩ (𝑣₁∗の子孫) = ∅ ⇕ R_𝐺 {𝑣₁∗, 𝑣} − R_𝐺 𝑣₁∗ = R_𝐺 𝑣 検出方法 ▶ _𝑣1∗の子孫から逆BFSで線形時間 6/4 4/3 1/0 𝑣₁∗ 2/2 1/1 3/3 ※不可避な頂点は素直にBFS 左： R_𝐺 𝑣 右： R_𝐺 𝑣₁∗, 𝑣 − R_𝐺 𝑣₁∗

実験評価：提案手法の実行時間

シードサイズ 𝑘 = 50 23 データセット 技法Ⅰ

有

技法Ⅱ

有

技法Ⅰ

無

技法Ⅱ

有

技法Ⅰ

有

技法Ⅱ

無

技法Ⅰ

無

技法Ⅱ

無

DBLP 𝑝_𝑒 = 0.01 27秒 26秒 149秒 158秒 DBLP 𝑝_𝑒 = 0.1 54秒 3,036秒 306秒 3,275秒 LiveJournal 𝑝_𝑒 = 0.01 327秒 1,934秒 2,176秒 3,820秒 LiveJournal 𝑝_𝑒 = 0.1 634秒 272,518秒 2,426秒 272,973秒 データセット _{𝑉 𝐸} DBLP 655K 2.0M LiveJournal 4.8M 69M

400

倍

実験評価：影響拡散の値の比較

シードサイズ 𝑘 = 50 24 ▶ 提案手法が最良 データセット 提案手法 StaticGreedy_DU [Cheng+'13] IRIE

[Jung+'12] [Chen+'10]PMIA [Jiang+'11]SAEDV

DBLP 𝑝_𝑒 = 0.01 332 330 323 317 76 DBLP 𝑝_𝑒 = 0.1 100076 -- 99533 99505 99579 LiveJournal 𝑝_𝑒 = 0.01 47527 -- 41906 40544 26066 LiveJournal 𝑝_𝑒 = 0.1 1686629 -- 1682436 -- 1682242 データセット _{𝑉 𝐸} DBLP 655K 2.0M LiveJournal 4.8M 69M

実験評価：実行時間の比較

シードサイズ 𝑘 = 50

25

Environment: Intel Xeon X5670 (2.93GHz), 48GB, Language: C++

▶ ヒューリスティクスと同等

▶ 辺確率設定に対して頑健

データセット 提案手法 StaticGreedy_DU

[Cheng+'13]

IRIE

[Jung+'12] [Chen+'10]PMIA [Jiang+'11]SAEDV

DBLP 𝑝_𝑒 = 0.01 27秒 117秒 77秒 4秒 388秒 DBLP 𝑝_𝑒 = 0.1 52秒 OOM 77秒 289秒 388秒 LiveJournal 𝑝_𝑒 = 0.01 327秒 OOM 1,622秒 500秒 1,275秒 LiveJournal 𝑝_𝑒 = 0.1 663秒 OOM 1,635秒 OOM 1,294秒 データセット _{𝑉 𝐸} DBLP 655K 2.0M LiveJournal 4.8M 69M

その後、数多くの手法が出現

26

我々の手法はもはや時代遅れ…？

カテゴリ 戦略・特徴 代表的手法 シミュレーション 拡散過程を素朴に実行_{高品質・低速} CELF++ [Goyal+. WWW'11] CELF [Leskovec+. KDD'07] スナップショット ランダムグラフを 標本し再利用 高品質・低速 PMC [我々. AAAI'14]

StaticGreedy [Cheng+. CIKM'13]

逆到達可能集合

逆シミュレーションの 結果を活用 (後述)

高品質・ほぼ線形時間

IMM [Tang+. SIGMOD'15]

TIM+ _{[Tang+. SIGMOD'14]} RIS [Borgs+. SODA'14]

ヒューリスティクス 精度保証無し_{高速・低品質}

EaSyIM [Galhotra+. SIGMOD'16]

IRIE [Jung+. ICDM'12]

SAEDV [Jiang+. AAAI'11]

Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study

[Arora-Galhotra-Ranu. SIGMOD'17] ▶ 徹底的な実験で既存手法の性能を検証 ▶ 我々の手法について … 27 要約 グラフ・辺確率設定に対し速度は安定だが、 メモリ消費が莫大

研究①のまとめ

▶ 解決できた点 ▶スナップショット手法の効率改善 ▶ 浮上した課題 ▶莫大なメモリ使用量 𝑂 𝑟 𝑉 + 𝐸 28

研究②

成長するグラフにおける

影響力推定・影響最大化のための

実時間完全動的索引手法

研究②の背景

現実のソーシャルネットワークは動的・成長する ▶ 最新の解析結果を追跡したい ▶ 静的手法の逐次適用 ⇝ 線形時間以上 30 Q. 研究①は使えますか？ A. 難しい_{; ハブ頂点の先祖・子孫の動的更新が大変} 友達関係の成立・解消

研究②の貢献

[大坂-秋葉-𠮷田-河原林. VLDB'16] 31 成長するグラフ上の影響解析をサポートする 完全動的索引手法の提案 b a

I

₀ b a

I

₁ b a

I

₂ 影響力最大はa bの影響力は3 bの影響力は2 索引構築 数千万辺 索引更新 追加+削除 1秒未満 解析クエリ 精度保証

既存の静的手法との関連

32 カテゴリ 戦略・特徴 代表的手法 シミュレーション 拡散過程を素朴に実行_{高品質・低速} CELF++ [Goyal+. WWW'11] CELF [Leskovec+. KDD'07] スナップショット ランダムグラフを 標本し再利用 高品質・低速 PMC [我々. AAAI'14]

StaticGreedy [Cheng+. CIKM'13]

逆到達可能集合

逆シミュレーションの 結果を活用 (後述)

高品質・ほぼ線形時間

IMM [Tang+. SIGMOD'15]

TIM+ _{[Tang+. SIGMOD'14]}

RIS [Borgs+. SODA'14]

ヒューリスティクス 精度保証無し_{高速・低品質}

EaSyIM [Galhotra+. SIGMOD'16]

IRIE [Jung+. ICDM'12]

SAEDV [Jiang+. AAAI'11]

PMIA [Chen+. KDD'10]

Reverse Influence Sampling アルゴリズム

[Borgs-Brautbar-Chayes-Lucier. SODA'14] ▶ 逆到達可能 (Reverse Reachable; RR) 集合 一様無作為に選んだ頂点 に影響しうる頂点集合 33

z

＝ランダムグラフ上で

z

に到達

a

b

d

f

e

c

a

b

d

f

e

c

a

b

d

f

e

c

a

b

z

c

a

z

a

f

z

Reverse Influence Sampling アルゴリズム

[Borgs-Brautbar-Chayes-Lucier. SODA'14] ▶ 逆到達可能 (Reverse Reachable; RR) 集合 一様無作為に選んだ頂点 に影響しうる頂点集合 34

Inf 𝑆 ∝ 𝐄[#𝑆と交わる逆到達可能集合]

探索辺数 = Θ 𝜖−3 _{𝑉 + 𝐸 log 𝑉} [Borgs-Brautbar-Chayes-Lucier. SODA'14]

z

＝ランダムグラフ上で

z

に到達

a

b

e

c

a

d

a

f

c

a

b

e

c

a

d

a

f

c

提案手法の概要

①索引構造 ▶動的更新しやすい＆省メモリ ②解析クエリ手法 ▶逆到達可能集合を利用 ③索引更新手法 ▶正しく＆効率的に到達可能性を修正 35 目標：

グラフ変化に応じて逆到達可能集合を更新

①索引構造

36 逆到達可能集合 提案スケッチ 完全情報 索引更新 難 情報過少 拡散経路が分からない 索引更新 易 消費空間 大 索引更新 易 消費空間 小

z

d

f

e

z

d

f

e

a

z

d

f

e

c

0.5 0.3 0.1 0.6 0.2 0.2 0.9 乱数は振直す z に届く頂点・辺だけ

②解析クエリ手法

▶ 逆到達可能集合の逆インデックス 1つ目の逆到達可能集合 = 𝑎, 𝑏, 𝑒 2つ目の逆到達可能集合 = 𝑎, 𝑑 3つ目の逆到達可能集合 = 𝑎, 𝑐, 𝑓 4つ目の逆到達可能集合 = 𝑏, 𝑒, 𝑓 5つ目の逆到達可能集合 = 𝑐, 𝑑, 𝑒 37 a b c d e f 1 2 3 4 5 頂点 ⟷ 逆到達可能集合 相互に表引き可能

②解析クエリ手法

38 a b c d e f 1 ✔ 2 3 ✔ 4 ✔ 5 ✔ ✔ {c, e}? k=2? 貪欲に頂点を選択 4×定数 ▶ 影響最大化：交わるスケッチ数が最大の頂点集合 ▶ 影響力推定：頂点集合と交わるスケッチ数の計算 {a, e} a b c d e f 1 2 3 4 5

③索引更新手法

グラフが変化したら … 各スケッチを独立に更新し、以下を保つ :

❝ 任意の

は

を通り

z

に到る ❞

a b d f z c a b d f z c a b d f z c ac 削除 db 追加 ⇝ 索引再構築の必要無 39 基本はBFS 5つの操作 辺追加・辺削除・辺確率変更・頂点追加・頂点削除

辺削除の例1

40

z

v

u

Q.「

z

に到達可能な頂点」が減る？

辺削除の例1

41

z

v

u

Q.「 に到達可能な頂点」が減る？ A. 減らない

z

辺削除の例2

42

u

v

z

Q.「

z

に到達可能な頂点」が減る？ 出近傍無し

辺削除の例2

43

u

v

z

Q.「 に到達可能な頂点」が減る？ A. 少し減る

z

から逆幅優先探索で良いのでは？ を消すため全 _{を見る ⇝} 全体を走査

辺削除の素朴な更新方法

z

＼遅い／ z v u u _v z 課題Ⅱ 効率的な逆幅優先探索 課題Ⅰ 迂回路の検知 44

辺削除の高速な反映：

到達可能木

の導入

45

を根とするスケッチの

部分有向木

技法Ⅰ= 迂回路の存在判定

技法Ⅱ= 逆幅優先探索の範囲抑制

* 頂点削除もOK

z

z 消費空間≤|スケッチ|

辺削除の高速な反映：迂回路の存在判定

46

uv ∉

到達可能木

_⇒

から へ迂回路が有る

※逆は成立しない

z

z

v

u

u

実験では10%が枝刈り

辺削除の高速な反映：探索範囲の抑制

を根とする部分木

_T

_u

_{だけ調査 &}

木

を更新

T

_u

高々数頂点

u

v

z

u

> 100,000 点 平均的に

辺削除の高速な反映：探索範囲の抑制

を根とする部分木

_T

_u

_{だけ調査 &}

木

を更新

T

_u

高々数頂点

u

> 100,000 点 平均的に 48

u

v

z

上手くいくワケ

49 http://www.cise.ufl.edu/research/sparse/ matrices/SNAP/soc-Epinions1.html

Core-fringe 構造

Fringe は 木っぽい T_u 小さい 技法Ⅱが効果的 Core は 密 迂回路沢山 技法Ⅰが効果的 [Leskovec-Lang-Dasgupta-Mahoney. WWW'08] [Maehara-Akiba-Iwata-Kawarabayashi. PVLDB'14]

Core

Fringe

実験評価

▶ 索引構築・索引更新・影響力推定・影響最大化

の効率を評価

▶ データ：Koblenz Network Collection

辺の作成時刻付き

▶ 計算機：Intel Xeon E5-2690 2.90GHz CPU + 256GB RAM ▶ コンパイラ：g++v4.6.3 (-O2)

▶ 索引サイズ =32(|𝑉| + |𝐸|) log |𝑉|

50

実験：索引構築

51 実験設定 索引構築 ネットワーク _𝒑 時間 サイズ Epinions 13万点 84万辺 ① _{89 s 1 GB} ② _{62 s 1 GB} YouTube 322万点 1,875万辺 ① 5,000 s 45 GB ② 1,986 s 4 GB Flickr 230万点 3,314万辺 ① 5,468 s 31 GB ② 4,254 s 12 GB ▶ 数時間だが一度きり ① 辺uvの確率 = 0.1, 0.01, 0.001から無作為に選択 ② 辺uvの確率 = 入次数(v)-1 完全な情報 サイズ 6 GB 7 GB 250 GB 180 GB ≈ 282 GB ≈ 292 GB

実験：グラフ変化による索引更新

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

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

実験設定 本研究 静的手法

ネットワーク _{𝒑 索引構築 クエリ} MC

[Kempe+'03] [Borgs+'14]RIS

Epinions 13万点 84万辺 ① _{89 s 0.97 μs 6 s 9 s} ② _{62 s 0.96 μs 0.01 s 9 s} YouTube 322万点 1,875万辺 ① _{5,000 s 1.79 μs > 100 s 519 s} ② _{1,986 s 1.68 μs 0.02 s 447 s} Flickr 230万点 3,314万辺 ① _{5,468 s 1.83 μs > 100 s 350 s} ② _{4,254 s 1.74 μs 0.05 s 473 s} 53 ▶ _{100万点／秒の追跡可能} ▶ ∵表引きしてるだけ ① 辺uvの確率 = 0.1, 0.01, 0.001から無作為に選択 ② 辺uvの確率 = 入次数(v)-1

① 辺uvの確率 = 0.1, 0.01, 0.001から無作為に選択 ② 辺uvの確率 = 入次数(v)-1

実験：影響最大化の時間

(シードサイズ 𝑘 = 100) 54 実験設定 本研究 静的手法 ネットワーク _{𝒑 クエリ} RIS

[Borgs+'14] [Tang+'15]IMM [Ohsaka+'14]PMC [Jung+'12]IRIE

Epinions 13万点 84万辺 ① _{0.5 s 10 s 39 s 11 s 13 s} ② _{0.4 s 12 s 0.3 s 21 s 13 s} YouTube 322万点 1,875万辺 ① _{23 s 508 s} メモリ不足 284 s 250 s ② _{1 s 535 s 8 s 922 s 239 s} Flickr 230万点 3,314万辺 ① _{16 s 361 s} メモリ不足 173 s 497 s ② _{3 s 617 s 6 s 932 s 457 s} ▶ スケッチが既にある効果 本研究と同精度設定

研究②のまとめ

解決した点 ▶ 動的設定で影響解析を効率的に実現 浮上した課題 ▶ 莫大な索引サイズ：数千万辺で10GBオーダー 55

滞在中の計画／アイデア

今回扱った基礎的な操作を圧縮したまま出来る？ ▶ 巨大データ×確率的振舞の空間を効率化 ▶サンプリングによる近似も重いため ▶ 超高速な動的・オンライン処理 ▶研究②の影響最大化は実はnotオンライン 56