Multi-objective memetic algorithm for core-periphery structure detection in complex network

Li，Guo1; Zhu，Zexuan1,2; Ma，Lijia1; Ma，Xiaoliang1

2021

10.1007/s12293-021-00342-9

Memetic Computing   影响因子和分区

1865-9284

1865-9292

Core-periphery structure detection (CPSD) in complex networks is essential to reveal functional nodes in the complicated systems, e.g., influential nodes in a social network and central cells in a biological network. Some progress has been made in solving the CPSD problem with heuristic algorithms. However, CPSD is naturally an NP-hard optimization problem and the core-periphery structures (CPSs) in real networks usually are not clearly distinguishable. The majority of the existing CPSD methods are single-objective methods relying on some assumptions, preference, and/or prior knowledge. They can provide only one trade-off solution that is inevitably biased and lacks of flexibility in terms of resolution. To address this issue, this paper formulates the CPSD problem as a multi-objective optimization problem (MOP), i.e., minimizing the core-node size and maximizing the core-node capacity of the CPSs, simultaneously. Solving the MOP can provide more accurate CPSs and allow one to explore the network structure at different preferred resolutions. A multi-objective memetic algorithm (called MOMA-PCLS) is accordingly proposed to solve the formulated problem. A new plateau-climbing local search (PCLS) method incorporating the information of the heavy-tailed distribution of the node capacity is introduced to fine-tune the individual solutions in MOMA-PCLS. By combining the evolutionary operations and PCLS, MOMA-PCLS manages to improve the search efficiency significantly. Experimental results on both synthetic and real-world data show the superiority of MOMA-PCLS to other state-of-the-art algorithms in detecting CPSs of complex networks.

Complex networks Core-periphery structure Memetic algorithm Multi-objective optimization

SCI ; EI

英语

通讯

National Natural Science Foundation of China[61871272,61803269] ; Guangdong Provincial Key Laboratory["2020B121201001","2020A1515010790"] ; Shenzhen Fundamental Research Program["JCYJ20190808173617147","JCYJ20190808174801673"] ; BGI-Research Shenzhen Open Funds[BGIRSZ 20200002]

Computer Science ; Operations Research & Management Science

Computer Science, Artificial Intelligence ; Operations Research & Management Science

WOS:000678494300002

SPRINGER HEIDELBERG

20213110708778

Economic and social effects ; Heuristic algorithms ; Multiobjective optimization ; NP-hard

Computer Systems and Equipment:722 ; Computer Programming:723.1 ; Optimization Techniques:921.5 ; Social Sciences:971

2-s2.0-85111534603

Scopus

1.College of Computer Science and Software Engineering,Shenzhen University,Shenzhen,518060,China
2.Guangdong Provincial Key Laboratory of Brain-Inspired Intelligent Computation,Southern University of Science and Technology,Shenzhen,518055,China

Li，Guo,Zhu，Zexuan,Ma，Lijia,et al. Multi-objective memetic algorithm for core-periphery structure detection in complex network[J]. Memetic Computing,2021,13:285-306.

Li，Guo,Zhu，Zexuan,Ma，Lijia,&Ma，Xiaoliang.(2021).Multi-objective memetic algorithm for core-periphery structure detection in complex network.Memetic Computing,13,285-306.

Li，Guo,et al."Multi-objective memetic algorithm for core-periphery structure detection in complex network".Memetic Computing 13(2021):285-306.