SamBaS: Sampling-Based Stochastic Block Partitioning
- 25 January 2024
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Network Science and Engineering
- Vol. 11 (3) , 3053-3065
Abstract
Community detection is a well-studied problem with applications in domains ranging from networking to bioinformatics. Due to the rapid growth in the volume of real-world data, there is growing interest in accelerating contemporary community detection algorithms. However, the more accurate and statistically robust methods tend to be hard to parallelize. One such method is stochastic block partitioning (SBP) – a community detection algorithm that works well on graphs with complex and heterogeneous community structure. In this paper, we present a sam pling- ba sed S BP ( SamBaS ) for accelerating SBP on sparse graphs. We characterize how various graph parameters affect the speedup and result quality of community detection with SamBaS and quantify the trade-offs therein. To evaluate SamBas on real-world web graphs without known ground-truth communities, we introduce p artition q uality s core (PQS), an evaluation metric that outperforms modularity in terms of correlation with F1 score. Overall, SamBaS achieves speedups of up to 10× while maintaining result quality (and even improving result quality by over 150% on certain graphs, relative to F1 score).Keywords
All Related Versions
Funding Information
- Under Secretary of Defense for Research and Engineering (FA8702-15-D-0001)
- NSF (I/UCRC CNS-1822080)
- Center for Space, High-performance, and Resilient Computing
This publication has 48 references indexed in Scilit:
- Descriptive vs. Inferential Community Detection in Networks2023
- Towards scaling community detection on distributed-memory heterogeneous systemsParallel Computing, 2022
- Compressing Networks with Super NodesScientific Reports, 2018
- Parallel heuristics for scalable community detectionParallel Computing, 2015
- Defining and evaluating network communities based on ground-truthKnowledge and Information Systems, 2013
- Community detection in graphsPhysics Reports, 2010
- Assessing the relevance of node features for network structureProceedings of the National Academy of Sciences, 2009
- Resolution limit in community detectionProceedings of the National Academy of Sciences, 2007
- Detection of functional modules from protein interaction networksProteins: Structure, Function, and Bioinformatics, 2003
- Growth dynamics of the World-Wide WebNature, 1999