A link clustering based memetic algorithm for overlapping community detection

摘要

Community detection has attracted plenty of attention in the field of complex networks recently, since communities often play important roles in networked systems. Overlapping communities are one of the characteristics of social networks, describing the phenomenon that a node may belong to more than one social group. Thus, it is necessary to find overlapping community structures for realistic social network analyses. In this paper, we propose a link clustering based memetic algorithm for detecting overlapping communities. Since links usually represent the unique relationships among nodes, link clustering can find link groups with the same characteristics. As a result, nodes are naturally partitioned into multiple communities. The proposed algorithm optimizes a modularity density function which is able to identify densely connected groups of links on the weighted line graph modeling the network, and then maps link communities to node communities based on a novel genotype representation. In our method, the number of communities can be automatically determined. Experimental results on general and sparse networks show that our method can successfully detect overlapping community structures and almost all the overlapping nodes. (C) 2018 Elsevier B.V. All rights reserved.