An In-Depth Analysis of Stochastic Kronecker Graphs

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.

References in corpus (5)

• Power-law distributions in empirical data
• New Model of Internet Topology Using k-shell Decomposition
• Kronecker Graphs: An Approach to Modeling Networks
• k-core (bootstrap) percolation on complex networks: Critical phenomena and nonlocal effects
• Multiplicative Attribute Graph Model of Real-World Networks

Cited by in corpus (14)

• Scale-free networks are rare
• A Scalable Generative Graph Model with Community Structure
• Network Sampling: From Static to Streaming Graphs
• BioCode: A Data-Driven Procedure to Learn the Growth of Biological Networks
• Learning multifractal structure in large networks
• Graph Distance from the Topological View of Non-backtracking Cycles
• The Infinity Mirror Test for Graph Models
• Exact rank-reduction of network models
• Properties of stochastic Kronecker graphs
• Block-Approximated Exponential Random Graphs
• Modeling Graphs Using a Mixture of Kronecker Models
• Large Graph Models: A Review
• On the diameter of Kronecker graphs
• Optimizing Communication by Compression for Multi-GPU Scalable Breadth-First Searches