An Extremal Optimization Approach to the Pairwise Connectivity Critical Node Detection Problem (2022)

Soft Computing Models in Industrial and Environmental Applications

Authors

Noémi Gaskó, Tamás Képes, M. Suciu, R. Lung

Abstract

The critical node detection is a computational challenging problem with several applications in biology, sociology, etc. Minimizing the pairwise connectivity after removing k critical nodes is one of the most studied problem. In this paper we approach this problem by using a standard Extremal Optimization algorithm, and another variant with incorporated network shifting mechanism. Network centrality measures are used to speed up the search, the variants are analyzed on synthetic and real-world problems. Numerical results indicate the potential of the proposed approach.

Citation

@Inproceedings{Gaskó2022AnEO,
 author = {Noémi Gaskó and Tamás Képes and M. Suciu and R. Lung},
 booktitle = {Soft Computing Models in Industrial and Environmental Applications},
 title = {An Extremal Optimization Approach to the Pairwise Connectivity Critical Node Detection Problem},
 year = {2022}
}