Kronecker graphs: an approach to modeling networks. 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.

References in zbMATH (referenced in 25 articles , 1 standard article )

Showing results 1 to 20 of 25.
Sorted by year (citations)

1 2 next

  1. Achlioptas, Dimitris; Siminelakis, Paris: Symmetric graph properties have independent edges (2018)
  2. Banaszak, Justyna; Łuczak, Tomasz: On the diameter of Kronecker graphs (2018)
  3. Ekinci, Gülnaz Boruzanli; Kirlangic, Alpay: The super edge connectivity of Kronecker product graphs (2018)
  4. Sless, Liat; Hazon, Noam; Kraus, Sarit; Wooldridge, Michael: Forming $k$ coalitions and facilitating relationships in social networks (2018)
  5. Zarezade, Ali; De, Abir; Upadhyay, Utkarsh; Rabiee, Hamid R.; Gomez-Rodriguez, Manuel: Steering social activity: a stochastic optimal control point of view (2018)
  6. Drakopoulos, Georgios; Kanavos, Andreas; Tsakalidis, Konstantinos: Fuzzy random Walkers with second order bounds: an asymmetric analysis (2017)
  7. Haghir Chehreghani, Mostafa; Abdessalem, Talel: Upper and lower bounds for the $q$-entropy of network models with application to network model selection (2017)
  8. Sharma, Rohan; Adhikari, Bibhas; Mishra, Abhishek: Structural and spectral properties of corona graphs (2017)
  9. Banaszak, Justyna: On matchings in stochastic Kronecker graphs (2016)
  10. Boruzanlı Ekinci, Gülnaz; Kırlangiç, Alpay: Super connectivity of Kronecker product of complete bipartite graphs and complete graphs (2016)
  11. Gupta, Rishi; Roughgarden, Tim; Seshadhri, C.: Decompositions of triangle-dense graphs (2016)
  12. Sayama, Hiroki: Estimation of Laplacian spectra of direct and strong product graphs (2016)
  13. Achlioptas, Dimitris; Siminelakis, Paris: Symmetric graph properties have independent edges (2015)
  14. Dehghani, Sina; Fazli, Mohammad Amin; Habibi, Jafar; Yazdanbod, Sadra: Using shortcut edges to maximize the number of triangles in graphs (2015)
  15. Du, Lingxia; Li, Cuiping; Chen, Hong; Tan, Liwen; Zhang, Yinglong: Probabilistic SimRank computation over uncertain graphs (2015)
  16. Johnson, Matthew; van Leeuwen, Erik Jan; Paulusma, Daniël: What graphs are 2-dot product graphs? (2015)
  17. Kang, Mihyun; Karoński, Michał; Koch, Christoph; Makai, Tamás: Properties of stochastic Kronecker graphs (2015)
  18. Berger, Noam; Borgs, Christian; Chayes, Jennifer T.; Saberi, Amin: Asymptotic behavior and distributional limits of preferential attachment graphs (2014)
  19. Chattopadhyay, Swarup; Murthy, C. A.; Pal, Sankar K.: Fitting truncated geometric distributions in large scale real world networks (2014)
  20. Crescenzi, Pilu; Grossi, Roberto; Habib, Michel; Lanzi, Leonardo; Marino, Andrea: On computing the diameter of real-world undirected graphs (2013)

1 2 next