Dissimilarity-based hypothesis testing for community detection in heterogeneous networks

Abstract

Read online

Identifying communities within networks is a crucial and challenging problem with practical implications across various scientific fields. Existing methods often overlook the heterogeneous distribution of nodal degrees or require prior knowledge of the number of communities. To overcome these limitations, we propose an efficient hypothesis test for community detection by quantifying dissimilarities between graphs. Our approach centers around examining the dissimilarity between a given random graph and a null hypothesis which assumes a degree-corrected Erdös–Rényi type. To compare the dissimilarity, we introduce a measure that takes into account the distributions of vertex distances, clustering coefficients, and alpha-centrality. This measure is then utilized in our hypothesis test. To simultaneously uncover the number of communities and their corresponding structures, we develop a two-stage bipartitioning algorithm. This algorithm integrates seamlessly with our hypothesis test and enables the exploration of community organization within the network. Through experiments conducted on both synthetic and real networks, we demonstrate that our method outperforms state-of-the-art approaches in community detection.

Keywords

• community detection
• stochastic block model
• hypothesis test
• graph dissimilarity
• divergence