Efficiently Anonymizing Social Networks with Reachability Preservation

Efficiently Anonymizing Social Networks with Reachability Preservation

  • Xiangyu Liu, Bin Wang, Xiaochun Yang
  • CIKM 2013

概要

  • 匿名化の話
  • Kleinbergのに考え方は似てる
  • 目標: 個人情報を隠しつつ、なんかのクエリ=到達可能性を処理する

k-degree anonymous

  • 敵がvを次数情報のみから頂点を特定できる確率は1/k以下
  • 有向グラフだけど、in-degとout-degがそれぞれ等しい頂点はk個以上

Reachability Preserving Anonymization

  • 問題設定
  • 入力
    • G=(V,E), 整数k
  • 目的
    • 基本的には辺を足すだけ、頂点もちょっとだけ足せる
    • コスト: |R(G_k)-R(G)|
  • k-匿名性から来ている
    • ↑の特殊版が今回
  • 全辺についてやるとO(n(m+n))でアホっぽい

アルゴリズム

  • 各点を(indeg(v), outdeg(v))に対応させてManhattan距離を考える
  • 何か順序つけて、よさそうなのをとってきて次数をいじる
  • 次数がpower-lawなので、…

コスト最小化

  • R(p): pから到達可能な頂点集合
  • 辺が追加されると変わるのでダルい
  • reachability queryとか必要だけど、intervalで何かデータ構造してる

実験

  • はい。

CIKM anonymization reachability

2015-07-06 23:18:02 (Mon)

最終更新:2015年07月06日 23:18