An ensemble based on a bi-objective evolutionary spectral algorithm for graph clustering

Abstract

Graph clustering is a challenging pattern recognition problem whose goal is to identify vertex partitions with high intra-group connectivity. This paper investigates a bi-objective problem that maximizes the number of intra-cluster edges of a graph and minimizes the expected number of inter-cluster edges in a random graph with the same degree sequence as the original one. The difference between the two investigated objectives is the definition of the well-known measure of graph clustering quality: the modularity. We introduce a spectral decomposition hybridized with an evolutionary heuristic, called MOSpecG, to approach this bi-objective problem and an ensemble strategy to consolidate the solutions found by MOSpecG into a final robust partition. The results of computational experiments with real and artificial LFR networks demonstrated a significant improvement in the results and performance of the introduced method in regard to another bi-objective algorithm found in the literature. The crossover operator based on the geometric interpretation of the modularity maximization problem to match the communities of a pair of individuals was of utmost importance for the good performance of MOSpecG. Hybridizing spectral graph theory and intelligent systems allowed us to define significantly high-quality community structures.

arXiv commentPreprint accepted for publication in Expert Systems with Applications

References in corpus (19)

• Community structure in social and biological networks
• Finding and evaluating community structure in networks
• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Maps of random walks on complex networks reveal community structure
• Near linear time algorithm to detect community structures in large-scale networks
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Statistical Mechanics of Community Detection
• Finding statistically significant communities in networks
• Consensus clustering in complex networks
• An information-theoretic framework for resolving community structure in complex networks
• Spectral redemption: clustering sparse networks
• Tolerating the Community Detection Resolution Limit with Edge Weighting
• Detecting criminal organizations in mobile phone networks
• Enhancing community detection using a network weighting strategy
• Multiway spectral community detection in networks
• Identification of network modules by optimization of ratio association
• Improving the performance of algorithms to find communities in networks