Recommendations to Boost Content Spread in Social Networks

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が届く確率
    • 期待値で測っている
  • 問題
  1. ICモデルで#P-hard
    • PMIA的アプローチをする
    • 最も高い確率の経路だけ通るとする
  2. PMIAモデルでも劣モジュラでない
    • モデルを改造(簡易化)
  • 解決法
  1. θ以下の経路は打ち切り
  2. 各経路は独立
    • 経路同士が重複しているけど簡単のため
  • $$ 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