We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Critical node identification for complex network based on a novel minimum connected dominating set.
- Authors
Yu, Fahong; Xia, Xiaoyun; Li, Wenping; Tao, Jiang; Ma, Longhua; Cai, Zhao-quan
- Abstract
Identifying critical nodes in complex networks aims to fragment a graph $$G = (V, E)$$ by removing a set of vertices R with cardinality $$\left| R \right| \le $$ k, such that the residual graph has minimum pairwise connectivity. Existing optimization algorithms are incapable of finding a good set R in complex networks. By investigating the role of nodes, a minimum dominating set approach is considered in controlling a network. This paper presents an algorithmic procedure to compute the critical nodes using a novel minimum connected dominating set, in which the critical nodes are identified based on the number of close subsequences. Through experimental verification on some randomly generated networks and comparing with the similar algorithms, the results showed that the proposed algorithm has high capability of identifying the critical nodes and low time complexity.
- Subjects
GRAPH connectivity; GEOMETRIC vertices; PARALLEL algorithms; SET theory; AUTOMATIC differentiation
- Publication
Soft Computing - A Fusion of Foundations, Methodologies & Applications, 2017, Vol 21, Issue 19, p5621
- ISSN
1432-7643
- Publication type
Article
- DOI
10.1007/s00500-016-2303-y