A Memetic Algorithm for the Minimum Conductance Graph Partitioning Problem

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.

• Publication year

  2017

• Venue

  arXiv.org

• Publication date

  2017-04-10

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1704.02854
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Small Worlds

  2019cited by this paper
• The Computational Complexity of NK Fitness Functions

  2017cited by this paper
• Graph Clustering

  2017cited by this paper
• Gray Box Optimization for Mk Landscapes (NK Landscapes and MAX-kSAT)

  2016cited by this paper
• Partition Crossover for Pseudo-Boolean Optimization

  2015cited by this paper
• Mk Landscapes, NK Landscapes, MAX-kSAT: A Proof that the Only Challenging Problems are Deceptive

  2015cited by this paper
• Tunnelling Crossover Networks

  2015cited by this paper
• Algorithms and tools for protein-protein interaction networks clustering, with a special focus on population-based stochastic methods

  2014cited by this paper
• {SNAP Datasets}: {Stanford} Large Network Dataset Collection

  2014cited by this paper
• An Evolutionary Multiobjective Approach for Community Discovery in Dynamic Networks

  2014cited by this paper
• Complex Network Clustering by Multiobjective Discrete Particle Swarm Optimization Based on Decomposition

  2014cited by this paper
• Tunably Rugged Landscapes With Known Maximum and Minimum

  2014cited by this paper
• Multi-level learning based memetic algorithm for community detection

  2014cited by this paper
• Efficient identification of improving moves in a ball for pseudo-boolean problems

  2014cited by this paper
• Partitioning networks into cliques : a randomized heuristic approach

  2014cited by this paper
• Second order partial derivatives for NK-landscapes

  2013cited by this paper
• Greedy or Not? Best Improving versus First Improving Stochastic Local Search for MAXSAT

  2013cited by this paper
• Constant time steepest descent local search with lookahead for NK-landscapes and MAX-kSAT

  2012cited by this paper
• Community detection in Social Media

  2012cited by this paper
• A Multiobjective Genetic Algorithm to Find Communities in Complex Networks

  2012cited by this paper
• DATA ANALYSIS IN PUBLIC SOCIAL NETWORKS

  2012cited by this paper
• A Multilevel Memetic Approach for Improving Graph k-Partitions

  2011cited by this paper
• A Multi-Facet Survey on Memetic Computation

  2011cited by this paper
• A combinatorial model and algorithm for globally searching community structure in complex networks

  2010cited by this paper
• Managing and Mining Graph Data

  2010cited by this paper
• Empirical comparison of algorithms for network community detection

  2010cited by this paper
• Hierarchy in the growing scale-free network with local rules

  2009cited by this paper
• COLA: Optimizing Stream Processing Applications via Graph Partitioning

  2009cited by this paper
• Community detection in graphs

  2009cited by this paper
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters

  2008cited by this paper
• Fast unfolding of communities in large networks

  2008cited by this paper
• A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning

  2008cited by this paper
• Detectives: detecting coalition hit inflation attacks in advertising networks streams

  2007cited by this paper
• Stochastic Local Search

  2007cited by this paper
• Energy Models for Graph Clustering

  2007cited by this paper
• Graph mining: Laws, generators, and algorithms

  2006cited by this paper
• Finding community structure in networks using the eigenvectors of matrices.

  2006cited by this paper
• MA mid PM: memetic algorithms with population management

  2006cited by this paper
• Chinese Whispers - an Efficient Graph Clustering Algorithm and its Application to Natural Language Processing Problems

  2006cited by this paper
• Stochastic Local Clustering for Massive Graphs

  2005cited by this paper
• A tutorial for competent memetic algorithms: model, taxonomy, and design issues

  2005cited by this paper
• On the NP-Completeness of Some Graph Cluster Measures

  2005cited by this paper
• The Database of Interacting Proteins: 2004 update

  2004cited by this paper
• Advanced Fitness Landscape Analysis and the Performance of Memetic Algorithms

  2004cited by this paper
• Stochastic Local Search: Foundations & Applications

  2004cited by this paper
• Hierarchical Organization of Complex Networks

  2004cited by this paper
• Experiments on Graph Clustering Algorithms

  2003cited by this paper
• The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations

  2003cited by this paper
• DIP, the Database of Interacting Proteins: a research tool for studying cellular networks of protein interactions

  2002cited by this paper
• Language as an evolving word web

  2001cited by this paper
• Community structure in social and biological networks

  2001cited by this paper
• DIP: The Database of Interacting Proteins: 2001 update

  2001cited by this paper
• Efficient identification of Web communities

  2000cited by this paper
• DIP: the Database of Interacting Proteins

  2000cited by this paper
• Emergence of Scaling in Random Networks

  1999cited by this paper
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper
• Advances in Knowledge Discovery and Data Mining: 9th Pacific-Asia Conference, PAKDD 2005, Hanoi, Vietnam, May 18-20, 2005, Proceedings

  1997cited by this paper
• The Stanford GraphBase - a platform for combinatorial computing

  1993cited by this paper
• Uniform Crossover in Genetic Algorithms

  1989cited by this paper
• The basic algorithm for pseudo-Boolean programming revisited

  1988cited by this paper
• An Information Flow Model for Conflict and Fission in Small Groups

  1977cited by this paper

• Metaheuristic approaches for ratio cut and normalized cut graph partitioning

  2022cites this paper
• Prior Signal Editing for Graph Filter Posterior Fairness Constraints

  2021cites this paper
• A hybrid evolutionary algorithm for finding low conductance of large graphs

  2020influential citation
• Unsupervised evaluation of multiple node ranks by reconstructing local structures

  2020cites this paper
• Applying Fairness Constraints on Graph Node Ranks Under Personalization Bias

  2020cites this paper
• Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem

  2019influential citation
• Memetic Algorithms for Business Analytics and Data Science: A Brief Survey

  2019cites this paper
• LinkAUC: Unsupervised Evaluation of Multiple Network Node Ranks Using Link Prediction

  2019cites this paper
• Hybrid Bridge-Based Memetic Algorithms for Finding Bottlenecks in Complex Networks

  2018influential citation