Skip to main content

Hybrid Bridge-Based Memetic Algorithms for Finding Bottlenecks in Complex Networks

Chalupa, David; Hawick, Ken; Walker, James

Authors

David Chalupa

Ken Hawick

James Walker



Abstract

We propose a memetic approach to find bottlenecks in complex networks based on searching for a graph partitioning with minimum conductance. Finding the optimum of this problem, also known in statistical mechanics as the Cheeger constant, is one of the most interesting NP-hard network optimisation problems. The existence of low conductance minima indicates bottlenecks in complex networks. However, the problem has not yet been explored in depth in the context of applied discrete optimisation and evolu- tionary approaches to solve it. In this paper, the use of a memetic frame- work is explored to solve the minimum condutance problem. The approach combines a hybrid method of initial population generation based on bridge identification and local optima sampling with a steady-state evolutionary process with two local search subroutines. These two local search subrou- tines have complementary qualities. Efficiency of three crossover operators is explored, namely one-point crossover, uniform crossover, and our own par- tition crossover. Experimental results are presented for both artificial and real-world complex networks. Results for Barab ́asi-Albert model of scale-free networks are presented, as well as results for samples of social networks and protein-protein interaction networks. These indicate that both well-informed initial population generation and the use of a crossover seem beneficial in solving the problem in large-scale.

Journal Article Type Article
Publication Date 2018-12
Electronic ISSN 2214-5796
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 14
Pages 68-80
Series Title Big Data Research
APA6 Citation Chalupa, D., Hawick, K., & Walker, J. (2018). Hybrid Bridge-Based Memetic Algorithms for Finding Bottlenecks in Complex Networks. Big Data Research, 14, 68-80. https://doi.org/10.1016/j.bdr.2018.04.001
DOI https://doi.org/10.1016/j.bdr.2018.04.001
Keywords Memetic algorithms; Bottlenecks; Complex networks; Minimum conductance problem; Sparsest cut; Cheeger constant
Publisher URL https://www.journals.elsevier.com/big-data-research
Copyright Statement © 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/

Files

Article (1.2 Mb)
PDF

Copyright Statement
© 2019. This manuscript version is made available under the CC-BY-NC-ND 4.0 license http://creativecommons.org/licenses/by-nc-nd/4.0/







Downloadable Citations