-
Controlling a complex network to achieve a certain desired objective is an important task for various interacting systems. In many practical situations, it is expensive and unrealistic to control all nodes especially in a large-scale complex network. In order to reduce control cost, one turns to control a small part of nodes in the network, which is called pinning control. This research direction has been widely concerned and much representative progress has been achieved so far. However, to achieve an optimal performance, two key questions about the node-selection scheme remain open. One is how many nodes need controlling and the other is which nodes the controllers should be applied to. It has been revealed in our recent work that the effectiveness of node-selection scheme can be evaluated by the smallest eigenvalue
$ {\rm{\lambda }}_{1} $ of the grounded Laplacian matrix obtained by deleting the rows and columns corresponding to the pinned nodes from the Laplacian matrix of the network. As a further study of our previous work, we study node selection algorithm for optimizing pinning control in depth, based on the proposed index$ {\rm{\lambda }}_{1} $ and its spectral properties. As is well known, it is an NP-hard problem to obtain the maximum of$ {\rm{\lambda }}_{1} $ by numerical calculations when the number of pinned nodes is given. To solve this challenge problem, in this paper a filtering algorithm is proposed to find most important nodes, which results in an optimal$ {\rm{\lambda }}_{1} $ when the number of pinned nodes is given. The method can be applied to any type of undirected networks. Furthermore, in this paper we propose the concept of node-set importance in complex networks from the perspective of network control, which is different from the existing definitions about node importance of complex networks: The importance of a node set and the selected nodes in this paper depends on the number of pinned nodes; if the number of pinned nodes is different, the selected nodes will be different. The concept of node-set importance reflects the effect of nodes’ combination in a network. It is expected that the obtained results are helpful in guiding the optimal control problems in practical networks.-
Keywords:
- complex dynamical networks /
- pinning control /
- optimization algorithm /
- node-set importance
[1] Liu H, Xu X, Lu J A, Chen G, Zeng Z 2021 IEEE Trans. Syst. Man Cybern. Syst. 51 786
Google Scholar
[2] 王凯莉, 邬春学, 艾均, 苏湛 2019 物理学报 68 196402
Google Scholar
Wang K L, Wu C X, Ai J, Su S 2019 Acta Phys. Sin. 68 196402
Google Scholar
[3] 韩伟涛, 伊鹏, 马海龙, 张鹏, 田乐 2019 物理学报 68 186401
Google Scholar
Han W T, Yi P, Ma H L, Zhang P, Tian L 2019 Acta Phys. Sin. 68 186401
Google Scholar
[4] Li M, Wang B H 2014 Chin. Phys. B 23 076402
Google Scholar
[5] Wang X F, Chen G R 2002 Phys. A 310 521
Google Scholar
[6] Li X, Wang X F, Chen G R 2004 IEEE Trans. Circuits Syst. Regul. Pap. 51 2074
Google Scholar
[7] Zhou J, Lu J A, Lu J H 2008 Automatica 44 996
Google Scholar
[8] Yu W W, Chen G R, Lu J H 2009 Automatica 45 429
Google Scholar
[9] Francesco S, Mario D B, Franco G, Chen G R 2007 Phys. Rev. E 75 046103
Google Scholar
[10] Wang L, Dai H P, Dong H, Cao Y Y, Sun Y X 2008 Eur. Phys. J. B 61 335
Google Scholar
[11] Wang X F, Su H S 2014 Annu Rev Control 38 103
Google Scholar
[12] Song Q, Cao J D 2009 IEEE Trans. Circuits Syst. Regul. Pap. 57 672
[13] Ali G, Soleyman A 2016 Nonlinear Dyn. 83 1003
Google Scholar
[14] Rong Z H, Li X, Lu W L 2009Proc. IEEE Int. Symp. Circuits Syst.Taipei, China, May 17–24, 2009 p1689
[15] Jia Z, Li X 2010 29th Chinese Control Conference Beijing, China, July 29–31, 2010 p4656
[16] Wang X Y, Liu X W 2018 Nonlinear Dyn. 92 13
Google Scholar
[17] Gong K, Kang L 2018 J. Syst. Sci. Inf. 6 366
[18] Jin Y, Bao Q, Zhang Z 2019 IEEE Int. Conference on Data Mining, Beijing, China, November 8–11, 2019 p339
[19] Amani A M, Jalili M, Yu X, Stone L 2017 IEEE Trans. Circuits Syst. Express Briefs 64 685
Google Scholar
[20] 陆君安, 刘慧, 陈娟 2016 复杂动态网络的同步（第一版）（北京: 高等教育出版社）第49页
Lu J A, Liu H, Chen J 2016 Synchronization in Complex Dynamical Networks (Vol. 1) (Beijing: Higher Education Press) p49 (in Chinese)
[21] Pirani M, Sundaram S 2015 IEEE Trans. Autom. Control 61 509
[22] Kitsak M, Gallos L, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888
Google Scholar
[23] Physicians network dataset, KONECT http://konect.unikoblenz.de/networks/ [2017.9.9]
[24] Danielle S B, Mason A P, Nicholas F W, Scott T G, Jean M C, Peter J M 2013 Chaos 23 013142
Google Scholar
[25] 徐明明, 陆君安, 周进 2016 物理学报 65 028902
Google Scholar
Xu M M, Lu J A, Zhou J 2016 Acta Phys. Sin. 65 028902
Google Scholar
-
图 1 生成的BA网络. 不同颜色代表节点的度的大小, 红色表示度大的节点, 蓝色表示度小的节点
Figure 1. A generated BA network. Different colors represent different node-degrees in the network; nodes in red have relative large degrees, and nodes in blue have small degrees.
图 2 在4种不同算法下Dolphin网络的选点情况 (a)度算法选点情况; (b) BC算法选点情况; (c) ESI算法选点情况; (d)本文算法选点情况
Figure 2. Visualization of nodes selections on the Dolphin network underfour strategies (
$ l=5 $ ): (a) Using the degree-based pinning scheme; (b) using the BC-based pinning scheme; (c) using the ESI-based pinning scheme; (d) using our proposed algorithm.
图 3 在4种不同算法下Email网络的选点情况 (a) 度算法选点情况; (b) BC算法选点情况; (c) ESI算法选点情况; (d) 本文算法选点情况
Figure 3. Visualization of nodes selections on the Email network under four strategies: (a) Using the degree-based pinning scheme; (b) using the BC-based pinning scheme; (c) using the ESI-based pinning scheme; (d) using our proposed algorithm.
图 4 两个网络A与B结构不同, 但删去节点4后网络相同 (a) 网络A及其Laplacian矩阵; (b) 网络A删除节点4及其Laplacian矩阵; (c) 网络B及其Laplacian矩阵; (d)网络B删除节点4及其Laplacian矩阵
Figure 4. The structures of networks A and B are different, but the remaining structures are the same after deleting node 4. (a) network A and its Laplacian matrix; (b) network A deleting node 4 and its Laplacian matrix; (c) network B and its Laplacian matrix; (d) network B deleting node 4 and its Laplacian matrix.
图 5 链状网络节点数N = 5及其拉普拉斯矩阵
Figure 5. Chain graph with N = 5 and its Laplacian matrix.
图 6
${\lambda _1}({L_{N - 2}})$ 与左节点位置(两节点对称选取)的关系图, 这里N = 82Figure 6. The relationship of
${\lambda _1}({L_{N - 2}})$ and the left node’s position, where N = 82 and the two nodes are selected symmetrically.
图 7 在正方形网格中选两个最重要的节点, 见图中红色的点 (a) 24 × 24的正方形网格; (b) 31 × 31的正方形网格; (c) 40 × 40的正方形网格; (d) 45 × 45的正方形网格
Figure 7. Pinning two nodes in a square lattice. The optimal options are shown by red nodes: (a) The square with 24 × 24 nodes; (b) the square with 31 × 31 nodes; (c) the square with 40 × 40 nodes; (d) the square with 45 × 45 nodes.
图 8 正方形网络选4个最重要的节点, 见图中红色的点 (a) 24 × 24正方形网格; (b) 27 × 27正方形网格; (c) 32 × 32正方形网格
Figure 8. Pinning four nodes in a square lattice. The optimal options are shown by red nodes: (a) The square with 24 × 24 nodes; (b) the square with 27 × 27 nodes; (c) the square with 32 × 32 nodes.
表 1 节点度排序及节点编号(BA网络, N = 1000, q = 5)
Table 1. Degree ordering and node numbering in a BA network with N = 1000 and q = 5.
节点的度 128 122 103 98 87 86 75 63 60 58 53 51 51 49 47 43 42 节点编号 2 11 3 18 1 9 4 8 14 31 21 17 10 63 34 20 13 
DownLoad: CSV
表 2 通过步骤2筛选后的剩余节点数n
Table 2. Number of remaining nodes n after Step 2 in Algorithm 1.
网络参数 l = 2 l = 3 l = 4 l = 5 l = 6 NW: N = 1000, P = 0.05 3.9 11.9 30.3 51.0 89.1 NW: N = 1000, P = 0.025 11.3 27.9 53.4 132.9 216.1 BA: N = 1000, q = 10 5.7 13.2 18.6 22.1 38.4 BA: N = 1000, q = 8 6.7 14.2 22.5 51.2 176.3 BA: N = 1000, q = 5 7.1 15.3 67.1 177.5 1000 BA: N = 1000, q = 3 10.2 55.7 1000.0 1000.0 1000.0
DownLoad: CSV
表 3 通过步骤3筛选后剩余节点的组合数量R
Table 3. Number of combinations R of remaining nodes after Step 3 in Algorithm 1.
网络参数 l = 2 l = 3 l = 4 l = 5 l = 6 NW: N = 1000, P = 0.05 5.1 33.3 216.1 1136.5 4245.8 NW: N = 1000, P = 0.025 18.2 215.6 1009.5 1.1 × 104 4.7 × 104 BA: N = 1000, q = 10 3.3 11.5 34.3 163.1 1801.6 BA: N = 1000, q = 8 6.3 16.3 83.8 233.5 2583.7 BA: N = 1000, q = 5 21.6 69.5 306.5 2203.8 2.4 × 104 BA: N = 1000, q = 3 25.3 307.3 4376.2 2.2 × 105 4.5 × 106
DownLoad: CSV
表 4 不同算法在Dolphin网络中的选点及
${\lambda _1}({ L_{N - l}})$ 对比Table 4. Node-selections and the corresponding
${\lambda _1}({ L_{N - l}})$ under different algorithms on the dolphin network.受控
节点数度算法 BC算法 K-shell算法 ESI算法 本文算法 l = 2 (15, 46)
${\lambda _1} = 0.1001$(37, 2)
${\lambda _1} = 0.1376$(19, 30)
${\lambda _1} = 0.0828$(15, 38)
${\lambda _1} = 0.0995$(15, 18)
${\lambda _1} = 0.2549$l = 3 (15, 46, 38)
${\lambda _1} = 0.1053$(37, 2, 41)
${\lambda _1} = 0.2344$(19, 30, 46)
${\lambda _1} = 0.0935$(15, 38, 46)
${\lambda _1} = 0.1053$(15, 14, 46)
${\lambda _1} = 0.3664$l = 4 (15, 46, 38, 52)
${\lambda _1} = 0.1064$(37, 2, 41, 38)
${\lambda _1} = 0.2511$(19, 30, 46, 52)
${\lambda _1} = 0.0950$(15, 38, 46, 51)
${\lambda _1} = 0.1069$(62, 14, 46, 2)
${\lambda _1} = 0.4662$l = 5 (15, 46, 38, 52, 34)
${\lambda _1} = 0.1072$(37, 2, 41, 38, 8)
${\lambda _1} = 0.2710$(19, 30, 46, 52, 22)
${\lambda _1} = 0.0960$(15, 38, 46, 51, 39)
${\lambda _1} = 0.1078$(15, 38, 52, 18, 14)
${\lambda _1} = 0.5399$
DownLoad: CSV
表 5 不同算法在Email网络中的选点及
${\lambda _1}({ L_{N - l}})$ 对比Table 5. Node-selections and the corresponding
${\lambda _1}({ L_{N - l}})$ under different algorithms on the email network.受控
节点数度算法 BC算法 K-shell算法 ESI算法 本文算法 l = 2 (105, 333)
${\lambda _1} = 0.0881$(333, 105)
${\lambda _1} = 0.0881$(299, 389)
${\lambda _1} = 0.0383$(105, 42)
${\lambda _1} = 0.0879$(105, 23)
${\lambda _1} = 0.0894$l = 3 (105, 333, 16)
${\lambda _1} = 0.1169$(333, 105, 23)
${\lambda _1} = 0.1243$(299, 389, 424)
${\lambda _1} = 0.0392$(105, 42, 333)
${\lambda _1} = 0.1202$(105, 333, 23)
${\lambda _1} = 0.1243$l = 4 (105, 333, 16, 23)${\lambda _1} = 0.1518$ (333, 105, 23, 578)
${\lambda _1} = 0.1490$(299, 389, 424, 552)
${\lambda _1} = 0.0494$(105, 42, 333, 16)
${\lambda _1} = 0.1481$(105, 333, 23, 42)
${\lambda _1} = 0.1535$l = 5 (105, 333, 16, 23, 42)
${\lambda _1} = 0.1801$(333, 105, 23, 578, 76)
${\lambda _1} = 0.1774$(299, 389, 424, 552, 571)
${\lambda _1} = 0.0520$(105, 42, 333, 16, 76)
${\lambda _1} = 0.1770$(105, 333, 23, 42, 41)
${\lambda _1} = 0.1843$
DownLoad: CSV
-
[1] Liu H, Xu X, Lu J A, Chen G, Zeng Z 2021 IEEE Trans. Syst. Man Cybern. Syst. 51 786
Google Scholar
[2] 王凯莉, 邬春学, 艾均, 苏湛 2019 物理学报 68 196402
Google Scholar
Wang K L, Wu C X, Ai J, Su S 2019 Acta Phys. Sin. 68 196402
Google Scholar
[3] 韩伟涛, 伊鹏, 马海龙, 张鹏, 田乐 2019 物理学报 68 186401
Google Scholar
Han W T, Yi P, Ma H L, Zhang P, Tian L 2019 Acta Phys. Sin. 68 186401
Google Scholar
[4] Li M, Wang B H 2014 Chin. Phys. B 23 076402
Google Scholar
[5] Wang X F, Chen G R 2002 Phys. A 310 521
Google Scholar
[6] Li X, Wang X F, Chen G R 2004 IEEE Trans. Circuits Syst. Regul. Pap. 51 2074
Google Scholar
[7] Zhou J, Lu J A, Lu J H 2008 Automatica 44 996
Google Scholar
[8] Yu W W, Chen G R, Lu J H 2009 Automatica 45 429
Google Scholar
[9] Francesco S, Mario D B, Franco G, Chen G R 2007 Phys. Rev. E 75 046103
Google Scholar
[10] Wang L, Dai H P, Dong H, Cao Y Y, Sun Y X 2008 Eur. Phys. J. B 61 335
Google Scholar
[11] Wang X F, Su H S 2014 Annu Rev Control 38 103
Google Scholar
[12] Song Q, Cao J D 2009 IEEE Trans. Circuits Syst. Regul. Pap. 57 672
[13] Ali G, Soleyman A 2016 Nonlinear Dyn. 83 1003
Google Scholar
[14] Rong Z H, Li X, Lu W L 2009Proc. IEEE Int. Symp. Circuits Syst.Taipei, China, May 17–24, 2009 p1689
[15] Jia Z, Li X 2010 29th Chinese Control Conference Beijing, China, July 29–31, 2010 p4656
[16] Wang X Y, Liu X W 2018 Nonlinear Dyn. 92 13
Google Scholar
[17] Gong K, Kang L 2018 J. Syst. Sci. Inf. 6 366
[18] Jin Y, Bao Q, Zhang Z 2019 IEEE Int. Conference on Data Mining, Beijing, China, November 8–11, 2019 p339
[19] Amani A M, Jalili M, Yu X, Stone L 2017 IEEE Trans. Circuits Syst. Express Briefs 64 685
Google Scholar
[20] 陆君安, 刘慧, 陈娟 2016 复杂动态网络的同步（第一版）（北京: 高等教育出版社）第49页
Lu J A, Liu H, Chen J 2016 Synchronization in Complex Dynamical Networks (Vol. 1) (Beijing: Higher Education Press) p49 (in Chinese)
[21] Pirani M, Sundaram S 2015 IEEE Trans. Autom. Control 61 509
[22] Kitsak M, Gallos L, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nat. Phys. 6 888
Google Scholar
[23] Physicians network dataset, KONECT http://konect.unikoblenz.de/networks/ [2017.9.9]
[24] Danielle S B, Mason A P, Nicholas F W, Scott T G, Jean M C, Peter J M 2013 Chaos 23 013142
Google Scholar
[25] 徐明明, 陆君安, 周进 2016 物理学报 65 028902
Google Scholar
Xu M M, Lu J A, Zhou J 2016 Acta Phys. Sin. 65 028902
Google Scholar
DownLoad:
Catalog
Metrics
- Abstract views: 9090
- PDF Downloads: 272
- Cited By: 0
