I'm working with a very large undirected graph (a social network from a telecomunication company).

I'm applying a clustering algorithm on this graph to find it’s most relevant communities. The problem is that the algorithm is very slow and I need to test it with a smaller graph to tune some parameters.

Recently, I came with the idea of getting a sample from this large graph. This sample has to be representative of the original graph.

Is there someone who knows the best algorithm to get that sample? And what should be the minimum size of the sample (is it 15%?)?

I already read some articles about sampling on large directed graphs (Estimating and Sampling Graphs with Multidimensional Random Walks, and Sampling from Large Graphs), and there doesn't seem to be any article about undirected graphs.

If you need any more information, please tell me.

Thank you very much,


  • 1
    $\begingroup$ Any undirected graph can be viewed as a directed graph (with edges going both ways), so results for the latter should apply for the former. Generally speaking, when sampling anything, the size of the sample depends on the accuracy, but generally speaking is very small, certainly a sub-constant fraction. So 15% sounds bogus. $\endgroup$ – Yuval Filmus May 12 '14 at 17:46
  • 1
    $\begingroup$ You should be careful in how you sample the graph - perhaps a completely random sample wouldn't yield meaningful result with respect to communities. $\endgroup$ – Yuval Filmus May 12 '14 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.