Published on Mon Dec 29 2008

Kronecker Graphs: An Approach to Modeling Networks

Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, Zoubin Ghahramani

Kronecker graphs are mathematically tractable and can be used to model real networks. They can also be used for null-models, summarization, and other applications.

1
0
1
Abstract

How can we model networks with a mathematically tractable model that allows for rigorous analysis of network properties? Networks exhibit a long list of surprising properties: heavy tails for the degree distribution; small diameters; and densification and shrinking diameters over time. Most present network models either fail to match several of the above properties, are complicated to analyze mathematically, or both. In this paper we propose a generative model for networks that is both mathematically tractable and can generate networks that have the above mentioned properties. Our main idea is to use the Kronecker product to generate graphs that we refer to as "Kronecker graphs". First, we prove that Kronecker graphs naturally obey common network properties. We also provide empirical evidence showing that Kronecker graphs can effectively model the structure of real networks. We then present KronFit, a fast and scalable algorithm for fitting the Kronecker graph generation model to large real networks. A naive approach to fitting would take super- exponential time. In contrast, KronFit takes linear time, by exploiting the structure of Kronecker matrix multiplication and by using statistical simulation techniques. Experiments on large real and synthetic networks show that KronFit finds accurate parameters that indeed very well mimic the properties of target networks. Once fitted, the model parameters can be used to gain insights about the network structure, and the resulting synthetic graphs can be used for null- models, anonymization, extrapolations, and graph summarization.

Tue Dec 29 2009
Machine Learning
A survey of statistical network models
Probability models on graphs date back to 1959. The growth of the World Wide Web and the emergence of onlinenetworking communities such as Facebook, MySpace, and LinkedIn has intensified interest in the study of networks.
0
0
0
Fri Nov 14 2014
Machine Learning
A unified view of generative models for networks: models, methods, opportunities, and challenges
Research on probabilistic models of networks now spans a wide variety of fields, including physics, sociology, biology, statistics, and machine learning. Differences between models generally stem from different philosophical choices about how to learn from data. The highly interdisciplinary nature of work on these generative models has
0
0
0
Fri Jan 06 2017
Machine Learning
Estimation of Graphlet Statistics
Graphlets are induced subgraphs of a large network and are important for understanding and modeling complex networks. Graphlets have been severely limited to applications and domains with relatively small graphs. It is often too expensive to compute graphlets exactly in massive networks with billions of edges.
0
0
0
Fri Oct 19 2018
Machine Learning
Data-driven Analysis of Complex Networks and their Model-generated Counterparts
Data-driven analysis of complex networks has been in the focus of research for decades. We study 400 real-world networks along with 2400 networks generated by five frequently used network models. We find that the correlation profiles of the structural measures of the networks significantly differ across network domains.
0
0
0
Thu Aug 06 2015
Machine Learning
Universal Approximation of Edge Density in Large Graphs
The method is based on non-parametric estimation of edge density in directed multigraphs. The method is both robust and scalable. It is able to extract insightful patterns in the unsupervised learning setting and to provide state of the art accuracy.
0
0
0
Wed Nov 14 2018
Machine Learning
Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
This paper surveys some recent developments in fundamental limits and optimal algorithms for network analysis. We focus on minimax optimal rates in three fundamental problems of network analysis: graphon estimation, community detection, and hypothesis testing.
0
0
0