Skip to main content

Optimization of Graph Clustering Inspired by Dynamic Belief Systems

Publication ,  Journal Article
Li, H; Cao, H; Feng, Y; Li, X; Pei, J
Published in: IEEE Transactions on Knowledge and Data Engineering
January 1, 2023

Graph clustering is essential to understand the nature and behavior of real world such as social network, technical network and transportation network. Different from the existing studies, we propose a new Markov clustering method inspired by belief dynamical system which can be used in general for optimization of different quality measures. By a rigorous theoretical proof, it has been shown that the quality function's global maximum is a dynamical system's asymptotically stable fixed point. Under specified conditions, the trajectory of the dynamical converges to the cluster labels of corresponding nodes. Particularly, a general formulation can unite well-known methodologies and the quality functions that correspond to them. The algorithm is fast and its computational complexity is nearly linear with the scale of sparse networks. Finally, we thoroughly evaluate our methodology on a variety of synthetic and real-world networks with various network properties, particularly on the dynamical networks. The results demonstrate that when compared to the current state-of-the-art algorithms, our method performs better on these networks.

Duke Scholars

Published In

IEEE Transactions on Knowledge and Data Engineering

DOI

EISSN

1558-2191

ISSN

1041-4347

Publication Date

January 1, 2023

Related Subject Headings

  • Information Systems
  • 46 Information and computing sciences
  • 08 Information and Computing Sciences
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Li, H., Cao, H., Feng, Y., Li, X., & Pei, J. (2023). Optimization of Graph Clustering Inspired by Dynamic Belief Systems. IEEE Transactions on Knowledge and Data Engineering. https://doi.org/10.1109/TKDE.2023.3274547
Li, H., H. Cao, Y. Feng, X. Li, and J. Pei. “Optimization of Graph Clustering Inspired by Dynamic Belief Systems.” IEEE Transactions on Knowledge and Data Engineering, January 1, 2023. https://doi.org/10.1109/TKDE.2023.3274547.
Li H, Cao H, Feng Y, Li X, Pei J. Optimization of Graph Clustering Inspired by Dynamic Belief Systems. IEEE Transactions on Knowledge and Data Engineering. 2023 Jan 1;
Li, H., et al. “Optimization of Graph Clustering Inspired by Dynamic Belief Systems.” IEEE Transactions on Knowledge and Data Engineering, Jan. 2023. Scopus, doi:10.1109/TKDE.2023.3274547.
Li H, Cao H, Feng Y, Li X, Pei J. Optimization of Graph Clustering Inspired by Dynamic Belief Systems. IEEE Transactions on Knowledge and Data Engineering. 2023 Jan 1;

Published In

IEEE Transactions on Knowledge and Data Engineering

DOI

EISSN

1558-2191

ISSN

1041-4347

Publication Date

January 1, 2023

Related Subject Headings

  • Information Systems
  • 46 Information and computing sciences
  • 08 Information and Computing Sciences