Improved Overlapping Community Detection in Networks based on Maximal Cliques Enumeration

摘要

Social Network Analysis has received great interest in recent years in several areas, including communities detection. Many studies have been carried out in this sense. The Bron Kerbosch Algorithm (BK) is one of the most widely known and most efficient algorithm to detect overlapping communities based on the maximal clique notion. It is a linear and fast algorithm, but its major disadvantage lies in “Lost nodes”, which are isolated nodes not belonging to any communities. In addition, this method represents a difficulty in extracting cliques. This difficulty is due to the strict definition of the clique. Since, to get better detection, this definition requires finding nodes which are all linked in the network.In this paper, we introduce DOCNA a new algorithm for detecting overlapping communities in networks based on maximal cliques. DOCNA adopts an improved version of BK Algorithm. In fact, we add an assignment phase which allows each “Lost node” to be a member of one or more detected communities. Moreover, our algorithm uses a special Click_Graph construction process to detect communities.The experimental results, on synthetic and real Networks with different sizes and overlapping rates, illustrate the effectiveness of our approach in detecting dynamic overlapping community structures.