Structure-Preserving Sparsification of Social Networks - todo314 @ ウィキ

Structure-Preserving Sparsification of Social Networks

• Gerd Lindner, Christian L. Staudt, Michael Hamann, Henning Meyerhenke, Dorothea Wagner
• ASONAM 2015

概要

• 疎化したグラフの性質を調べたよ
• "Local Degree"なる単純な手法で実は充分良いよ
• 辺数が元の20%でも、大体保存される

比較手法

• Random Edge (RE)
  • 一様ランダムに辺を選んでいく
• Triangles
  • 属する△の個数の多い辺を順に残す
• Local Similarity (LS)
  • 得点 = J(N(u), N(v))
  • 頂点uに接続する辺は$$ \lfloor d(u)^\alpha \rfloor $$本残す
    • d(u)=2のときとかやばくね？
• Simmelian Backbones (TS, QLS)
  • よく分からんので省略
• Edge Forest Fire (EFF)
  • 森火事で訪問しやすい辺は大事
• Local Degree (LD) 提案手法
  • 各頂点uについて$$ \lfloor d(u)^\alpha \rfloor $$本、高次数頂点に繋がる辺から残す
  • ハブに繋がる辺は残したいらしい

実験

• Facebookのデータセットから100グラフについて平均を取る
• 直径
  • Local Degreeが良い
• クラスタ係数
  • Local Degreeが良い（良すぎ
• 次数・媒介中心性・PageRankの順位相関係数
  • Local Degreeが良いが、割りとRandom edgeも良い
  • Forest Fireが悪すぎるように見える
• コミュニティ（Louvain法）分割／連結成分分割の正規化相互情報量、コミュニティ数
  • 何ともいえない、コミュニティ数はLocal Degreeが良い
  • Random Edgeは変な事になりそうだなとは思う

まとめ

• (ﾟДﾟ)ﾊｧ?
• 適当にやっても大体上手く行きそうというのは同意

ASONAM 疎化

2016/12/25