21 Aug 2009 | Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, Zoubin Ghahramani
The paper introduces Kronecker graphs as a new generative model for networks that are both mathematically tractable and capable of capturing the structural properties of real networks. The main idea is to use the Kronecker product of matrices to create self-similar graphs, which naturally exhibit heavy-tailed degree distributions, small diameters, and other structural features observed in real networks. The authors prove that Kronecker graphs follow the densification power law and have constant diameters, and provide empirical evidence of their effectiveness in modeling real-world networks. They also present KRONFIT, an efficient algorithm for fitting Kronecker graphs to large networks, which scales linearly in time and can handle networks with millions of nodes and edges. Experiments on various real and synthetic networks show that Kronecker graphs can accurately model the statistical properties of target networks using only four parameters. The paper discusses the benefits of using Kronecker graphs for network analysis, including insights into network structure, null-models, simulations, extrapolations, sampling, graph similarity, visualization, and anonymization.The paper introduces Kronecker graphs as a new generative model for networks that are both mathematically tractable and capable of capturing the structural properties of real networks. The main idea is to use the Kronecker product of matrices to create self-similar graphs, which naturally exhibit heavy-tailed degree distributions, small diameters, and other structural features observed in real networks. The authors prove that Kronecker graphs follow the densification power law and have constant diameters, and provide empirical evidence of their effectiveness in modeling real-world networks. They also present KRONFIT, an efficient algorithm for fitting Kronecker graphs to large networks, which scales linearly in time and can handle networks with millions of nodes and edges. Experiments on various real and synthetic networks show that Kronecker graphs can accurately model the statistical properties of target networks using only four parameters. The paper discusses the benefits of using Kronecker graphs for network analysis, including insights into network structure, null-models, simulations, extrapolations, sampling, graph similarity, visualization, and anonymization.