読者です 読者をやめる 読者になる 読者になる

Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks

WWW 2011

目的

  • インメモリに載せたい,隣接リストを高速に取得できるようにしたい

既存手法 (BV)

  • 頂点をいいかんじに並べる(similarity, locality)
  • 隣接点が似ている頂点との差分で覚える (copying)
  • 頂点番号の差分で覚える (gap strategy)
  • など
問題点

頂点の並べ方が重要

  • Web Graph: URL でソートすればいいw 高性能
  • Social Network: 性能が出ない

提案手法

コミュニティ検出手法を使おう!クラスタ内の頂点は似ているはず.

並べるアルゴリズム

今の順番がある.ランダムな適当なリソリューションでやって,代表元をとってそれのもとのじゅんでならびかえる.

実験結果

良くなった.既存の手法は,頂点の元の順番に意味があることを利用してしまっていた.

ウェブグラフははるかに簡単で,ソーシャルは難しい.ソーシャルでも,Co-authorやHollywoodみたいなクリークが多い感じのネットワークでは簡単.

でも結局,3倍とかにしか圧縮しかできなくて,それのために十倍とか百倍とか遅くなるのは,許せるのか?