  The minimum conductance problem is an NP-hard graph partitioning problem.
Apart from the search for bottlenecks in complex networks, the problem is very
closely related to the popular area of network community detection. In this
paper, we tackle the minimum conductance problem as a pseudo-Boolean
optimisation problem and propose a memetic algorithm to solve it. An efficient
local search strategy is established. Our memetic algorithm starts by using
this local search strategy with different random strings to sample a set of
diverse initial solutions. This is followed by an evolutionary phase based on a
steady-state framework and two intensification subroutines. We compare the
algorithm to a wide range of multi-start local search approaches and classical
genetic algorithms with different crossover operators. The experimental results
are presented for a diverse set of real-world networks. These results indicate
that the memetic algorithm outperforms the alternative stochastic approaches.
