Graph model selection using maximum likelihood

ABSTRACT

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.

REFERENCES

• 1: William Aiello , Fan Chung , Linyuan Lu, A random graph model for massive graphs, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.171-180, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335326]
• 2: Barabási, A., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286, 509--512.
• 3: Barabási, A. L., Albert, R., & Jeong, H. (2000). Scale-free characteristics of random networks: topology of the world-wide web. Physica A, 281, 69.
• 4: Barabási, A.-L., & Oltvai, Z. (2004). Network biology: Understanding the cells functional organization. Nature Reviews Genetics, 5, 101--113.
• 5: Bollobás, B. (1985). Random graphs. Academic Press.
• 6: Bork, P., Jensen, L., von Mering, C., Ramani, A., Lee, I., & Marcotte, E. (2004). Protein interaction networks from yeast to human. Current Opinion in Structural Biology, June 14(3), 292--9.
• 7: Bu, T., & Towsley, D. F. (2002). On distinguishing between internet power law topology generators. Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Society (INFOCOM-02) (pp. 638--647).
• 8: Chen, S., Beeeferman, D., & Rosenfeld, R. (1998). Evaluation metrics for language models. DARPA Broadcast News Transcription and Understanding Workshop.
• 9: Chen, S., & Rosenfeld, R. (1999). Efficient sampling and feature selection in whole sentence maximum entropy language models. Proceedings of ICASSP '99.
• 10: CONDOR (2005). University of Wisconsin at Madison. http://www.cs.wisc.edu/condor/.
• 11: Lixin Gao, On inferring autonomous system relationships in the internet, IEEE/ACM Transactions on Networking (TON), v.9 n.6, p.733-745, December 2001 [doi>10.1109/90.974527]
• 12: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 13: Kubica, J., Moore, A., Cohn, D., & Schneider, J. (2003). Finding underlying connections: A fast graph-based method for link analysis and collaboration queries. Proceedings of Twentieth International Conference on Machine Learning.
• 14: László Lovász , Santosh Vempala, Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.650, October 11-14, 2003
• 15: Alberto Medina , Ibrahim Matta , John Byers, On the origin of power laws in Internet topologies, ACM SIGCOMM Computer Communication Review, v.30 n.2, April 2000 [doi>10.1145/505680.505683]
• 16: Mitzenmacher, M. (2001). A brief history of generative models for power law and log normal distributions. Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing (pp. 182--191).
• 17: NLANR (2001). National Laboratory for Applied Network Research Routing data. http://moat.nlanr.net/Routing/rawdata/.
• 18: Rissanen, J. (1978). Modeling by shortest data description. Automatica, 14, 265--271.
• 19: Georgos Siganos , Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, Power laws and the AS-level internet topology, IEEE/ACM Transactions on Networking (TON), v.11 n.4, p.514-524, August 2003 [doi>10.1109/TNET.2003.815300]
• 20: Hongsuda Tangmunarunkit , Ramesh Govindan , Sugih Jamin , Scott Shenker , Walter Willinger, Network topology generators: degree-based vs. structural, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 21: Watts, D., & Strogatz, S. (1998). Collective dynamics of 'small-world' networks. Nature, 393, 440--442.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Statistical computing

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Theory