2.5K-Graphs: From Sampling to Generation
Understanding network structure and having access to realistic graphs plays a central role in computer and social networks research. In this paper, the authors propose a complete, practical methodology for generating graphs that resemble a real graph of interest. The metrics of the original topology they target to match are the Joint Degree Distribution (JDD) and the degree-dependent average clustering coefficient. They start by developing efficient estimators for these two metrics based on a node sample collected via either independence sampling or random walks. Then, they process the output of the estimators to ensure that the target metrics are realizable.