Detecting overlapping communities in networks using the maximal sub-graph and the clustering coefficient

• Introduce the maximal sub-graphs and the clustering coefficient of two neighboring communities.
• Propose ACC algorithm and an extended modularity.
• Find overlapping vertices.
• Give excellent experimental results.

In this paper, we present an alternate algorithm for detecting overlapping community structures in the complex network. Two concepts named the maximal sub-graph and the clustering coefficient between two neighboring communities are introduced. First, all the maximal sub-graphs are extracted from the original networks and then merge them by considering the clustering coefficient of two neighboring maximal sub-graphs. And a new extended modularity is proposed to quantify this algorithm. The other advantage of this algorithm is that the overlapping vertex can be detected. The effectiveness of our algorithm is tested on some real networks. Finally, we compare the computational complexity of this algorithm with selected close related algorithms. The results show that this algorithm gives satisfactory results.