Delineating Social Network Data Anonymization via Random Edge Perturbation (CIKM'12)

• 問題：匿名化
• 手法 random edge pertubation
  • 一定確率 μ で辺の有無を入れ替える (perturbation probability)
• 特徴量の推定
  • 特徴量は，変化してしまうが，推定ができる（最尤推定する）
  • density, degree distribution, transitivity, modularity
  • 独立でランダムに変更してるので簡単
• 攻撃
  • walk-based attack に新たなテクニックを追加 (probabilistic attack)
  • interval degree check
  • error-tolerant edge check
  • もう少し頑張る一般的な攻撃というのもあるらしい
• 実験
  • とても小さいグラフでしかできない
  • （かなり dense になってしまうのであたりまえ）