PROJECT TITLE :

Detecting Statistically Significant Communities

ABSTRACT:

The identification of communities is a fundamental issue in the data analysis of many different fields. Over the course of the last few decades, a great many algorithmic solutions to this problem have been proposed. The majority of research on community detection, on the other hand, does not address the problem of statistical significance. Although there have been some research efforts made towards mining statistically significant communities, the task of deriving an analytical solution of p-value for one community under the configuration model is still difficult and has not been solved. The configuration model is a random graph model that is utilized extensively in the field of community detection. In this model, the degree of each node is maintained within the generated random networks. We present a stringent upper bound on the p-value of a single community under the configuration model. This p-value can be used for quantifying the statistical significance of each community in an analytical manner. This is an attempt to partially fill the void that has been created. In the meantime, we will present a local search method that uses an iterative approach to identify communities that are statistically significant. The results of our experiments indicate that our approach is on par with those of our competitors' approaches when it comes to identifying statistically significant communities.