Fast Markov Clustering Algorithm Based on Belief Dynamics

Graph clustering is one of the most significant, challenging, and valuable topic in the analysis of real complex networks. To detect the cluster configuration accurately and efficiently, we propose a new Markov clustering algorithm based on the limit state of the belief dynamics model. First, we pre...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on cybernetics 2023-06, Vol.53 (6), p.3716-3725
Main Authors: Li, Huijia, Xu, Wenzhe, Qiu, Chenyang, Pei, Jian
Format: Article
Language:English
Subjects:
Algorithms
Belief dynamics
Broadcasting
Clustering
Clustering algorithms
complex networks
Computational complexity
Configurations
Convergence
Dynamics
Heuristic algorithms
large-scale networks
Limit states
Markov clustering algorithm
Markov processes
Networks
Trajectory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Graph clustering is one of the most significant, challenging, and valuable topic in the analysis of real complex networks. To detect the cluster configuration accurately and efficiently, we propose a new Markov clustering algorithm based on the limit state of the belief dynamics model. First, we present a new belief dynamics model, which focuses beliefs of multicontent and randomly broadcasting information. A strict proof is provided for the convergence of nodes' normalized beliefs in complex networks. Second, we introduce a new Markov clustering algorithm (denoted as BMCL) by employing a belief dynamics model, which guarantees the ideal cluster configuration. Following the trajectory of the belief convergence, each node is mapped into the corresponding cluster repeatedly. The proposed BMCL algorithm is highly efficient: the convergence speed of the proposed algorithm researches O(TN) in sparse networks. Last, we implement several experiments to evaluate the performance of the proposed methods.
ISSN:2168-2267
2168-2275
DOI:10.1109/TCYB.2022.3141598