Mining Social Networks Using Heat Diffusion Processes for Marketing ...

Mining Social Networks Using Heat Diffusion Processes for Marketing Candidates Selection

  • Hao Ma, Haixuan Yang, Michael R. Lyu, Irwin King
  • CIKM 2008

概要

  • 熱拡散過程によるモデリング
  • 3つの拡散モデル,3つのアルゴリズム
  1. 製品採択に時間を入れる
  2. クラスタ(係数)を反映
  3. 正負の意見を伝える

熱拡散モデル

  • 当然,物理現象
    • 分類,次元削減とかに使われている
  • 開発者・ターゲットは熱源として振る舞い,一杯熱を持ってる
  • で,どんどん広がっていく
  • f_t(x,t)=Δf(x,t)
    • f(x,t): 時刻tでの位置xの温度
    • f_tはtによる偏微分

無向グラフ

  • iはjから時刻tでΔtの間にΔM(i,j,t,Δt)の熱をもらう
  • ΔM(i,j,t,Δt) = α(f_j(t)-f_i(t))Δt,とおけば
  • [f_i(t+Δt)-f_i(t)]/Δt = αΣ_j [f_j(t)-f_i(t)]
  • 行列で簡単にかける
  • [f(t+Δt)-f(t)]/Δt = -αLf(t)
  • Δt→0の極限に飛ばして微分方程式を解くと
  • f(t) = exp(-αtL)f(0)
    • exp(・)は(拡散)カーネル
    • 適当なαの元ではある収束状態に向かう

有向グラフ

  • 若干ややこしいパラメータを導入する
  • 基本的には頂点iとその近傍jの温度の線形和が温度の微分係数
  • これも解けるがexpの中の行列がちょっと違う

事前知識+有向グラフ

  • 伝播確率p_ijがわかってる
  • p_ijを考慮した式で表現
  • 解けるけどexpの中…(ry

αの値

  • 高いと拡散が速い,低いと遅い
  • 伝わる情報の内容による
    • 悪いニュースは良いニュースより速い(?)等

候補選択手法

  • シードiに対してはf_i(0)=h_0に設定
  • σ(S) = |{i | f_i(t)≧θ}|
    • θはパラメータ

Top-k

  • 実際に計算する
  • σ({v})の高い順に返す

k-Step Greedy

  • 新しくactive(扱い)になる頂点数が一番多い頂点を選択
    • ゲインでは無い
  • 1-1/e近似が証明できる(らしい

Enhanced k-Step Greedy

  • ゲイン最大を選んでいく

計算量解析

  • 熱拡散過程
  • exp(A)を直接計算するのは大変なので,
  • (I+A/k)^kで近似する
  • O(km)
    • mは辺数
  • 前の節のアルゴリズムは基本的にグラフサイズの自乗近くかかるのでやばお
  • 次数がpower-lawなので次数が低いところはカット☆(ゝω・)vキャピ
    • (゚Д゚)ハァ?

実験

  • 3アルゴリズムの比較
  • Enhanced Greedy,Greedy,Top-kの順で良い
  • 拡散の様子を描画しているのは珍しい
    • 真ん中当たりがアツい感じ
  • negativeの創り方
    • 温度を負にします
    • それをディフェンスするヒューリスティクスも考案
      • 実験するとちょっと良くなった

まとめ

  • 確率過程じゃない
  • 次数で削減はいただけないけれど,熱拡散をこっちにもってきたのは良さそう
  • 式も閉じている(カーネル計算が大変だけど
  • 振動するようなモデリングって面白そうだが,意味としてどうなんだろう

CIKM influence maximization modeling

2014-03-25 23:35:11 (Tue)

最終更新:2014年03月25日 23:35