Abstract
In this thesis, we propose a correlation-based algorithm for detecting overlapping communities in networks (graphs) based on a general probabilistic framework introduced in [20].For a set of nodes in a graph, we first define the self correlation of the set for measuring its importance, and then we define the correlation intensity of the set for describing how strongly each node in the set is correlated to the other nodes in the set. The key idea in our correlation-based algorithm is to locally maximize the self correlations of sets of nodes in a greedy manner while maintaining the correlation intensities of those sets to be above a given threshold. Given the generalized node degrees of a graph, the threshold can be chosen so that every set of nodes generated by our algorithm possesses certain properties. Through extensive computer simulations of random graphs with built-in overlapping community structure, we show that the performance of our algorithm is quite good. Furthermore, we apply our algorithm to the real-world network “Karate club” and show that the overlapping communities detected by our algorithm are very close to the known communities in this graph.