Preserving coupled nodes in population-based CNP solvers by clustering-elitism search

Mingyang Feng; Qi Zhao; Liang Zhang; Shan He; Yuhui Shi

doi:10.1109/SSCI50451.2021.9660065

Preserving coupled nodes in population-based CNP solvers by clustering-elitism search

Mingyang Feng, Qi Zhao, Liang Zhang, Shan He, Yuhui Shi

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Critical node problems (CNP) are important in many fields such as network immunization and viral marketing. Although population-based metaheuristics have been successful on CNP, they fail to efficiently identify and preserve the coupled critical nodes. To narrow this gap, this paper proposes a new search operator called clustering-elitism search for population-based CNP solvers. The proposed operator mainly consists of two parts: clustering and generating. The clustering part divides populations into several clusters to differentiate solutions with various structures, while the generating parts produces new solutions by investigating the consensus and difference between the elite solutions with different structures. Experimental results on synthesis and real networks demonstrate the better performance of the proposed operator with respect to existing solvers.

Original language	English
Title of host publication	2021 IEEE Symposium Series on Computational Intelligence (SSCI)
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Number of pages	7
ISBN (Electronic)	9781728190488
ISBN (Print)	9781728190495 (PoD)
DOIs	https://doi.org/10.1109/SSCI50451.2021.9660065
Publication status	Published - 24 Jan 2022
Event	IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2021) - Orlando, United States Duration: 5 Dec 2021 → 7 Dec 2021

Publication series

Name	IEEE Symposium Series on Computational Intelligence
Publisher	IEEE
ISSN (Electronic)	2770-0097

Conference

Conference	IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2021)
Abbreviated title	IEEE SSCI 2021
Country/Territory	United States
City	Orlando
Period	5/12/21 → 7/12/21

Bibliographical note

Funding Information:
This work is partially supported by the Shenzhen Fundamental Research Program under the Grant No. JCYJ20200109141235597, National Science Foundation of China under grant No. 61761136008, Shenzhen Peacock Plan under Grant No. KQTD2016112514355531, and Program for Guangdong Introducing Innovative and Entrepreneurial Teams under grant No. 2017ZT07X386. (Yuhui Shi is the Corresponding Author.)

Publisher Copyright:
© 2021 IEEE.

Keywords

Critical node problem
Evolutionary algorithm
Population-based search

ASJC Scopus subject areas

Artificial Intelligence
Computer Science Applications
Decision Sciences (miscellaneous)
Safety, Risk, Reliability and Quality
Control and Optimization

Access to Document

10.1109/SSCI50451.2021.9660065

Cite this

Feng, M., Zhao, Q., Zhang, L., He, S., & Shi, Y. (2022). Preserving coupled nodes in population-based CNP solvers by clustering-elitism search. In 2021 IEEE Symposium Series on Computational Intelligence (SSCI) Article 9660065 (IEEE Symposium Series on Computational Intelligence). Institute of Electrical and Electronics Engineers (IEEE). https://doi.org/10.1109/SSCI50451.2021.9660065

@inproceedings{681aa156122b42b190ce37319a93d5a2,

title = "Preserving coupled nodes in population-based CNP solvers by clustering-elitism search",

abstract = "Critical node problems (CNP) are important in many fields such as network immunization and viral marketing. Although population-based metaheuristics have been successful on CNP, they fail to efficiently identify and preserve the coupled critical nodes. To narrow this gap, this paper proposes a new search operator called clustering-elitism search for population-based CNP solvers. The proposed operator mainly consists of two parts: clustering and generating. The clustering part divides populations into several clusters to differentiate solutions with various structures, while the generating parts produces new solutions by investigating the consensus and difference between the elite solutions with different structures. Experimental results on synthesis and real networks demonstrate the better performance of the proposed operator with respect to existing solvers.",

keywords = "Critical node problem, Evolutionary algorithm, Population-based search",

author = "Mingyang Feng and Qi Zhao and Liang Zhang and Shan He and Yuhui Shi",

note = "Funding Information: This work is partially supported by the Shenzhen Fundamental Research Program under the Grant No. JCYJ20200109141235597, National Science Foundation of China under grant No. 61761136008, Shenzhen Peacock Plan under Grant No. KQTD2016112514355531, and Program for Guangdong Introducing Innovative and Entrepreneurial Teams under grant No. 2017ZT07X386. (Yuhui Shi is the Corresponding Author.) Publisher Copyright: {\textcopyright} 2021 IEEE.; IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2021), IEEE SSCI 2021 ; Conference date: 05-12-2021 Through 07-12-2021",

year = "2022",

month = jan,

day = "24",

doi = "10.1109/SSCI50451.2021.9660065",

language = "English",

isbn = "9781728190495 (PoD)",

series = "IEEE Symposium Series on Computational Intelligence",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

booktitle = "2021 IEEE Symposium Series on Computational Intelligence (SSCI)",

}

Feng, M, Zhao, Q, Zhang, L, He, S & Shi, Y 2022, Preserving coupled nodes in population-based CNP solvers by clustering-elitism search. in 2021 IEEE Symposium Series on Computational Intelligence (SSCI)., 9660065, IEEE Symposium Series on Computational Intelligence, Institute of Electrical and Electronics Engineers (IEEE), IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2021), Orlando, Florida, United States, 5/12/21. https://doi.org/10.1109/SSCI50451.2021.9660065

Preserving coupled nodes in population-based CNP solvers by clustering-elitism search. / Feng, Mingyang; Zhao, Qi; Zhang, Liang et al.
2021 IEEE Symposium Series on Computational Intelligence (SSCI). Institute of Electrical and Electronics Engineers (IEEE), 2022. 9660065 (IEEE Symposium Series on Computational Intelligence).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Preserving coupled nodes in population-based CNP solvers by clustering-elitism search

AU - Feng, Mingyang

AU - Zhao, Qi

AU - Zhang, Liang

AU - He, Shan

AU - Shi, Yuhui

N1 - Funding Information: This work is partially supported by the Shenzhen Fundamental Research Program under the Grant No. JCYJ20200109141235597, National Science Foundation of China under grant No. 61761136008, Shenzhen Peacock Plan under Grant No. KQTD2016112514355531, and Program for Guangdong Introducing Innovative and Entrepreneurial Teams under grant No. 2017ZT07X386. (Yuhui Shi is the Corresponding Author.) Publisher Copyright: © 2021 IEEE.

PY - 2022/1/24

Y1 - 2022/1/24

N2 - Critical node problems (CNP) are important in many fields such as network immunization and viral marketing. Although population-based metaheuristics have been successful on CNP, they fail to efficiently identify and preserve the coupled critical nodes. To narrow this gap, this paper proposes a new search operator called clustering-elitism search for population-based CNP solvers. The proposed operator mainly consists of two parts: clustering and generating. The clustering part divides populations into several clusters to differentiate solutions with various structures, while the generating parts produces new solutions by investigating the consensus and difference between the elite solutions with different structures. Experimental results on synthesis and real networks demonstrate the better performance of the proposed operator with respect to existing solvers.

AB - Critical node problems (CNP) are important in many fields such as network immunization and viral marketing. Although population-based metaheuristics have been successful on CNP, they fail to efficiently identify and preserve the coupled critical nodes. To narrow this gap, this paper proposes a new search operator called clustering-elitism search for population-based CNP solvers. The proposed operator mainly consists of two parts: clustering and generating. The clustering part divides populations into several clusters to differentiate solutions with various structures, while the generating parts produces new solutions by investigating the consensus and difference between the elite solutions with different structures. Experimental results on synthesis and real networks demonstrate the better performance of the proposed operator with respect to existing solvers.

KW - Critical node problem

KW - Evolutionary algorithm

KW - Population-based search

UR - http://www.scopus.com/inward/record.url?scp=85125764664&partnerID=8YFLogxK

U2 - 10.1109/SSCI50451.2021.9660065

DO - 10.1109/SSCI50451.2021.9660065

M3 - Conference contribution

AN - SCOPUS:85125764664

SN - 9781728190495 (PoD)

T3 - IEEE Symposium Series on Computational Intelligence

BT - 2021 IEEE Symposium Series on Computational Intelligence (SSCI)

PB - Institute of Electrical and Electronics Engineers (IEEE)

T2 - IEEE Symposium Series on Computational Intelligence (IEEE SSCI 2021)

Y2 - 5 December 2021 through 7 December 2021

ER -

Preserving coupled nodes in population-based CNP solvers by clustering-elitism search

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this