.png){kind=icon}
.png){kind=icon}
Return
Fast Markov Clustering Algorithm Based on Belief Dynamics
.png){kind=icon}
PRE
AI
DOI：10.1109/TCYB.2022.3141598.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Heuristic algorithms
Clustering algorithms
Convergence
Markov processes
Broadcasting
Computational complexity
Trajectory
Belief dynamics
complex networks
convergence
large-scale networks
Markov clustering algorithm
Journal
IF:
10.5
Papers:
1.1W
Citations:
5.0W