In Search of Influential Event Organizers in Online Social Networks

In Search of Influential Event Organizers in Online Social Networks

  • Kaiyu Feng, Gao Cong, Sourav S. Bhowmick, Shuai Ma
  • SIGMOD 2014

概要

  • 影響最大化 + 集合被覆のような問題
  • タイトルの通りイベント主催者を見つけるのが動機づけ
  • 貪欲アルゴリズムと近似比2のアルゴリズムを提案

イントロ

  • Plancast,Meetupというサービスが出てきている
  • イベント主催者も影響力が有ったほうがいいね
  • でも,分野横断とかだと色々な内容をカバーしてないと駄目だね
  • this paper

問題定義

  • グラフ G = (V, E, w, A)
    • wは辺確率,Aは頂点から特性集合への写像
  • k: シード集合サイズ
  • Q: クエリ
  • maximize σ(S)
  • s.t. $$ Q \subseteq \bigcup_{s \in S} {\cal A}(s) $$
  • 仮定
    • |Q|は小さい(定数)
    • kも小さい,6くらい
      • イベント主催者数だから100超えとかない

貪欲法

  • Score-based Greedy Algorithm
    • 頂点vのスコアは
    • α(vが新たに被覆するクエリ) + (1-α)(vの影響拡散増加量)
    • ただし,各々は最大値で割って正規化してある
  • PigeonGreedy Algorithm
    • Q'を残りの被覆すべき特性集合として,
    • ceil( |Q'|/(k-|S|) )個被覆できる頂点の内,一番増加量が大きいものを選ぶ
    • 鳩ノ巣原理みたいな…
  • 両方とも保証無し

Partition-based Influential Cover Set (PICS) Algorithm

  • Q = {A1, …, Am} (m≦k): Qの分割
  • V(Ai) = {v: Ai⊆A(v)}
  • もし,V(Ai)が全部非空なら,各分割から頂点をとってくれば,被覆の制約が満たされる
  • なので,分割全パターンについて,貪欲に選んでいく
  • もし,実行可能解があれば必ず出力される
  • 近似度は2らしい
  • 計算時間はオワコンなので,これを高速化したのがPICS+
  • 実験はごちゃごちゃしてるので省略

まとめ

SIGMOD 影響最大化 情報拡散

2014-07-07 17:10:48 (Mon)

最終更新:2014年07月07日 17:10