Graph model selection using maximum likelihood

Ivona Bezáková, Adam Kalai, Rahul Santhanam

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In recent years, there has been a proliferation of theoretical graph models, e.g., preferential attachment and small-world models, motivated by real-world graphs such as the Internet topology. To address the natural question of which model is best for a particular data set, we propose a model selection criterion for graph models. Since each model is in fact a probability distribution over graphs, we suggest using Maximum Likelihood to compare graph models and select their parameters. Interestingly, for the case of graph models, computing likelihoods is a difficult algorithmic task. However, we design and implement MCMC algorithms for computing the maximum likelihood for four popular models: a power-law random graph model, a preferential attachment model, a small-world model, and a uniform random graph model. We hope that this novel use of ML will objectify comparisons between graph models.
Original languageEnglish
Title of host publicationMachine Learning, Proceedings of the Twenty-Third International Conference (ICML 2006), Pittsburgh, Pennsylvania, USA, June 25-29, 2006
Number of pages8
Publication statusPublished - 2006


Dive into the research topics of 'Graph model selection using maximum likelihood'. Together they form a unique fingerprint.

Cite this