IMRank: Influence Maximization via Finding Self-Consistent Ranking

IMRank: Influence Maximization via Finding Self-Consistent Ranking

  • Suqi Cheng, Huawei Shen, Junming Huang, Wei Chen, Xueqi Cheng
  • SIGIR 2014

概要

  • 貪欲アルゴリズムで選ぶと,ゲインは単調非増加
  • 逆にゲインが単調なランキング(順列)は割りと良さそう?
  • 適当なランキングから初めて,並び替えを反復
    • ゲインの計算はヒューリスティック

提案手法

自己整合(self-consistent)な順列

  • 以下を満たすランキング $$ r:[n] \to V $$
  • $$ i<j \Rightarrow M(i) \geq M(j) $$
    • $$ M(i) = \sigma(r(i) \mid \{r(1),\ldots,r(i-1)\}) $$
  • 貪欲アルゴリズムを最後まで走らせると自己整合な順列がとれる

IMRank

  • 以下を収束まで反復
  1. 今のrを元にゲインM(i)を全て計算
  2. M(i)に従ってrを整列する
  • ゲインの計算
  • 1,2の性質を利用
  1. M(i)←1 ∀i
  2. ランキングが低い頂点iから高い頂点jに伝播する
    • IRIE的
    • $$ M(i)p(j,i) \prod_{1 \leq k \leq k}(1-p(k,i)) $$
  • O(n+m)時間で良い
  • シミュレーションと比較してるがズレ過ぎたろう

収束の挙動

  • 5反復位で局所解に落ちる
    • 割りとありそう
  • 初期ランキングを無作為,次数,逆次数,重み和,PageRankでやる
    • 最初が良さそうな感じの方が回も良い
    • 速度はそんなに変わらん

解析

  • 定理 2: どんなランキングから始めても有限ステップで収束する

実験

  • データセット
    • DBLP, EPinions, Douban, LiveJournal等
  • IMRank1(計算端折ってる)
    • LiveJournalで100秒
    • 下に10%位負けてるけど…
  • IMRank2(少し真面目)
    • 1000秒
  • PMIA, IRIEよりはマシ

まとめ

  • 何故ゲインの計算を謎な方法にしたのか?
  • ランダムグラフを固定したとして,
  • ランク高い順にBFSして,新たに訪れた頂点数(の平均値)がゲインなんだよな~
  • 反復数が多い:ランダムグラフは事前に生成した方が辺数が減って得しそう
  • 反復数が少ない:確率が小さい時グラフ全体は見ないのでその場でサンプルしたほうが速そう
  • こういうランキングをちまちま変える手法って名前ついてんのかな?

SIGIR 影響最大化

2015/07/09 14:59

最終更新:2015年07月13日 19:44
添付ファイル