An In-Depth Study of Stochastic Kronecker Graphs

ICDM に参加中の村田先生からのメッセージ。

"An In-Depth Study of Stochastic Kronecker Graphs"
C. Seshadhri, Ali Pinar, and Tamara G. Kolda,
Proceedings of the 11th IEEE International Conference on
Data Mining, pp.587-596, 2011.
http://arxiv.org/abs/1102.5046

タイトルの通り、(Graph500で用いられる)Kronecker Graphの研究です。発表を聞いただけで論文はまだ読んでいないのですが、
・次数分布はheavy tailでもpower lawでもなく、論文中の図の
ように何度もバウンドしたような曲線になる
・ノイズを入れたnoisy SKGになると次数分布が直線に近づく
・孤立点が多い。k=42で74%が孤立点
・coreのサイズは実ネットワークのそれより小さい