Information Theoretic Comparison of Stochastic Graph Models: Some Experiments

author: Kevin J. Lang, Yahoo! Research Silicon Valley
published: March 12, 2009,   recorded: February 2009,   views: 3332

See Also:

Download slides icon Download slides: waw09_lang_itesgm_01.pdf (108.0 KB)

Help icon Streaming Video Help

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


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.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: