Technical Report CSI-0076

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

D. Chalupa and K. A. Hawick and J. A. Walker

Archived: 2017

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. However, the problem has not yet been explored in depth in the context of applied discrete optimisation and evolutionary approaches to solve it. In this paper, we explore the use of a memetic framework 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. Efficiency of three crossover operators is explored. Experimental results are presented mainly 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.

Keywords: memetic algorithms, bottlenecks, complex networks, minimum conductance problem, sparsest cut, Cheeger constant

Full Document Text: Not yet available.

Citation Information: BiBTeX database for CSI Notes.

BiBTeX reference:

@TechReport{CSI-0076,
        Title = {Hybrid Bridge-Based Memetic Algorithms for Finding Bottlenecks in Complex Networks},
        Author = {D. Chalupa and K. A. Hawick and J. A. Walker},
        Institution = {Computer Science, University of Hull},
        Year = {2017},
        Address = {Cottingham Road, Hull, HU6 7RX},
        Month = {August},
        Number = {CSI-0076},
        Keywords = {memetic algorithms, bottlenecks, complex networks, minimum conductance problem, sparsest cut, Cheeger constant},
        Owner = {kahawick},
        Timestamp = {2017.09.01}
}