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
-
Uniform Independence Sampling (UIS)
-
Weighted Independence Sampling (WIS)
-
各頂点をw(u)の重みに従いサンプル、でもw(v)=deg(v)にしちゃう
-
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
-
頂点vに乱数r_vを設定する
-
dist(u,v) = min(|r_v-r_u|, 1-|r_v-r_u|)で辺をソート
-
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は高いところからストンと落とせばいいだけ
-
他の性質も似てるかな?
-
The degree distribution
-
Edgewise shared partner distribution
-
Shortest path distribution
-
Maximal clique distribution
-
Cycles distribution
-
Spectrum
-
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