「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+
- 実験はごちゃごちゃしてるので省略
* まとめ
- 何か影響最大化の変種が流行っているなあ
- 分野横断の件とかは[[Evaluating Multi-Way Joins over Discounted Hitting Time]]にちょっと似てる？
&tags()
&update()
