Topology-Guided Sampling for Fast and Accurate Community Detection
  Community detection is a well-studied problem with applications in domains
ranging from computer networking to bioinformatics. While there are many
algorithms that perform community detection, the more accurate and
statistically robust algorithms tend to be slow and hard to parallelize. One
way to speed up such algorithms is through data reduction. However, this
approach has not been thoroughly studied, and the quality of results obtained
with this approach varies with the graph it is applied to. In this manuscript,
we present an approach based on topology-guided sampling for accelerating
stochastic block partitioning - a community detection algorithm that works well
on graphs with complex and heterogeneous community structure. We also introduce
a degree-based thresholding scheme that improves the efficacy of our approach
at the expense of speedup. Finally, we perform a series of experiments on
synthetically generated graphs to determine how various graph parameters affect
the quality of results and speedup obtained with our approach, and we validate
our approach on real-world data. Our results show that our approach can lead to
a speedup of up to 15X over stochastic block partitioning without sampling
while maintaining result quality and can even lead to improvements of over 150%
in result quality in terms of F1 score on certain kinds of graphs.
