「StaticGreedy: Solving the Scalability-Accuracy Dilemma in Influence Maximization」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
StaticGreedy: Solving the Scalability-Accuracy Dilemma in Influence Maximization
- Suqi Cheng, Huawei Shen, Junming Huang, Guoqing Zhang, Xueqi Cheng
- In CIKM 2013
-- ArXiv 2012
* 概要
- 実は今までのMonte-Carloは間違っていた！
- 毎回ランダムグラフを作っているのが問題
- そのせいで莫大な試行回数が要求される
- 俺が最強のMonte-Carloアルゴリズムを提案するぜ！
- ランダムグラフを使いまわす
- Rは1/100に減った
* StaticGreedy
+ R回ループ
++ 各辺を割り当てられた確率に応じて消す
+ k回ループ
++ 各頂点のmarginal influence spreadを求める
++ marginal influence spreadが最大の頂点をseed setに加える
- え、どこが新しいの？
-- グラフを最初に作ってしまいそれを使いまわすところ
* CELFGreedyとStaticGreedyの比較
** 真の解との誤差
- R=20,000を真の解として、得られた解によるinfluence spreadが試行回数Rによってどう変わるか調べる
- CLEFGreedy
-- R=10,000位ないと0.05までいかない
- StaticGreedy
-- R=100程度で0.05を切る
* 計算量
- 時間計算量: O(R'm+knR'm')
-- R': 削減したR
-- m': 平均的に残る辺数
- 空間計算量: O(R'm')
* 高速化(StaticGreedyDU)
- 各サブグラフについて以下を前計算
-- R(G',v) = vから到達可能なノードの集合
-- U(G',v) = vに到達可能なノードの集合
- σ(v)は|R(G',v)|の和
- seed v*が選ばれたら
++ R(G',v*)に含まれるwについて
++ U(G',w)に含まれるuについて
++ wをR(G',v*)から消す
++ σ(u)を1減らす
** 計算量
- 一番大きそうな項が: O(kR' maxR maxU)
-- 本質的には改善されていない？？？
* 実験
** データセット
- NetHEPT,NetPHY,DBLP,Epinions,Slashdot,Douban
-- |V|=15K~655K, |E|=59K~22M
-- Doubanがでかい
** 伝播モデル
- p=0.01 or 0.001
-- Doubanだけ0.001（せこい！
** アルゴリズム
- CELF
- PMIA
- DegreeDiscount
- Degree
** 結果
*** influence spread
- ほぼ最適
-- CELF(R=20000)には、ちょびっと負けてるが、小さいグラフだけ
- PMIA微妙
*** 実行時間
- 高速化を入れるとだいたい10倍早くなっている
- PMIAとStaticGreedyが同じくらい
* 結論
- Rの値をどう決めるか
- linear threshold modelへの拡張
- 並列計算
- 実ネットワークとかいろいろ応用
* まとめ
- 実はsubmodularがちゃんと成り立っていない、というところに着目したのはすごいと思った
-- 誰も見ていなかったから
- pの値をめちゃ小さくしていたのはせこいと思った
-- でかいグラフで0.001にしたのはひどい
StaticGreedy: Solving the Scalability-Accuracy Dilemma in Influence Maximization
- Suqi Cheng, Huawei Shen, Junming Huang, Guoqing Zhang, Xueqi Cheng
- In CIKM 2013
-- ArXiv 2012
* 概要
- 実は今までのMonte-Carloは間違っていた！
- 毎回ランダムグラフを作っているのが問題
- そのせいで莫大な試行回数が要求される
- 俺が最強のMonte-Carloアルゴリズムを提案するぜ！
- ランダムグラフを使いまわす
- Rは1/100に減った
* StaticGreedy
+ R回ループ
++ 各辺を割り当てられた確率に応じて消す
+ k回ループ
++ 各頂点のmarginal influence spreadを求める
++ marginal influence spreadが最大の頂点をseed setに加える
- え、どこが新しいの？
-- グラフを最初に作ってしまいそれを使いまわすところ
* CELFGreedyとStaticGreedyの比較
** 真の解との誤差
- R=20,000を真の解として、得られた解によるinfluence spreadが試行回数Rによってどう変わるか調べる
- CLEFGreedy
-- R=10,000位ないと0.05までいかない
- StaticGreedy
-- R=100程度で0.05を切る
* 計算量
- 時間計算量: O(R'm+knR'm')
-- R': 削減したR
-- m': 平均的に残る辺数
- 空間計算量: O(R'm')
* 高速化(StaticGreedyDU)
- 各サブグラフについて以下を前計算
-- R(G',v) = vから到達可能なノードの集合
-- U(G',v) = vに到達可能なノードの集合
- σ(v)は|R(G',v)|の和
- seed v*が選ばれたら
++ R(G',v*)に含まれるwについて
++ U(G',w)に含まれるuについて
++ wをR(G',v*)から消す
++ σ(u)を1減らす
** 計算量
- 一番大きそうな項が: O(kR' maxR maxU)
-- 本質的には改善されていない？？？
* 実験
** データセット
- NetHEPT,NetPHY,DBLP,Epinions,Slashdot,Douban
-- |V|=15K~655K, |E|=59K~22M
-- Doubanがでかい
** 伝播モデル
- p=0.01 or 0.001
-- Doubanだけ0.001（せこい！
** アルゴリズム
- CELF
- PMIA
- DegreeDiscount
- Degree
** 結果
*** influence spread
- ほぼ最適
-- CELF(R=20000)には、ちょびっと負けてるが、小さいグラフだけ
- PMIA微妙
*** 実行時間
- 高速化を入れるとだいたい10倍早くなっている
- PMIAとStaticGreedyが同じくらい
* 結論
- Rの値をどう決めるか
- linear threshold modelへの拡張
- 並列計算
- 実ネットワークとかいろいろ応用
* まとめ
- 実はsubmodularがちゃんと成り立っていない、というところに着目したのはすごいと思った
-- 誰も見ていなかったから
- pの値をめちゃ小さくしていたのはせこいと思った
-- でかいグラフで0.001にしたのはひどい
&tags()
&update()
