Search

Article

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

Node-set importance and optimization algorithm of nodes selection in complex networks based on pinning control

Liu Hui Wang Bing-Jun Lu Jun-An Li Zeng-Yang

Citation:

Node-set importance and optimization algorithm of nodes selection in complex networks based on pinning control

Liu Hui, Wang Bing-Jun, Lu Jun-An, Li Zeng-Yang
PDF
HTML
Get Citation
  • 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.
      Corresponding author: Lu Jun-An, jalu@whu.edu.cn
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61773175, 61702377, 61773294)
    [1]

    Liu H, Xu X, Lu J A, Chen G, Zeng Z 2021 IEEE Trans. Syst. Man Cybern. Syst. 51 786Google Scholar

    [2]

    王凯莉, 邬春学, 艾均, 苏湛 2019 物理学报 68 196402Google Scholar

    Wang K L, Wu C X, Ai J, Su S 2019 Acta Phys. Sin. 68 196402Google Scholar

    [3]

    韩伟涛, 伊鹏, 马海龙, 张鹏, 田乐 2019 物理学报 68 186401Google Scholar

    Han W T, Yi P, Ma H L, Zhang P, Tian L 2019 Acta Phys. Sin. 68 186401Google Scholar

    [4]

    Li M, Wang B H 2014 Chin. Phys. B 23 076402Google Scholar

    [5]

    Wang X F, Chen G R 2002 Phys. A 310 521Google Scholar

    [6]

    Li X, Wang X F, Chen G R 2004 IEEE Trans. Circuits Syst. Regul. Pap. 51 2074Google Scholar

    [7]

    Zhou J, Lu J A, Lu J H 2008 Automatica 44 996Google Scholar

    [8]

    Yu W W, Chen G R, Lu J H 2009 Automatica 45 429Google Scholar

    [9]

    Francesco S, Mario D B, Franco G, Chen G R 2007 Phys. Rev. E 75 046103Google Scholar

    [10]

    Wang L, Dai H P, Dong H, Cao Y Y, Sun Y X 2008 Eur. Phys. J. B 61 335Google Scholar

    [11]

    Wang X F, Su H S 2014 Annu Rev Control 38 103Google 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 1003Google 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 13Google 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 685Google 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 888Google 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 013142Google Scholar

    [25]

    徐明明, 陆君安, 周进 2016 物理学报 65 028902Google Scholar

    Xu M M, Lu J A, Zhou J 2016 Acta Phys. Sin. 65 028902Google 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 = 82

    Figure 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.

    图 9  比较三个社团在网络中的重要性, 图中红蓝绿色标识了三个社团, 该图取自文献[24]

    Figure 9.  Compare the importance of three communities in a network, in which red, blue, and green colors implicit three different communities. This network is taken from Ref. [24].

    表 1  节点度排序及节点编号(BA网络, N = 1000, q = 5)

    Table 1.  Degree ordering and node numbering in a BA network with N = 1000 and q = 5.

    节点的度1281221039887867563605853515149474342
    节点编号2113181948143121171063342013
    DownLoad: CSV

    表 2  通过步骤2筛选后的剩余节点数n

    Table 2.  Number of remaining nodes n after Step 2 in Algorithm 1.

    网络参数l = 2l = 3l = 4l = 5l = 6
    NW: N = 1000, P = 0.053.911.930.351.089.1
    NW: N = 1000, P = 0.02511.327.953.4132.9216.1
    BA: N = 1000, q = 105.713.218.622.138.4
    BA: N = 1000, q = 86.714.222.551.2176.3
    BA: N = 1000, q = 57.115.367.1177.51000
    BA: N = 1000, q = 310.255.71000.01000.01000.0
    DownLoad: CSV

    表 3  通过步骤3筛选后剩余节点的组合数量R

    Table 3.  Number of combinations R of remaining nodes after Step 3 in Algorithm 1.

    网络参数l = 2l = 3l = 4l = 5l = 6
    NW: N = 1000, P = 0.055.133.3216.11136.54245.8
    NW: N = 1000, P = 0.02518.2215.61009.51.1 × 1044.7 × 104
    BA: N = 1000, q = 103.311.534.3163.11801.6
    BA: N = 1000, q = 86.316.383.8233.52583.7
    BA: N = 1000, q = 521.669.5306.52203.82.4 × 104
    BA: N = 1000, q = 325.3307.34376.22.2 × 1054.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 786Google Scholar

    [2]

    王凯莉, 邬春学, 艾均, 苏湛 2019 物理学报 68 196402Google Scholar

    Wang K L, Wu C X, Ai J, Su S 2019 Acta Phys. Sin. 68 196402Google Scholar

    [3]

    韩伟涛, 伊鹏, 马海龙, 张鹏, 田乐 2019 物理学报 68 186401Google Scholar

    Han W T, Yi P, Ma H L, Zhang P, Tian L 2019 Acta Phys. Sin. 68 186401Google Scholar

    [4]

    Li M, Wang B H 2014 Chin. Phys. B 23 076402Google Scholar

    [5]

    Wang X F, Chen G R 2002 Phys. A 310 521Google Scholar

    [6]

    Li X, Wang X F, Chen G R 2004 IEEE Trans. Circuits Syst. Regul. Pap. 51 2074Google Scholar

    [7]

    Zhou J, Lu J A, Lu J H 2008 Automatica 44 996Google Scholar

    [8]

    Yu W W, Chen G R, Lu J H 2009 Automatica 45 429Google Scholar

    [9]

    Francesco S, Mario D B, Franco G, Chen G R 2007 Phys. Rev. E 75 046103Google Scholar

    [10]

    Wang L, Dai H P, Dong H, Cao Y Y, Sun Y X 2008 Eur. Phys. J. B 61 335Google Scholar

    [11]

    Wang X F, Su H S 2014 Annu Rev Control 38 103Google 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 1003Google 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 13Google 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 685Google 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 888Google 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 013142Google Scholar

    [25]

    徐明明, 陆君安, 周进 2016 物理学报 65 028902Google Scholar

    Xu M M, Lu J A, Zhou J 2016 Acta Phys. Sin. 65 028902Google Scholar

  • [1] Wang Ting-Ting, Liang Zong-Wen, Zhang Ruo-Xi. Importance evaluation method of complex network nodes based on information entropy and iteration factor. Acta Physica Sinica, 2023, 72(4): 048901. doi: 10.7498/aps.72.20221878
    [2] Ruan Yi-Run, Lao Song-Yang, Tang Jun, Bai Liang, Guo Yan-Ming. Node importance ranking method in complex network based on gravity method. Acta Physica Sinica, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
    [3] Yang Song-Qing, Jiang Yuan, Tong Tian-Chi, Yan Yu-Wei, Gan Ge-Sheng. A method of evaluating importance of nodes in complex network based on Tsallis entropy. Acta Physica Sinica, 2021, 70(21): 216401. doi: 10.7498/aps.70.20210979
    [4] Ren Zhuo-Ming. Node influence of the dynamic networks. Acta Physica Sinica, 2020, 69(4): 048901. doi: 10.7498/aps.69.20190830
    [5] Han Zhong-Ming, Li Sheng-Nan, Zheng Chen-Ye, Duan Da-Gao, Yang Wei-Jie. Link prediction model based on dynamic network representation. Acta Physica Sinica, 2020, 69(16): 168901. doi: 10.7498/aps.69.20191162
    [6] Huang Li-Ya, Tang Ping-Chuan, Huo You-Liang, Zheng Yi, Cheng Xie-Feng. Node importance based on the weighted K-order propagation number algorithm. Acta Physica Sinica, 2019, 68(12): 128901. doi: 10.7498/aps.68.20190087
    [7] Yang Jian-Nan, Liu Jian-Guo, Guo Qiang. Node importance idenfication for temporal network based on inter-layer similarity. Acta Physica Sinica, 2018, 67(4): 048901. doi: 10.7498/aps.67.20172255
    [8] Kong Jiang-Tao, Huang Jian, Gong Jian-Xing, Li Er-Yu. Evaluation methods of node importance in undirected weighted networks based on complex network dynamics models. Acta Physica Sinica, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [9] Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Chen Li-Dong. Node importance measurement based on neighborhood similarity in complex network. Acta Physica Sinica, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [10] Wang Yu, Guo Jin-Li. Evaluation method of node importance in directed-weighted complex network based on multiple influence matrix. Acta Physica Sinica, 2017, 66(5): 050201. doi: 10.7498/aps.66.050201
    [11] Han Min, Zhang Ya-Mei, Zhang Meng. Outer synchronization analysis of two time-varying networks with double delays based on pinning control. Acta Physica Sinica, 2015, 64(7): 070506. doi: 10.7498/aps.64.070506
    [12] Zhou Xuan, Yang Fan, Zhang Feng-Ming, Zhou Wei-Ping, Zou Wei. Control method for complex network topological connection optimization. Acta Physica Sinica, 2013, 62(15): 150201. doi: 10.7498/aps.62.150201
    [13] Ren Zhuo-Ming, Shao Feng, Liu Jian-Guo, Guo Qiang, Wang Bing-Hong. Node importance measurement based on the degree and clustering coefficient information. Acta Physica Sinica, 2013, 62(12): 128901. doi: 10.7498/aps.62.128901
    [14] Liu Jian-Guo, Ren Zhuo-Ming, Guo Qiang, Wang Bing-Hong. Node importance ranking of complex networks. Acta Physica Sinica, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
    [15] Yu Hui, Liu Zun, Li Yong-Jun. Key nodes in complex networks identified by multi-attribute decision-making method. Acta Physica Sinica, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
    [16] Zhou Xuan, Zhang Feng-Ming, Li Ke-Wu, Hui Xiao-Bin, Wu Hu-Sheng. Finding vital node by node importance evaluation matrix in complex networks. Acta Physica Sinica, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [17] Zhao Yan-Yan, Jiang Guo-Ping. Fault diagnosis for a class of output-coupling complex dynamical networks with time delay. Acta Physica Sinica, 2011, 60(11): 110206. doi: 10.7498/aps.60.110206
    [18] Luo Qun, Gao Ya, Qi Ya-Nan, Wu Tong, Xu Huan, Li Li-Xiang, Yang Yi-Xian. Model reference adaptive synchronization in integration complex dynamical networks. Acta Physica Sinica, 2009, 58(10): 6809-6817. doi: 10.7498/aps.58.6809
    [19] Gao Yang, Li Li-Xiang, Peng Hai-Peng, Yang Yi-Xian, Zhang Xiao-Hong. Adaptive synchronization in united complex dynamical network with multi-links. Acta Physica Sinica, 2008, 57(4): 2081-2091. doi: 10.7498/aps.57.2081
    [20] Tracking control of Lorenz systems in unidirectional coupling network. Acta Physica Sinica, 2007, 56(12): 6851-6856. doi: 10.7498/aps.56.6851
Metrics
  • Abstract views:  6671
  • PDF Downloads:  208
  • Cited By: 0
Publishing process
  • Received Date:  09 June 2020
  • Accepted Date:  04 September 2020
  • Available Online:  18 February 2021
  • Published Online:  05 March 2021

/

返回文章
返回