Title: Detecting Statistically Significant Communities,
Abstract: Community detection is a key data analysis problem across different fields.
During the past decades, numerous algorithms have been proposed to address this
issue. However, most work on community detection does not address the issue of
statistical significance. Although some research efforts have been made towards
mining statistically significant communities, deriving an analytical solution
of p-value for one community under the configuration model is still a
challenging mission that remains unsolved. To partially fulfill this void, we
present a tight upper bound on the p-value of a single community under the
configuration model, which can be used for quantifying the statistical
significance of each community analytically. Meanwhile, we present a local
search method to detect statistically significant communities in an iterative
manner. Experimental results demonstrate that our method is comparable with the
competing methods on detecting statistically significant communities.