Whale optimization algorithm based on Markov chain is used for overlapping community discovery

Area of Science:

• Complex Networks
• Computational Intelligence
• Data Mining

Background:

• Traditional Whale Optimization Algorithm (WOA) suffers from low search efficiency and reduced diversity in later stages.
• Overlapping community detection is crucial for understanding complex network structures.
• Existing methods often struggle with redundant nodes, impacting partitioning accuracy.

Purpose of the Study:

• To propose a Markov Chain-based Whale Optimization Algorithm (MKWOA) for enhanced overlapping community detection.
• To improve the search efficiency and diversity of the WOA.
• To increase the accuracy of overlapping community partitioning.

Main Methods:

• Incorporation of a Markov chain-based state decision mechanism to utilize prior knowledge.
• Implementation of a differential bidirectional crossover strategy to enhance late-stage diversity.
• Application of a topology-potential-based overlapping node optimization strategy to eliminate redundant nodes.

Main Results:

• MKWOA demonstrated superior performance compared to six mainstream algorithms on LFR synthetic and seven real-world networks.
• Achieved competitive Normalized Mutual Information (NMI) values on the LFR benchmark, especially under high mixed parameters and ambiguous structures.
• Obtained the highest Extended Modularity (EQ) values on five real-world networks, significantly outperforming others on datasets like Polbooks.

Conclusions:

• The proposed MKWOA effectively enhances performance and robustness in overlapping community detection.
• The integration of Markov chains, differential crossover, and node optimization strategies addresses key limitations of traditional WOA.
• MKWOA shows significant potential for analyzing complex network structures with overlapping communities.