Kronecker Graphs: An Approach to Modeling Networks

By Jure Leskovec, Deepayan Chakrabarti, Jon M. Kleinberg, Christos Faloutsos, Zoubin Ghahramani. 2008

1,118 citations recorded by the source corpus.

How can we generate realistic networks? In addition, how can we do so with a mathematically tractable model that allows for rigorous analysis of network properties? Real networks exhibit a long list of surprising properties: Heavy tails for the in- and out-degree distribution, heavy tails for the eigenvalues and eigenvectors, small diameters, and densification and shrinking diameters over time. Current network models and generators either fail to match several of the above properties, are complicated to analyze mathematically, or both. Here we propose a generative model for networks that is both mathematically tractable and can generate networks that have all the above mentioned structural properties. Our main idea here is to use a non-standard matrix operation, the Kronecker product, to generate graphs which we refer to as "Kronecker graphs". First, we show that Kronecker graphs naturally obey common network properties. In fact, we rigorously prove that they do so. 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 a wide range of large real and synthetic networks show that KRONFIT finds accurate parameters that very well mimic the properties of target networks. In fact, using just four parameters we can accurately model several aspects of global network structure. 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.

Subfields: Geometry and Topology, Molecular Biology, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

In Molecular Biology

In Statistical and Nonlinear Physics

Citations in the corpus

Graphite: Iterative Generative Modeling of Graphs (2018, background): “small diameter and hence the generated graphs exhibit strong local clustering (Watts and Strogatz, 1998), the Barabasi-Albert models preferential attachment whereby nodes high-degree nodes are likely to form edges with newly added nodes (Barabasi and Albert, 1999), and Kronecker graph models generat”
GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models (2018, methodology): “In addition, we compare against popular generative models that include learnable parameters: Kronecker graph models (Leskovec et al., 2010) and mixed-membership stochastic block models (MMSB) (Airoldi et al., 2008).”
Learning Deep Generative Models of Graphs (2018, background): “Interested readers can also refer to (Leskovec et al., 2010; Vinyals et al., 2015a; Stewart et al., 2016) for discussions of similar ordering issues from different angles.”
Permutation Invariant Graph Generation via Score-Based Generative Modeling (2020, background): “, 2019), as well as research in network science (Watts and Strogatz, 1998; Albert and Barabási, 2002; Leskovec et al., 2010).”
GraphRNN: A Deep Generative Model for Graphs (2018, methodology): “In addition, we compare against popular generative models that include learnable parameters: Kronecker graph models (Leskovec et al., 2010) and mixed-membership stochastic block models (MMSB) (Airoldi et al., 2008).”
SNAP: A General Purpose Network Analysis and Graph Mining Library (2016, methodology): “Complete graphs, circles, grids, stars, and trees; Basic random graphs Erd ˝ os-R ´ enyi graphs, Bipartite graphs, Graphs where each node has a constant degree, Graphs with exact degree sequence; Advanced graph models Conﬁguration model [Bollob´as 1980], Ravasz-Barabasi model [Ravasz and Barab´asi 2”
Introduction to MAchine Learning & Knowledge Extraction (MAKE) (2017, background): “(2010) [79] asked themselves the interesting question "How can we generate synthetic, but realistic looking, time-evolving graphs?".”
Evolution of social-attribute networks: measurements, modeling, and implications using google+ (2012, background): “…set E s , while links between social nodes and attribute nodes are called attribute links and de-social For a given social or attribute node u in a SAN, we denote its attribute neighbors as Γ a ( u ) = { v | v ∈ V a , ( u, v ) ∈ E a } , social neighbors as Γ s ( u ) = { v | v ∈ V s , ( v, u ) ∈…”
Hierarchical block structures and high-resolution model selection in large networks (2013, methodology): “[51] as well. the edge and node counts associated with the block partition { b i } , and Ω( { e rs } , { n r } ) is the number of diﬀerent network realizations.”
Influence Maximization in Continuous Time Diffusion Networks (2012, methodology): “(a) 35-node core-periphery Kronecker network.”
Modeling Information Propagation with Survival Theory (2013, methodology): “First we generate realistic synthetic networks using the Kronecker graph model (Leskovec et al., 2010), and set the edge hazard function parameters α j,i randomly, drawn from a uniform distribution.”
Quantifying Information Overload in Social Media and Its Impact on Social Contagions (2014, methodology): “To this aim, we ﬁrst generate a network G = ( V , E ) using a well-known mathematical model of social networks: the Kronecker model (Leskovec et al. 2010), and set the out-ﬂow rate of each node in the network by drawing samples from λ i ∼ N ( µ, σ ) , where µ is the average out-ﬂow rate.”
A Survey of Statistical Network Models (2009, methodology): “has turned into a well analyzed methodology [195] with an efficient algorithm for model fitting, analysis of the parameter space, and model selection.”
Constrained Graph Variational Autoencoders for Molecule Design (2018, neutral): “[20] do account for edge correlations, but they are hand-crafted into the models.”
Mizan: a system for dynamic load balancing in large-scale graph processing (2013, methodology): “We also generated synthetic datasets using the Kronecker [21] generator that models the structure of real life networks.”
Microscopic Social Influence (2012, methodology): “Mean-while, product network, especially Kronecker product has been applied to model graph generation [25] and dynamic tensor analysis [26].”
Asymptotic behavior and distributional limits of preferential attachment graphs (2014, background): “Note, however, that we do not cover models exhibiting densification in the sense of Leskovec, Kleinberg and Faloutsos [19]; see [18] for a mathematical model exhibiting this phenomenon.”