2.5K-Graphs: from Sampling to Generation

2.5K-Graphs: from Sampling to Generation

  • Minas Gjoka, Maciej Kurant, Athina Markopoulou
  • INFOCOM 2013

概要

  • 2.5K-graph
  • 次数kの頂点と次数lの頂点を結ぶ辺の個数の分布と、次数kの頂点のクラスタ係数の平均値を分布に着目
  • ソーシャルネットワークから↑を高速に見積もり、そういう分布になるグラフも生成する
  • ↑以外の分布も結構一致する!

問題

  • JDD(k,l) = 次数kの頂点と次数lの頂点を結ぶ辺の数
    • JDD = Joint Degree Distribution
    • 2頂点の部分グラフの次数依存の分布
  • ‾c(k) = 次数kの頂点のクラスタ係数の平均値
  • dk-series
    • 0K: 平均次数
    • 1K: 1頂点の次数分布
    • 2K: JDD
    • 3K: 次数k,l,mの頂点の三角形とwedgeの個数
    • dKについてdが増えたほうが細かくなる、でも計算がやばめ
  • 2.25Kと2.5Kは?
    • 2.25K: JDDと‾c
    • 2.5K: JDDと‾c(k)
  • 2.5Kに今回注目するよ!
  • 問題定義
    • Estimation: JDD(k,l)と‾c(k)をランダムウォークから見積もる
    • Graph Generation: ↑で求めたパラメータを持つグラフを構築する(非自明に)

Estimation

  1. Uniform Independence Sampling (UIS)
    • 等確率で頂点をサンプルするとして見積もる
  2. Weighted Independence Sampling (WIS)
    • 各頂点をw(u)の重みに従いサンプル、でもw(v)=deg(v)にしちゃう
  3. Simple Random Walk (RW)
    • WISと同じじゃね????
    • パスがあるから違うか…
  • 後処理
    • Smoothing
      • Gaussian Kernel Smoothingとかしちゃう(幅とって重み付けするやつかな?)
    • Realizable JDD
      • 長い(´・ω・`)

Generating a 2.5K Graph

  • アホっぽいやりかたMCMC
    • JDD(k,l)の分布をどうにか一致させられたとする
    • 適当に辺を2つ選んで、クラスタ係数の分布が近くなったら更新する、ただし、JDDが変化しないように
    • 三角形がボカスカ壊れるので、無理ゲー

Our 2.5K generator

  1. 頂点vに乱数r_vを設定する
  2. dist(u,v) = min(|r_v-r_u|, 1-|r_v-r_u|)で辺をソート
    • 境界がない1次元[0,1]での距離
  3. JDDや次数が見積もったのを超えないならば辺を追加していく
  • 何がうれしいの?
    • 辺がローカルに密集する、distでソートしたから
    • つまり、クラスタ係数がでかい感じでJDD、次数分布を一致させられる
  • これをしてからdouble-edge swapsでクラスタ係数を近づける

実験

  • 基本ベクトルなので、Normalized Mean Absolute Errorで測る
  • クラスタ係数分布…結構いい感じ
  • JDD…smoothingが偉大だった
  • 生成速度
    • {2K-T, 2K} × {Imp. MCMC, MCMC}の組み合わせ
    • 2K-Tは提案したやつ、2Kは既存手法
    • Imp.MCMC は何か頑張ったらしい
    • 2K-Tはかなり速い、Imp. MCMCと組み合わせるとベスト!
    • 何でか?
    • 時間に対する収束度合いを見ると、2Kはクラスタ係数をじわじわ上げていかなきゃならんのに対し、2K-Tは高いところからストンと落とせばいいだけ
  • 他の性質も似てるかな?
  1. The degree distribution
  2. Edgewise shared partner distribution
  3. Shortest path distribution
  4. Maximal clique distribution
  5. Cycles distribution
  6. Spectrum
  7. Closeness centrality
  • 2Kはどうにも元のグラフと合わない、2.5Kは最大クリークを除いてかなり似ている(実際に結構一致していると思った

まとめ

  • タイトルが謎すぎてほったらかしていたが思いの他面白かった
  • グラフの生成に対するこういうアプローチは既にアッたんだなあと思った
  • 手法がシンプルな割に三角形いっぱいつくるぞーって感じで面白い
  • 他の性質にはむしろモチーフを使って欲しかった?
  • 3.5Kにまで拡張したらどうなるか知りたい

INFOCOM clustering coefficient degree distribution random walk

2014-01-01 03:54:31 (Wed)

最終更新:2014年01月01日 03:54