Fast Markov Clustering Algorithm Based on Belief Dynamics.

Area of Science:

• Network analysis
• Data mining
• Computational complexity

Background:

• Graph clustering is crucial for understanding complex networks.
• Existing methods face challenges in accuracy and efficiency.
• Real-world networks require robust clustering techniques.

Purpose of the Study:

• To propose a novel Markov clustering algorithm (BMCL) for accurate and efficient graph clustering.
• To introduce a new belief dynamics model for analyzing complex networks.
• To guarantee ideal cluster configurations through belief convergence.

Main Methods:

• Developed a new belief dynamics model focusing on multicontent and random information broadcasting.
• Proved the convergence of nodes' normalized beliefs in complex networks.
• Introduced the BMCL algorithm, mapping nodes to clusters based on belief convergence trajectory.

Main Results:

• The BMCL algorithm guarantees ideal cluster configurations.
• Achieved high efficiency with a convergence speed of O(TN) in sparse networks.
• Experimental evaluations demonstrated the proposed method's performance.

Conclusions:

• The BMCL algorithm offers an accurate and efficient solution for graph clustering.
• The belief dynamics model provides a theoretical foundation for network clustering.
• BMCL is a promising approach for analyzing complex network structures.