Mining Statistically Significant Communities From Weighted Networks

As one of the most important issues in data mining and network science, the community detection problem has been extensively investigated during the past decades. Despite of the success achieved by existing methods, how to directly access the statistical significance of an individual community in a weighted network remains unsolved. To address this issue, we present a new method to calculate the analytical p-value of an individual community in weighted networks. The proposed analytical p-value is able to assess the statistical significance that one target community appears in a random weighted graph in a straightforward manner. To verify the effectiveness of the proposed p-value in community evaluation, it is utilized as the objective function in a local search procedure to derive a new community detection algorithm. Experimental results show that the new algorithm is able to achieve comparable performance to those state-of-the-art algorithms for identifying communities from weighted networks.

Automated summary

As one of the most important topics in data mining and network science, community detection problem has been extensively studied. However, determining the statistical significance of an individual community in a weighted network remains unsolved. In this study, a new method is proposed to calculate the analytical p-value of an individual community in weighted networks, and it is utilized as the objective function in a local search procedure to derive a new community detection algorithm. Experimental results demonstrate that the new algorithm achieves comparable performance to state-of-the-art algorithms for identifying communities in weighted networks.