Information theoretic comparison of stochastic graph models: some experiments. (English) Zbl 1207.05183

Lang, Kevin J.

Avrachenkov, Konstantin (ed.) et al., Algorithms and models for the web-graph. 6th international workshop, WAW 2009, Barcelona, Spain, February 12–13, 2009. Proceedings. Berlin: Springer (ISBN 978-3-540-95994-6/pbk). Lecture Notes in Computer Science 5427, 1-12 (2009).

Summary: The Modularity-Q measure of community structure is known to falsely ascribe community structure to random graphs, at least when it is naively applied. Although Q is motivated by a simple kind of comparison of stochastic graph models, it has been suggested that a more careful comparison in an information-theoretic framework might avoid problems like this one. Most earlier papers exploring this idea have ignored the issue of skewed degree distributions and have only done experiments on a few small graphs. By means of a large-scale experiment on over 100 large complex networks, we have found that modeling the degree distribution is essential. Once this is done, the resulting information-theoretic clustering measure does indeed avoid Q’s bad property of seeing cluster structure in random graphs.
For the entire collection see [Zbl 1154.68003].

MSC:

05C80	Random graphs (graph-theoretic aspects)
05C82	Small world graphs, complex networks (graph-theoretic aspects)