An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in ... - todo314 @ ウィキ

An Upper Bound based Greedy Algorithm for Mining Top-k Influential Nodes in Social Networks

• Chuan Zhou, Peng Zhang, Jing Guo, Li Guo
• WWW 2014 companion
  • ポスター

概要

• UBLF: An Upper Bound Based Approach to Discover Influential Nodes in Social ...のLT版
• CELFより5倍速い

提案手法

• σ(S)=ΣΠw(e)の形でかける
• ↑は行列のべき乗和（有限）で上から抑えられる
• Wのべき乗和は(I-W)^-1で上から抑えられる
  • 確率だから1以下って制約とか使う
• σ(S)≦A(I-W)^-1 1
  • こんな感じの行列計算にできる
• 最初に上の式で各頂点vの上限δ_vを求めておく
• CELFをしながら今uを取り出したらδ_uをシミュレーションでのゲインに更新
  • シミュレーションは必要になった時にやっている
• それでもδ_uが最大だったらそれがゲイン最大

実験

• グラフは小さい
• シミュレーション数は1/100位になった
• けど，実行時間は1/5位

まとめ

• 今更CLEFの5倍早くてもね…

WWW 影響最大化

2014-05-22 22:50:09 (Thu)