StaticGreedy: Solving the Scalability-Accuracy Dilemma in Influence Maximization - todo314 @ ウィキ

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

1. R回ループ
   1. 各辺を割り当てられた確率に応じて消す
2. k回ループ
   1. 各頂点のmarginal influence spreadを求める
   2. 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*が選ばれたら
  1. R(G',v*)に含まれるwについて
  2. U(G',w)に含まれるuについて
  3. wをR(G',v*)から消す
  4. σ(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にしたのはひどい

CIKM influence maximization

2013-11-04 18:56:37 (Mon)