Sampling from Large Graphs

[wagpa]

https://cs.stanford.edu/people/jure/pubs/sampling-kdd06.pdf

[wagpa]

Notes

• "Sampling strategies based on edge selection do not perform well; simple uniform random node selection performs surprisingly well. Overall, best performing methods are the ones based on random-walks and “forest fire”; they match very accurately both static as well as evolutionary graph patterns, with sample sizes down to about 15% of the original graph"
• Scale-down goal, and Back-in-time goal
• "One could also use ideas from graph clustering and graph partitioning. These algorithms are usually computationally intensive and do not scale well to very large graphs. Graph sampling becomes important with massive graphs, where real-world algorithms become too expensive and one has to reside to sampling. Thus simplicity of sampling is essential."