「Recommendations to Boost Content Spread in Social Networks」の編集履歴（バックアップ）一覧はこちら

「Recommendations to Boost Content Spread in Social Networks」(2015/11/16 (月) 00:05:33) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

* Recommendations to Boost Content Spread in Social Networks
- Vineet Chaoji, Sayan Ranu, Rajeev Rastogi, Rushi Bhatt
- WWW 2012

* 概要
- コンテンツ共有は強力
- どういう広がるかは連結関係が大事
- 共通近傍とか，類似度じゃなくて，コンテンツの量を考慮したい
- 辺を次数制約のもと挿入する
- 劣モジュラじゃないので，色々と改造する
- 近似アルゴリズム

* コンテンツ最大化問題
- 各頂点iについて
-- $$ p_i $$: iが各近傍と共有する確率（独立）
-- $$ c_i $$: iの作った／発見したコンテンツ
-- $$ N_i $$: iと相性が良い頂点集合
- コンテンツ拡散 $$ f(X) := \sum_c \sum_i P_X(i,c) $$
-- $$ P_X(i,c) $$: コンテンツE∪X上で頂点iにcが届く確率
-- 期待値で測っている
- 問題
+ ICモデルで#P-hard
-- PMIA的アプローチをする
-- 最も高い確率の経路だけ通るとする
+ PMIAモデルでも劣モジュラでない
-- モデルを改造（簡易化）
- 解決法
+ θ以下の経路は打ち切り
+ 各経路は独立
-- 経路同士が重複しているけど簡単のため
- $$ f(X) := \sum_c \sum_i \left( 1 - \prod_{j \in V(c)} (1-q_X(i,j))  \right) $$
-- $$ q_X(i,j) $$: j->iの確率
-- 独立としているので簡単
- fは劣モジュラ
- 5節では，経路の独立性とかについて実験的に議論している

* 近似アルゴリズム
- Vondrakの「連続的貪欲算法＋パイプ丸め」を使う
-- 刻み幅やシミュレーション回数は結構適当で良い

* 実験
- 貪欲，連続的貪欲，次数，Friend-of-Friendをベースに辺を選択
- 各頂点次数の増加はk=10以下

* まとめ
- モデルが粗っぽいけれどまぁいいのかな
- Vondrakの実際に使えるのね，遅いだろうけれど

&tags()

2015/11/16