Graph Model Selection using the Minimum Description Length Principle

In recent years, there has been a proliferation of theoretical graph models, e.g., preferential attachment, motivated by real-world graphs such as the Web or Internet topology. Typically these models are designed to mimic particular properties observed in the graphs, such as power-law degree distribution or the small-world phenomenon. The mainstream approach to comparing models for these graphs has been somewhat subjective and very application dependent — comparisons are often based on ad hoc graph properties. We use the Minimum Description Length principle to compare graph models: models are scored based on the degree of compression that they achieve on real data. This principle is popular across fields for various types of model selection because it is objective and not application specific. Unfortunately, computing this metric is usually a daunting algorithmic task, especially for existing models that were not designed with this metric in mind. To illustrate the feasibility of our approach, we design and implement sophisticated algorithms for computing the description length for four natural models: a power-law random graph model, a preferential attachment model, a small-world model, and a uniform random graph model. Based on experiments on three snapshots of the Internet topology graph, we find that the preferential attachment model ranks highest, while the uniform random graph model performs the worst. We hope that this metric will enable a more objective model comparison and the development of improved models. Categories and Subject Descriptors D.2.8 [Software Engineering]: Metrics—complexity measures, performance measures; F.2 [Theory of Computation]