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)
-
k: シード集合サイズ
-
Q: クエリ
-
maximize σ(S)
-
s.t. $$ Q \subseteq \bigcup_{s \in S} {\cal A}(s) $$
-
仮定
貪欲法
-
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