A local-to-global scheme-based multi-objective evolutionary algorithm for overlapping community detection on large-scale

  • PDF / 2,193,671 Bytes
  • 15 Pages / 595.276 x 790.866 pts Page_size
  • 20 Downloads / 206 Views

DOWNLOAD

REPORT


(0123456789().,-volV)(0123456789().,-volV)

ORIGINAL ARTICLE

A local-to-global scheme-based multi-objective evolutionary algorithm for overlapping community detection on large-scale complex networks Haiping Ma1 • Haipeng Yang2 • Kefei Zhou2 • Lei Zhang2 • Xingyi Zhang2 Received: 18 January 2020 / Accepted: 19 August 2020 Ó Springer-Verlag London Ltd., part of Springer Nature 2020

Abstract Recently, multi-objective evolutionary algorithms (MOEAs) have been shown promising performance for detecting overlapping community structure in complex networks. However, it is still challenging to design MOEAs for overlapping community detection on large-scale complex networks due to the curse of dimensionality. Along this avenue, this paper proposes a local-to-global scheme-based MOEA named LG-MOEA for overlapping community detection on large-scale complex networks, which mainly consists of two stages: a local community structure detection stage and a global community structure determination stage. To be specific, in the local community structure detection stage, the key nodes that are central to community and essential to the connectedness of community are firstly identified. Then for each key node, an MOEA with the proposed community boundary control strategy is suggested to detect a set of local overlapping communities through local expansion around the key node. In the global community structure determination stage, a single objective evolutionary algorithm is adopted to search for a suitable local overlapping community for each key node and combine them as one global community partition of the whole network. The proposed LG-MOEA is compared with several competitive overlapping community detection algorithms on both real-world small-scale and large-scale networks, and the experimental results show its superiority for overlapping community detection in terms of the generalized normalized mutual information gNMI and the extended modularity Qov , especially has competitive superiority for large-scale complex networks. Keywords Multi-objective optimization  Evolutionary algorithm  Overlapping community detection  Large-scale complex network

& Lei Zhang [email protected] Haiping Ma [email protected]

2

Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, School of Computer Science and Technology, Anhui University, Hefei 230039, China

Haipeng Yang [email protected] Kefei Zhou [email protected] Xingyi Zhang [email protected] 1

Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education, Institutes of Physical Science and Information Technology, Anhui University, Hefei 230039, China

123

Neural Computing and Applications

1 Introduction Generally speaking, community detection is to divide a network into several groups of nodes based on the topology structure of the network, such that nodes in the same group are densely connected and the nodes in different groups are sparsely connected [1]. It has been considered as a very important tool to reveal the f