An in-depth analysis of stochastic Kronecker graphs

DOI10.1145/2450142.2450149MaRDI QIDQ5395712zbMATH OpenOpenAlexFDO

Authors C. Seshadhri, Ali Pinar, Tamara G. Kolda

Publication date 17 February 2014

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1102.5046

zbMATH Keywords

graph modelsGraph500R-MATstochastic Kronecker graphs (SKG)

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Applications of graph theory (05C90)

Abstract: Graph analysis is playing an increasingly important role in science and industry. Due to numerous limitations in sharing real-world graphs, models for generating massive graphs are critical for developing better algorithms. In this paper, we analyze the stochastic Kronecker graph model (SKG), which is the foundation of the Graph500 supercomputer benchmark due to its favorable properties and easy parallelization. Our goal is to provide a deeper understanding of the parameters and properties of this model so that its functionality as a benchmark is increased. We develop a rigorous mathematical analysis that shows this model cannot generate a power-law distribution or even a lognormal distribution. However, we formalize an enhanced version of the SKG model that uses random noise for smoothing. We prove both in theory and in practice that this enhancement leads to a lognormal distribution. Additionally, we provide a precise analysis of isolated vertices, showing that the graphs that are produced by SKG might be quite different than intended. For example, between 50% and 75% of the vertices in the Graph500 benchmarks will be isolated. Finally, we show that this model tends to produce extremely small core numbers (compared to most social networks and other real graphs) for common parameter choices.

Recommendations

• Stochastic Kronecker graphs
• Stochastic Kronecker Graphs
• Properties of stochastic Kronecker graphs
• scientific article; zbMATH DE number 5994660
• The Kronecker theory of power law graphs

Cited in

(12)

• On the diameter of Kronecker graphs
• The Kronecker-clique model for higher-order clustering coefficients
• Sampling online social networks by random walk with indirect jumps
• Kronecker graphs: an approach to modeling networks
• A mathematical analysis of the R-MAT random graph generator
• The Kronecker theory of power law graphs
• The hitting time of multiple random walks
• Moment-Based Estimation of Stochastic Kronecker Graph Parameters
• GraphBLAST: A High-Performance Linear Algebra-based Graph Framework on the GPU
• Coin-flipping, Ball-dropping, and Grass-hopping for generating random graphs from matrices of edge probabilities
• Community detection in complex networks: from statistical foundations to data science applications
• On matchings in stochastic Kronecker graphs

This page was built for publication: An in-depth analysis of stochastic Kronecker graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5395712)