Community-based Greedy Algorithm for Mining Top-K Influential Nodes in ... - todo314 @ ウィキ

Community-based Greedy Algorithm for Mining Top-K Influential Nodes in Mobile Social Networks

• Yu Wang, Gao Cong, Guojie Song, Kunqing Xie
  • 焼きなましベースの人々と大体同じ
• KDD 2010

概要

• NewGreedyIC（MixedGreedy）がstate-of-the-artだったころの話
• どうしても時間がかかっちゃうので、コミュニティに分割することにした
• Community-based Greedy algorithm
• ちょっとおもしろい点
  • コミュニティ分割がICモデルのシミュレートで行われる
  • ↑の後はDPする

予備知識みたいな何か

• 何故p_ijを以下で設定する
  • $$ \lambda_{ij} = 2 \overline{\lambda} \frac{w_{ij}}{w_{max}+w_{min}} $$
  • 辺に重みを付けて平均で設定する

提案手法

• とりあえずコミュニティに分割できたとする
  • コミュニティの数: M
• R[m,k]: k番目のシードを1~mのコミュニティから選んだ時の最大のIS
  • R[m,k] = max{R[m-1,k], R[M,k-1]+ΔR_m}
  • ΔR_m: コミュニティC_mの中で最大のmarginal gain
• K回ループするんだけど、ループの最後で、DPして選んだコミュニティ内で一番gainのでかい頂点を選びなおす
  • ΔR_mの頂点は使わないらしい
• DP自体の計算量は大したことない
• 問題はΔR_mを求める所
  • 極力イイ感じに分割されていて欲しい、かたよるとツラい
• コミュニティ検出
  • 分割
    • カスケードが届くような頂点同士は同じコミュニティだとうれしい（そりゃそうだ
    • 伝搬させて反復、みたいな
  • 併合
    • 何かエントロピーを定義してそれがθ以上ならマージしたりする

実験

• 手法
  • MixedGreedy, NewGreedy, CGA, SPCGA, DegreeDiscount, Random
  • SPCGAはコミュニティ検出を他の手法にした
• influence spread
  • Greedyにはおとるけど、そこそこ
• 速度
  • Greedyの100倍位？

まとめ

• これでKDD通るのだなあという印象
• ここに書いてないけど、精度保証を書いているのがポイントなんだろうか
• コミュニティ検出が独特で普通のより良いのも高評価なのかもしれん

KDD influence maximization

2014-01-08 00:22:08 (Wed)