An In-Depth Analysis of Stochastic Kronecker Graphs

Details An In-Depth Analysis of Stochastic Kronecker Graphs An In-Depth Analysis of Stochastic Kronecker Graphs

2011-02-24

arxiv.org/abs/1102.5046v2

Computer Science

Social and Information Networks

Scientific paper

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. These results have been communicated to the Graph500 steering committee, and they are currently using our theorems to set the benchmark parameters. Our noisy version of SKG is likely to become the Graph500 standard for next year's benchmark.

Affiliated with

Also associated with

No associations

Rating

An In-Depth Analysis of Stochastic Kronecker Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An In-Depth Analysis of Stochastic Kronecker Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An In-Depth Analysis of Stochastic Kronecker Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-87122