Influence Maximization in Dynamic Social Networks - todo314 @ ウィキ

Influence Maximization in Dynamic Social Networks

• Honglei Zhuang, Yihan Sun, Jie Tang, Jialin Zhang, Xiaoming Sun
• ICDM 2013

概要

• influence max.の動的グラフ版を考える
• 現実的設定で、どこの頂点をprobeし直せば良いかを問題とする
  • b頂点だけ更新できる
• influence spreadのずれがでかそうな頂点を頑張って計算する
• 実験の結果ベースラインよりかなり良かった

問題設定

• G^t: 時刻tでのグラフ
• b: probeできる頂点数
• b頂点を更新した時に、そのグラフで計算した解と真の解ができるだけ近くなるようにしたい

Maximum Gap Probing (MaxG)

• influence max.のアルゴリズムはDegree discountを使う
  • だから確率は全部同じ
• Q_v(S): vをprobe後のinfluence spread
• S_o: 頂点vをprobe前の最適解
• S'_o: 頂点vをprobe後の最適解
• Q_v(S'_o)-Q_v(S_o)をギャップとしてこれが大きい頂点をprobeする
• 実際には、εを指定して Pr[差≧β(v)]≦ε となるβ(v)をもとめる
• β(v)がデカイを頂点をprobeしたら、また計算し直す。これをb回繰り返す
• β(v)の値は√lnεと頂点の次数の足し引きで概算

実験

• 比較対象: ランダム、適当な順番、次数重みの確率、次数重みのRound-Robin
• 真のG^tに対して逐一アルゴリズムを走らせてground truth
• 2倍とかかなり差が大きいのもあるけど、ベースラインにはほぼ必ず勝っている

まとめ

• 問題は普通、いずれ考えるはずの内容
  • 動的というから、真面目に再計算するより早いタイプかと思ったら違った
  • PageRankのと似たアプローチ
• Degree discountでいいのか？
• β(v)の導出は読んでないけど理論解析なのかなあ…
  • PageRankの程はやってなさそう

ICDM dynamic graphs influence maximization

2014-01-27 01:28:20 (Mon)