<p>Community detection in complex networks is fundamental across social, biological, and technological domains. While traditional single-objective methods like Louvain and Leiden are computationally efficient, they suffer from resolution bias and structural degeneracy. Multi-objective evolutionary algorithms (MOEAs) address these limitations by simultaneously optimizing conflicting structural criteria, however, their high computational costs have historically limited their application to small networks. We present HP-MOCD, a High-Performance Evolutionary Multiobjective Community Detection Algorithm built on Non-dominated Sorting Genetic Algorithm II (NSGA-II), which overcomes these barriers through topology-aware genetic operators, full parallelization, and bit-level optimizations–achieving theoretical <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$O(G \cdot N_p |V|)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo>·</mo> <msub> <mi>N</mi> <mi>p</mi> </msub> <mo stretchy="false">|</mo> <mi>V</mi> <mo stretchy="false">|</mo> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> complexity. We conduct experiments on both synthetic and real-world networks. Results demonstrate strong scalability, with HP-MOCD processing networks of over 1,000,000 nodes while maintaining high quality across varying noise levels. It outperforms other MOEAs by more than 531 times in runtime on synthetic datasets, achieving runtimes as low as 57 s for graphs with 40,000 nodes on moderately powered hardware. Across 14 real-world networks, HP-MOCD was the only MOEA capable of processing the six largest datasets within reasonable time, with results competitive with single-objective approaches. Unlike single-solution methods, HP-MOCD produces a Pareto Front, enabling individual-specific trade-offs and providing decision-makers with a spectrum of high-quality community structures. It introduces the first open-source <Emphasis FontCategory="NonProportional">Python</Emphasis> MOEA library compatible with <Emphasis FontCategory="NonProportional">networkx</Emphasis> and <Emphasis FontCategory="NonProportional">igraph</Emphasis> for large-scale community detection.</p>

A high-performance evolutionary multiobjective community detection algorithm

期刊论文
出版模式：

开放获取
发表日期：

2025年11月18日

查看全文

Guilherme O. Santos,
Lucas S. Vieira,
Giulio Rossetti,
Carlos H. G. Ferreira,
Gladston J. P. Moreira

摘要

Community detection in complex networks is fundamental across social, biological, and technological domains. While traditional single-objective methods like Louvain and Leiden are computationally efficient, they suffer from resolution bias and structural degeneracy. Multi-objective evolutionary algorithms (MOEAs) address these limitations by simultaneously optimizing conflicting structural criteria, however, their high computational costs have historically limited their application to small networks. We present HP-MOCD, a High-Performance Evolutionary Multiobjective Community Detection Algorithm built on Non-dominated Sorting Genetic Algorithm II (NSGA-II), which overcomes these barriers through topology-aware genetic operators, full parallelization, and bit-level optimizations–achieving theoretical $O(G \cdot N_p |V|)$ $O (G \cdot N_{p} | V |)$ complexity. We conduct experiments on both synthetic and real-world networks. Results demonstrate strong scalability, with HP-MOCD processing networks of over 1,000,000 nodes while maintaining high quality across varying noise levels. It outperforms other MOEAs by more than 531 times in runtime on synthetic datasets, achieving runtimes as low as 57 s for graphs with 40,000 nodes on moderately powered hardware. Across 14 real-world networks, HP-MOCD was the only MOEA capable of processing the six largest datasets within reasonable time, with results competitive with single-objective approaches. Unlike single-solution methods, HP-MOCD produces a Pareto Front, enabling individual-specific trade-offs and providing decision-makers with a spectrum of high-quality community structures. It introduces the first open-source Python MOEA library compatible with networkx and igraph for large-scale community detection.