Developing an efficient clique-based algorithm for community detection in large graphs

Abstract

Many computer science problems are structured as a network. Mobile, e-mail, social networks (MySpace, Friendster, Facebook, etc.), collaboration networks, and Protein-Protein Interaction (PPI), Gene Regulatory Networks (GRN) and Metabolic Networks (MN) in bioinformatics, are among several applications. Discovering communities in Networks is a recent and critical task in order to understand and model network structures. Several methods exist for community detection, such as modularity, clique, and random walk methods. These methods are somewhat limited because of the time needed to detect communities and their modularity. In this work, a Clique-based Community Detection Algorithm (CCDA) is proposed to overcome time and modularity limitations. The clique method is suitable since it arises in many real-world problems, as in bioinformatics, computational chemistry, and social networks. In definition, clique is a group of individuals who interact with one another and share similar interests. Based on this definition, if one vertex of a clique is assigned to a specific community, all other vertices in this clique often belong to the same community. CCDA develops a simple and fast method to detect maximum clique for specific vertex. In addition, testing is done for the closest neighbor node instead of testing all nodes in the graph. Since neighbor nodes are also sorted in descending order, it contributes to save more execution time. Furthermore, each node will be visited exactly once. To test the performance of CCDA, it is compared with previously proposed community detection algorithms (Louvain, and MACH with DDA-M2), using various datasets: Amazon (262111 nodes/1234877 vertices), DBLP (317080 nodes/1049866 vertices), and LiveJournal (4847571 nodes, 68993773 vertices). Results have proven the efficiency of the proposed method in terms of time performance and modularity.