Negative Influence Minimizing by Blocking Nodes in Social Networks

Negative Influence Minimizing by Blocking Nodes in Social Networks

  • Senzhang Wang, Xiaojian Zhao, Yan Chen, Zhoujun Li, Kai Zhang, Jiali Xia
  • AAAI Workshop 2013

概要

  • ノードを取り除いて影響の拡散を抑えたい!
    • ウイルス,誤情報等
  • Negative Influence Minimization
    • 感染シード(given): I
    • ブロック: S(|S|=k)
    • 目標: minimize σ(I; V-S)
      • Sは感染しない

手法

  • σが小さくなるノードを貪欲に選んでいく

実験

  • 比較対象
    • 出次数,betweenness,PageRank
  • 設定
    • |E|=370K
    • ICモデル p=0.2,0.4
    • 100~200位感染シードを設定
  • 適当なヒューリスティクスはダメ,提案手法はoutperform

まとめ

  • Limiting the Spread of Misinformation in Social Networksとの関連もあり
  • 理論的保証が全く無いが,Future workにあった
    • ``whether it is a matroid''ってどういうことだろう?
  • 既存の研究は少ない?
    • ので,理論的保証を与えられたらすごいなあ…

AAAI contamination minimization

2014-06-18 17:10:18 (Wed)

最終更新:2014年06月18日 17:10