The Similarity between Stochastic Kronecker and Chung-Lu Graph Models

Details The Similarity between Stochastic Kronecker and Chung-Lu Graph Models The Similarity between Stochastic Kronecker and Chung-Lu Graph Models

2011-10-21

arxiv.org/abs/1110.4925v2

Computer Science

Social and Information Networks

Scientific paper

The analysis of massive graphs is now becoming a very important part of science and industrial research. This has led to the construction of a large variety of graph models, each with their own advantages. The Stochastic Kronecker Graph (SKG) model has been chosen by the Graph500 steering committee to create supercomputer benchmarks for graph algorithms. The major reasons for this are its easy parallelization and ability to mirror real data. Although SKG is easy to implement, there is little understanding of the properties and behavior of this model. We show that the parallel variant of the edge-configuration model given by Chung and Lu (referred to as CL) is notably similar to the SKG model. The graph properties of an SKG are extremely close to those of a CL graph generated with the appropriate parameters. Indeed, the final probability matrix used by SKG is almost identical to that of a CL model. This implies that the graph distribution represented by SKG is almost the same as that given by a CL model. We also show that when it comes to fitting real data, CL performs as well as SKG based on empirical studies of graph properties. CL has the added benefit of a trivially simple fitting procedure and exactly matching the degree distribution. Our results suggest that users of the SKG model should consider the CL model because of its similar properties, simpler structure, and ability to fit a wider range of degree distributions. At the very least, CL is a good control model to compare against.

Affiliated with

Also associated with

No associations

Rating

The Similarity between Stochastic Kronecker and Chung-Lu Graph Models 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 The Similarity between Stochastic Kronecker and Chung-Lu Graph Models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Similarity between Stochastic Kronecker and Chung-Lu Graph Models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-564181