A link clustering based overlapping community detection algorithm

There is a surge of community detection study on complex network analysis in recent years, since communities often play important roles in network systems. However, many real networks have more complex overlapping community structures. This paper proposes a novel algorithm to discover overlapping communities. Different from conventional algorithms based on node clustering, the proposed algorithm is based on link clustering. Since links usually represent unique relations among nodes, the link clustering will discover groups of links that have the same characteristics. Thus nodes naturally belong to multiple communities. The algorithm applies genetic operation to cluster on links. An effective encoding schema is designed and the number of communities can be automatically determined. Experiments on both artificial networks and real networks validate the effectiveness and efficiency of the proposed algorithm. Crown Copyright (C) 2013 Published by Elsevier B.V. All rights reserved.