KronFit

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 36 articles , 1 standard article )

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

1 2 next

  1. Conte, Alessio; Grossi, Roberto; Marino, Andrea: Large-scale clique cover of real-world networks (2020)
  2. Fox, Jacob; Roughgarden, Tim; Seshadhri, C.; Wei, Fan; Wein, Nicole: Finding cliques in social networks: a new distribution-free model (2020)
  3. Lin, Ruizhi; Zhang, Heping; Zhao, Weisheng: Matching preclusion for direct product of regular graphs (2020)
  4. Yousuf, Muhammad Irfan; Kim, Suhyun: Generating graphs by creating associative and random links between existing nodes (2020)
  5. Kotzagiannidis, M. S.; Dragotti, P. L.: Splines and wavelets on circulant graphs (2019)
  6. Ramani, Arjun S.; Eikmeier, Nicole; Gleich, David F.: Coin-flipping, Ball-dropping, and Grass-hopping for generating random graphs from matrices of edge probabilities (2019)
  7. Zheng, Zemin; Bahadori, M. Taha; Liu, Yan; Lv, Jinchi: Scalable interpretable multi-response regression via SEED (2019)
  8. Achlioptas, Dimitris; Siminelakis, Paris: Symmetric graph properties have independent edges (2018)
  9. Banaszak, Justyna; Łuczak, Tomasz: On the diameter of Kronecker graphs (2018)
  10. Ekinci, Gülnaz Boruzanli; Kirlangic, Alpay: The super edge connectivity of Kronecker product graphs (2018)
  11. Moreno, Sebastian; Pfeiffer, Joseph J. III; Neville, Jennifer: Scalable and exact sampling method for probabilistic generative graph models (2018)
  12. Sless, Liat; Hazon, Noam; Kraus, Sarit; Wooldridge, Michael: Forming (k) coalitions and facilitating relationships in social networks (2018)
  13. Zarezade, Ali; De, Abir; Upadhyay, Utkarsh; Rabiee, Hamid R.; Gomez-Rodriguez, Manuel: Steering social activity: a stochastic optimal control point of view (2018)
  14. Drakopoulos, Georgios; Kanavos, Andreas; Tsakalidis, Konstantinos: Fuzzy random Walkers with second order bounds: an asymmetric analysis (2017)
  15. Haghir Chehreghani, Mostafa; Abdessalem, Talel: Upper and lower bounds for the (q)-entropy of network models with application to network model selection (2017)
  16. Jurkiewicz, Marcin: Average distance is submultiplicative and subadditive with respect to the strong product of graphs (2017)
  17. Sharma, Rohan; Adhikari, Bibhas; Mishra, Abhishek: Structural and spectral properties of corona graphs (2017)
  18. Banaszak, Justyna: On matchings in stochastic Kronecker graphs (2016)
  19. Boruzanlı Ekinci, Gülnaz; Kırlangiç, Alpay: Super connectivity of Kronecker product of complete bipartite graphs and complete graphs (2016)
  20. Gupta, Rishi; Roughgarden, Tim; Seshadhri, C.: Decompositions of triangle-dense graphs (2016)

1 2 next