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 になってしまうのであたりまえ)