Detecting Overlapping Community In Social Network

Overlapping community is a widespread feature in the complex system. Because overlapping community can intuitively and vividly reveals the internal organizational structure and relationship between the clubs, the overlapping community detection is important to analyze the network topology and understand the network function. What’s more, the overlapping community detection can also predicate the dynamic behavior of the network. Up to now, most of the overlapping community partition algorithms are complex and difficult to realize overlapping community detection. The main contributions of this article are as follows:1. Propose an improved clique percolation method to accelerate overlapping community detection by optimizing the clique search process. Based on complete graph in the network, put forward a new method that digs clique from big to small iteratively. Accelerate the process of overlapping community detection by reducing the nodes scope. Apply the improved clique percolation method to simulated and empirical networks, which quickly realize the overlapping community detection.2. Based on the community measure quality, propose a new linear time complex method to detect overlapping community. Firstly, update the modularity matrix and merge the community that divides the network into non-overlapping community quickly by using the heap data structure. Secondly, dig the overlapping nodes between the communities accurately by analyzing every edge in the network edge. Finally, apply the algorithm to simulation network in order to test the accuracy and analyze that new algorithm is nearly linear time complexity.3. Select the classic social network data sets to verify the accuracy and efficiency of the overlapping community detection algorithm. Based on the community partition measure, apply the method to karate club network and dolphin network to confirm the accuracy of the algorithm, whose community structure have been known. Apply the method to Les Miserables role network and scientists cooperation network to reveal the internal topology characteristic of network, whose network structure are unknown. The overlapping communities reflect the importance of the main characters in the novel and the cooperation mode between scientists. By analyzing the time cost of the above four network, the new method can quickly realizes the overlapping community detection.