Influence maximization in complex networks through optimal percolation - todo314 @ ウィキ

Influence maximization in complex networks through optimal percolation

• Flaviano Morone, Hernán A. Makse
• Nature 2015

概要

• 頂点を削除して最大の連結成分を最小化したい
  • 強影響力頂点抽出，immunization，コミュニティ検出
• 既存手法…ヒューリスティクス
• 本手法
  • 最適化問題
  • ある種の貪欲アルゴリズム

輪郭

1. 最適パーコレーション
2. 固有値の最小化問題
3. 上を解く

最適パーコレーション

• $$ \nu_i $$の計算