Influence Blocking Maximization in Social Networks under the Competitive ...

Influence Blocking Maximization in Social Networks under the Competitive Linear Threshold Model

  • Xinran He, Guojie Song, Wei Chen, Qingye Jiang
  • SDM 2012

概要

  • Competitive Linear Threshold モデルを考えたよ
  • 目的関数は自分の最大化じゃなくて,相手の最大化だよ
  • そうするとこのモデルではsubmodularだよ
  • 目的関数の計算が大変なのでPMIAっぽいものを作った

Competitive Linear Threshold Model

  • 各辺には2つの重みw+とw-がある
  • 各頂点の閾値も2つθ+とθ-
  • 状態はinactive,-active,+activeの3つ
  • 基本的には普通に拡散していく,早い者勝ち
  • 同時だったら-activeの方が強い
    The negative dominance rule reflects the negativity
    bias phenomenon well studied in social psychology, and
    matches the common sense that rumors are usually hard to
    fight with.
    
  • Threshold Models for Competitive Influence in Social Networksとほぼ同じ
    • -activeの方が強いか,確率的かの違い
    • ほぼ影響なし

Influence Blocking Maximization Problem

  • IBS(S,N | θ+, θ-) = Sがいないと-activeだけど, Sがいると-activeでない頂点集合
    • 閾値が与えられた元なので決定的
  • σ_NIR(S) = E[IBS(S|θ+,θ-)]
  • 上を最大化したい

CLDAG Algorithm for the IBM Problem

  • 省略
  • ちょっとDPするっぽい?

実験

  • 良さそうに見える?
  • 提案手法のσの増加量が変なんだが…
  • 散布図の線分を曲線で補間しないでくれ(怒

まとめ

  • 目新しさ無し

SDM 影響最大化 情報拡散モデル

2014-09-23 00:16:05 (Tue)

最終更新:2014年09月23日 00:16