复杂网络牵制控制优化选点算法及节点组重要性排序

刘慧; 王炳珺; 陆君安; 李增扬

doi:10.7498/aps.70.20200872

摘要

本文研究复杂网络动力学模型的无向网络牵制控制的优化选点及节点组重要性排序问题. 根据牵制控制的同步准则, 网络的牵制控制同步取决于网络的Laplacian删后矩阵的最小特征值. 因此, 通过合理选择受控节点集得到一个较大的Laplacian删后矩阵最小特征值, 是牵制控制优化选点问题的核心所在. 基于Laplacian删后矩阵最小特征值的图谱性质, 本文提出了多个受控节点选取的递归迭代算法, 该算法适用于任意类型的网络. 通过BA无标度网络、NW小世界网络及一些实际网络中的仿真实验表明: 该算法在控制节点数较少时, 能有效找到最优受控节点集. 最后讨论了在复杂网络牵制控制背景下节点组重要性排序问题, 提出节点组的重要性排序与受控节点的数目有关.

关键词:

Abstract

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:

作者及机构信息

1.
华中科技大学人工智能与自动化学院, 武汉　430074

2.
武汉大学数学与统计学院, 武汉　430072

3.
华中师范大学计算机学院, 武汉　430079

通信作者: 陆君安, jalu@whu.edu.cn

基金项目: 国家自然科学基金(批准号:61773175, 61702377, 61773294)资助的课题.

Authors and contacts

1.
School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, China

2.
School of Mathematics and Statistics, Wuhan University, Wuhan 430072, China

3.
School of Computer Science, Central China Normal University, Wuhan 430079, China

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)

文章全文 : translate this paragraph

参考文献

[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网络. 不同颜色代表节点的度的大小, 红色表示度大的节点, 蓝色表示度小的节点

Fig. 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)本文算法选点情况

Fig. 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) 本文算法选点情况

Fig. 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矩阵

Fig. 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及其拉普拉斯矩阵

Fig. 5. Chain graph with N = 5 and its Laplacian matrix.

下载: 全尺寸图片幻灯片

图 6 ${\lambda _1}({L_{N - 2}})$与左节点位置(两节点对称选取)的关系图, 这里N = 82

Fig. 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的正方形网格

Fig. 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正方形网格

Fig. 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]

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

节点的度	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

下载: 导出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

下载: 导出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 × 10⁴	4.7 × 10⁴
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 × 10⁴
BA: N = 1000, q = 3	25.3	307.3	4376.2	2.2 × 10⁵	4.5 × 10⁶

下载: 导出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$

下载: 导出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$

下载: 导出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

[1]	王博雅, 杨小春, 卢升荣, 唐勇平, 洪树权, 蒋惠园. 基于图卷积神经网络的多维度节点重要性评估方法. 物理学报, 2024, 73(22): 226401. doi: 10.7498/aps.73.20240937
[2]	汪亭亭, 梁宗文, 张若曦. 基于信息熵与迭代因子的复杂网络节点重要性评价方法. 物理学报, 2023, 72(4): 048901. doi: 10.7498/aps.72.20221878
[3]	阮逸润, 老松杨, 汤俊, 白亮, 郭延明. 基于引力方法的复杂网络节点重要度评估方法. 物理学报, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
[4]	杨松青, 蒋沅, 童天驰, 严玉为, 淦各升. 基于Tsallis熵的复杂网络节点重要性评估方法. 物理学报, 2021, 70(21): 216401. doi: 10.7498/aps.70.20210979
[5]	韩忠明, 李胜男, 郑晨烨, 段大高, 杨伟杰. 基于动态网络表示的链接预测. 物理学报, 2020, 69(16): 168901. doi: 10.7498/aps.69.20191162
[6]	黄丽亚, 汤平川, 霍宥良, 郑义, 成谢锋. 基于加权K-阶传播数的节点重要性. 物理学报, 2019, 68(12): 128901. doi: 10.7498/aps.68.20190087
[7]	杨剑楠, 刘建国, 郭强. 基于层间相似性的时序网络节点重要性研究. 物理学报, 2018, 67(4): 048901. doi: 10.7498/aps.67.20172255
[8]	孔江涛, 黄健, 龚建兴, 李尔玉. 基于复杂网络动力学模型的无向加权网络节点重要性评估. 物理学报, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
[9]	阮逸润, 老松杨, 王竣德, 白亮, 陈立栋. 基于领域相似度的复杂网络节点重要度评估算法. 物理学报, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
[10]	王雨, 郭进利. 基于多重影响力矩阵的有向加权网络节点重要性评估方法. 物理学报, 2017, 66(5): 050201. doi: 10.7498/aps.66.050201
[11]	韩敏, 张雅美, 张檬. 具有双重时滞的时变耦合复杂网络的牵制外同步研究. 物理学报, 2015, 64(7): 070506. doi: 10.7498/aps.64.070506
[12]	周漩, 杨帆, 张凤鸣, 周卫平, 邹伟. 复杂网络系统拓扑连接优化控制方法. 物理学报, 2013, 62(15): 150201. doi: 10.7498/aps.62.150201
[13]	任卓明, 邵凤, 刘建国, 郭强, 汪秉宏. 基于度与集聚系数的网络节点重要性度量方法研究. 物理学报, 2013, 62(12): 128901. doi: 10.7498/aps.62.128901
[14]	刘建国, 任卓明, 郭强, 汪秉宏. 复杂网络中节点重要性排序的研究进展. 物理学报, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
[15]	于会, 刘尊, 李勇军. 基于多属性决策的复杂网络节点重要性综合评价方法. 物理学报, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
[16]	周漩, 张凤鸣, 李克武, 惠晓滨, 吴虎胜. 利用重要度评价矩阵确定复杂网络关键节点. 物理学报, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
[17]	赵岩岩, 蒋国平. 一类输出耦合时延复杂动态网络故障诊断研究. 物理学报, 2011, 60(11): 110206. doi: 10.7498/aps.60.110206
[18]	罗群, 高雅, 齐雅楠, 吴桐, 许欢, 李丽香, 杨义先. 融合复杂动态网络的模型参考自适应同步研究. 物理学报, 2009, 58(10): 6809-6817. doi: 10.7498/aps.58.6809
[19]	高洋, 李丽香, 彭海朋, 杨义先, 张小红. 多重边融合复杂动态网络的自适应同步. 物理学报, 2008, 57(4): 2081-2091. doi: 10.7498/aps.57.2081
[20]	张荣, 胡爱花, 徐振源. 单向耦合网络连接的Lorenz系统的追踪控制. 物理学报, 2007, 56(12): 6851-6856. doi: 10.7498/aps.56.6851

计量

文章访问数: 8786
PDF下载量: 263
被引次数: 0

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

搜索

留言板