Detecting highly overlapping community structure by model-based maximal clique expansion

International audienceCommunity detection, also known as graph clustering, has been extensively studied in the literature. The goal of community detection is to partition vertices in a complex graph into densely-connected components so-called communities. Discovering the hidden community structure is a fundamental problem in network and graph analysis. Several approaches have been proposed to solve this challenging problem. Among them, detecting overlapping communities in a network is an usual way towards understanding the features of networks. In this paper, we propose an efficient overlapping community detection method using a seed set expansion approach. In particular, we make an original use of a particular concept of graph theory, called chordal graph, to discover densely connected structures in social interactions based on maximal cliques. Indeed, a chordal graph possesses a number of interesting and useful properties that can help us to efficiently recover all maximal cliques of a given graph. Then, we develop new seeding strategies based on different fitness functions for discovering meaningful communities. Experimental results demonstrate the effectiveness and the efficiency of our overlapping community model in a variety of real graph