Dual modularity optimization for detecting overlapping communities in bipartite networks

作者：Souam Fatiha^*; Aitelhadj Ali; Baba Ali Riadh

来源：Knowledge and Information Systems, 2014, 40(2): 455-488.

DOI：10.1007/s10115-013-0644-8

• Overlapping community detection
• Data mining
• Edge partitioning
• Global and local modularity optimization
• Evolutionary algorithm
• Bipartite graph

Many algorithms have been designed to discover community structure in networks. These algorithms are mostly dedicated to detecting disjoint communities. Very few of them are intended to discover overlapping communities, particularly the bipartite networks have hardly been explored for the detection of such communities. In this paper, we describe a new approach which consists in forming overlapping mixed communities in a bipartite network based on dual optimization of modularity. To this end, we propose two algorithms. The first one is an evolutionary algorithm dedicated for global optimization of the Newman's modularity on the line graph. This algorithm has been tested on well-known real benchmark networks and compared with several other existing methods of community detection in networks. The second one is an algorithm that locally optimizes the graph Mancoridis modularity, and we have adapted to a bipartite graph. Specifically, this second algorithm is applied to the decomposition of vertices, resulting from the evolutionary process, and also characterizes the overlapping communities taking into account their semantic aspect. Our approach requires a priori no knowledge on the number of communities searched in the network. We show its interest on two datasets, namely, a group of synthetic networks and real-world network whose structure is also difficult to understand.

• 出版日期2014-8