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の実際に使えるのね,遅いだろうけれど
WWW 劣モジュラ 影響最大化
2015/11/16
最終更新:2015年11月16日 00:05