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
-
問題設定
-
入力
-
目的
-
基本的には辺を足すだけ、頂点もちょっとだけ足せる
-
コスト: |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