Delineating Social Network Data Anonymization via Random Edge Perturbation

Delineating Social Network Data Anonymization via Random Edge Perturbation

  • Mingqiang Xue, Panagiotis Karras, Chedy Raissi, Panos Kalnis, Hung Keng Pung
  • CIKM 2012

概要

  • random edge perturbation によるグラフの匿名化
  • 上を攻撃する手法
  • グラフの特徴量を推定

Random Edge Perturbation

  • 辺を確率μで独立に足したり消したりする
    • XORってこと
    • denseになるけどいいや

色々推定

  • ※μは公開するとして良い

密度

  • μが分かるので、てきとーにやればいい** 次数分布
  • 同上
  • 色々指標あるけど、全部気合でやればいい

攻撃手法

  • walk-based attack
    • 例のアレ
  • 新テク1: interval degree check
    • 頂点の次数が、期待値±wに入るか調べる
  • 新テク2: error-tolerant edge check
    • m箇所まで違っていても良い
  • 解析すると…?良いらしい
  • 攻撃側は何か頑張る

実験

  • オリジナルのwalk-based attackはμがでかくなるとすぐ死ぬ
  • まぁ、後は、よくある考察

CIKM anonymization

2014-01-30 17:19:43 (Thu)

タグ:

CIKM anonymization
最終更新:2014年01月30日 17:19