Scalable modeling of real graphs using Kronecker multiplication

ABSTRACT

Given a large, real graph, how can we generate a synthetic graph that matches its properties, i.e., it has similar degree distribution, similar (small) diameter, similar spectrum, etc? We propose to use "Kronecker graphs", which naturally obey all of the above properties, and we present KronFit, a fast and scalable algorithm for fitting the Kronecker graph generation model to real networks. A naive approach to fitting would take super-exponential time. In contrast, KronFit takes linear time, by exploiting the structure of Kronecker product and by using sampling. Experiments on large real and synthetic graphs show that KronFit indeed mimics very well the patterns found in the target graphs. Once fitted, the model parameters and the resulting synthetic graphs can be used for anonymization, extrapolations, and graph summarization.

REFERENCES

• 1: Albert, R., & Barabasi, A.-L. (1999). Emergence of scaling in random networks. Science, 509--512.
• 2: Albert, R., & Barabáási, A.-L. (2002). Statistical mechanics of complex networks. Reviews of Modern Physics.
• 3: Bezáková, I., Kalai, A., & Santhanam, R. (2006). Graph model selection using maximum likelihood. ICML.
• 4: Butts, C. T. (2005). Permutation models for relational data(Tech. Rep. MBS 05-02). Univ. of California, Irvine.
• 5: Deepayan Chakrabarti , Christos Faloutsos, Graph mining: Laws, generators, and algorithms, ACM Computing Surveys (CSUR), v.38 n.1, p.2-es, 2006 [doi>http://doi.acm.org/10.1145/1132952.1132954]
• 6: Chakrabarti, D., Zhan, Y., & Faloutsos, C. (2004). R-MAT: A recursive model for graph mining. SDM.
• 7: Efron, B. (1975). Defining the curvature of a statistical problem (with applications to second order efficiency). Ann. Statist., 3, 1189--1242.
• 8: Erdos, P., & Renyi, A. (1960). On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Acadamy of Science, 5, 17--67.
• 9: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 10: Gamerman, D. (1997). Markov chain monte carlo, stochastic simulation for bayesian inference. Chapman & Hall.
• 11: Kleinberg, J. M., Kumar, S. R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (1999). The web as a graph: Measurements, models and methods. COCOON.
• 12: Leskovec, J., Chakrabarti, D., Kleinberg, J. M., & Faloutsos, C. (2005). Realistic, mathematically tractable graph generation and evolution, using kronecker multiplication. PKDD (pp. 133--145).
• 13: Milgram, S. (1967). The small-world problem. Psychology Today, 2, 60--67.
• 14: Redner, S. (1998). How popular is your paper? an empirical study of the citation distribution. European Physical Journal B, 4, 131--134.
• 15: Richardson, M., Agrawal, R., & Domingos, P. (2003). Trust management for the semantic web. ISWC.
• 16: Schwarz, G. (1978). Estimating the dimension of a model. The Annals of Statistics, 6, 461--464.
• 17: Stumpf, M. P. H., Wiuf, C., & May, R. M. (2005). Subnets of scale-free networks are not scale-free: Sampling properties of networks. PNAS, 102.
• 18: Wasserman, S., & Pattison, P. (1996). Logit models and logistic regressions for social networks. Psychometrika, 60, 401--425.
• 19: Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks. Nature, 393, 440--442.
• 20: Wiuf, C., Brameier, M., Hagberg, O., & Stumpf, M. P. (2006). A likelihood approach to analysis of network data. PNAS, 103, 7566--7570.