Efficient Location-Aware Influence Maximization - todo314 @ ウィキ

Efficient Location-Aware Influence Maximization

• Guoliang Li, Shuo Chen, Jianhua Feng, Kian-lee Tan, Wen-Syan Li
• SIGMOD 2014

概要

• 位置を考慮した影響最大化
  • Foursquareとか
  • クエリは領域とk
• 2つの手法を提案
  • 1-1/e近似
  • expansion-based
  • assembly-based
• それでも遅いのでさらに2手法
  • ε(1-1/e)近似
  • bound-based
  • hint-based

問題定式化

• vの位置は二次元座標(x,y)
• 情報拡散モデルはICモデル
• クエリ Q=(R,k)
  • Rは領域
• σ(S,V_R)=(V_Rに限った影響拡散)を最大化したい
  • SはV_RからとってこなくてもOK

Tree-based Approximation Model

• PMIAのモデルを使う

Expansion-based Method

• 最初にシードになりうる（少数の）候補頂点集合を選択
• P(S∪{u}, V_R)の上界を見積もってbest-first

Assembly-based Method

• Expansionの問題: クエリ領域が大きいと候補がでかくなる
• インデックスを作っておくらしい

ε(1-1/e)近似比アルゴリズム

• 上の2つの問題: kがデカイと遅い！

Bound-based Algorithm

• 下界を見積もってゴニョゴニョ

Hint-based Algorithm

解析

• いろんな変数が入り交じっていて時間計算量がキモすぎ

実験

• Weibo.comのグラフ
• 比較対象
  • PMIA, IRIEのみ

まとめ

• 手法がごちゃごちゃしててほとんど読んでない
• ランダム，次数順入れないタイプかー
• 適当にやっても良かったら意味が無いのに