作者
Piet Van Mieghem, Dragan Stevanović, Fernando Kuipers, Cong Li, Ruud Van De Bovenkamp, Daijie Liu, Huijuan Wang
发表日期
2011/7
期刊
Physical Review E—Statistical, Nonlinear, and Soft Matter Physics
卷号
84
期号
1
页码范围
016101
出版商
American Physical Society
简介
The decrease of the spectral radius, an important characterizer of network dynamics, by removing links is investigated. The minimization of the spectral radius by removing links is shown to be an NP-complete problem, which suggests considering heuristic strategies. Several greedy strategies are compared, and several bounds on the decrease of the spectral radius are derived. The strategy that removes that link with largest product of the components of the eigenvector belonging to the largest adjacency eigenvalue is shown to be superior to other strategies in most cases. Furthermore, a scaling law where the decrease in spectral radius is inversely proportional to the number of nodes in the graph is deduced. Another sublinear scaling law of the decrease in spectral radius versus the number of removed links is conjectured.
学术搜索中的文章
P Van Mieghem, D Stevanović, F Kuipers, C Li… - Physical Review E—Statistical, Nonlinear, and Soft …, 2011