「Delineating Social Network Data Anonymization via Random Edge Perturbation」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* Locating the Source of Diffusion in Large-Scale Network
- Pedro C. Pinto, Patrick Thiran, Martin Vetterli
- PRL 2012
* 概要
- 情報拡散の話
- 一部の頂点だけを観測して、「「発信源」」を推定する
- モデル化+実験
* モデル
- 辺の時間: 正規分布
-- 負の値はごまかす
- 発信源: uniformly at randomに選択される
- 受信者: 時刻+ソース
-- 他の頂点に伝えない
- 理不尽な仮定はおかない
-- 受信者がネットワークを分離したり、最初の観測時刻だけ記録
* 問題設定
- 入力
-- グラフ: G=(V,E)
-- 分布: μ_e、σ_e
-- 受信者・受信時刻の集合
- 出力
- 発信源s
* アプローチ
** 木なら？
- 受信者は葉にいる
-- あ、はい
- 発信時刻が分かる場合も分からん場合も考える
** 一般の場合
- 仮定
-- 発信源から受信者まで情報は最短経路を伝わる
--- ( ﾟдﾟ)ﾊｧ?
-- BFS木の上を求めてその上で木の場合のをやる
* 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はμがでかくなるとすぐ死ぬ
- まぁ、後は、よくある考察
&tags()
&update()
