Fast Robustness Estimation in Large Social Graphs: Communities and Anomaly ...

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

タグ:

SDM 頑健性 中心性
最終更新:2016年05月13日 00:13