Fast Robustness Estimation in Large Social Graphs: Communities and Anomaly Detection
-
Fragkiskos D. Malliaros, Vasileios Megalooikonomou, Christos Faloutsos
-
SDM 2012
概要だけ
-
頂点は閉路の数が多いほど重要と考える
-
部分グラフ中心性(物理側から持ってきた)
-
$$ \mathrm{SC}(v) = \sum_{i} u_{vi}^2 \sinh(\lambda_i) $$
-
i番目の固有ベクトルのv要素目
-
まとめると
-
$$ \xi(G) = \sqrt{ \frac{1}{|V|}\sum_{v} \left\{ \log(u_{v1}) - (\log A + \frac{1}{2}\log(\mathrm{SC(i)})) \right\}^2 } $$
-
計算がダルいので、ちょっと端折ります
-
上位k固有値だけについて勘定する
-
で、正規化っぽいことをする
-
log-logプロットすると、固有ベクトルの各値と正規化部分グラフ中心性は線形相関を持つ
-
ERだと、それっぽい
-
小さい共著ネットワークだとダメぽ
-
デカイグラフだとまぁまぁ良い感じ
-
$$ \xi(G) $$(の簡易版)の追跡をすると、異常検知に使えるっぽいよ~
まとめ
SDM 中心性 頑健性
2016/05/13
最終更新:2016年05月13日 00:13