2.5K-graphs: From sampling to generation
Authors:
- 1 April 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1968-1976
Abstract
Understanding network structure and having access to realistic graphs plays a central role in computer and social networks research. In this paper, we propose a complete, practical methodology for generating graphs that resemble a real graph of interest. The metrics of the original topology we target to match are the joint degree distribution (JDD) and the degree-dependent average clustering coefficient (c̅(k)). We start by developing efficient estimators for these two metrics based on a node sample collected via either independence sampling or random walks. Then, we process the output of the estimators to ensure that the target metrics are realizable. Finally, we propose an efficient algorithm for generating topologies that have the exact target JDD and a c̅(k) close to the target. Extensive simulations using real-life graphs show that the graphs generated by our methodology are similar to the original graph with respect to, not only the two target metrics, but also a wide range of other topological metrics. Furthermore, our generator is order of magnitudes faster than state-of-the-art techniques.Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Sharing graphs using differentially private graph models2011
- Social Structure of Facebook NetworksSSRN Electronic Journal, 2011
- Estimating and sampling graphs with multidimensional random walks2010
- Measurement-calibrated graph models for social network experiments2010
- On the evolution of user interaction in Facebook2009
- Random Graphs with ClusteringPhysical Review Letters, 2009
- Tuning clustering in random networks with arbitrary degree distributionsPhysical Review E, 2005
- Collective dynamics of ‘small-world’ networksNature, 1998
- A critical point for random graphs with a given degree sequenceRandom Structures & Algorithms, 1995
- Multivariate Density Estimation1992