网络节点组重要性指标：删后矩阵最小特征值

原创 陆君安、刘慧 集智俱乐部 3天前

收录于话题

#网络科学35

#复杂科学前沿202176

1. 单个节点的重要性排序方法

复杂网络无处不在，现实中人们总是要问：网络众多的节点中哪些节点是最重要的，最具有影响力的。

目前对于单个节点的重要性排序有不少方法，譬如节点的度（degree），即节点的连边数，一般认为度数高的节点与更多的节点链接，所以比较重要，但是后来发现节点度数高的节点未必重要，要看节点是不是处于网络的核心位置，人们引入了中心度（K-shell）和核数概念[1]，网络的外壳和边缘的Ks为1，网络的核心K-shell值大, Ks越高就说明这个节点更靠近网络核心，所以越重要越具有影响力。度大的节点k-shell不一定大，如图1。

图1

图3

2. 节点组重要性提出

上面我们介绍了网络单个节点重要性的一些指标，但是对于网络中多个节点的节点组如何比较其重要性，目前还没有现成的理论和方法。节点组的重要性在现实中广泛地存在，譬如在疾病控制中希望找到那些传播疾病“最厉害”的“超级传播者”，可能是一个也可能是一群；在社会关系网络中如何评价社团的影响力；在大规模网络控制中要对所有节点实施控制是不现实的，那么是否可以通过控制部分节点（譬如百分之五）来达到控制整个网络的目的, 即所谓牵制控制，这就需要比较节点组的重要性和影响力了。而节点组的重要性并非是单个节点重要性排序的直接推广，如图4由7个节点组成的网络，现在问选哪两个种子节点的组合最具有影响力呢，{B,F}虽然单个节点度最大，但是组合后影响力并不强。由于B和F同时认识的人多，所以，B和F组合认识的人的总数为4，少于B和D (或者D和F) 认识的人数5，虽然节点D的度数比B,F小。所以两个节点的节点组应该选{B,D}或者{D,F}，而不是选{B,F}。利用本文后面介绍的删后矩阵最小特征值方法，我们可以量化计算出节点组{B,F}的重要性指数为0.8299，而{B,D}或者{D,F}的重要性指数为1.1392, 是{B,F}的1.37倍。

3. 删后矩阵最小特征值

图5

4. 删后矩阵最小特征值是节点组重要性指标

从动态网络的牵制控制方程出发

考虑网络自适应反馈牵制控制个节点[7]

得到牵制控制成功的一个重要的充分条件 ，不等式左边是删后矩阵最小特征值，右边常数α由动力学f和内连矩阵P决定，c是网络的耦合强度。对于网络线性反馈牵制控制问题同样也有上述结果。所以，不等式表明删后主子矩阵最小特征值是牵制控制的关键，它的值越大表示牵制的节点越重要，因此删后矩阵最小特征值成为节点组重要性的指标。[8]

文献[8]还利用200年前著名的Cauchy 特征值交叉定理[10]出发，得到了有关删后矩阵最小特征值的几个重要性质和估计式。譬如：考虑一个节点时其删后主子矩阵最小特征值不超过1；一般情况下删后主子矩阵的最小特征值有一个上界——节点组外与节点组连接的平均边数，由于这个上界只与度有关，所以它也是后面过滤算法的一个主要依据。另外，删后主子矩阵的最小特征值不会超过节点组外的节点的度数，这一性质可以清楚地解释在大规模网络中，牵制控制中究竟优先控制度大还是度小节点的问题取决于控制节点的比例，当牵制节点数目较少时应优先牵制控制度大节点为主，而在牵制节点数目很大时恰恰相反，应优先牵制控制度小节点为主。图6横坐标表示牵制控制节点数目，纵坐标表示删后矩阵最小特征值，图6（a）是N=1000的BA网络,最大度113,最小度5，（b）是N=1000的NW网络,最大度19，最小度4。其中参数q对应的不同颜色表示度大节点所占的比例，q=1和q=0分别表示严格从度大和从度小优先控制。从图中看出，在控制节点较少时应控制度大节点，才能够保证删后矩阵最小特征值比较大，而在控制节点较多时恰恰相反，只有控制度小节点才能够保证删后矩阵最小特征值比较大。

5. 大规模网络删后矩阵最小特征值算法

牵制控制三个节点，如果枚举法需计算997阶矩阵的最小特征值，共166167000次！根据筛选算法只要计算120次。

6. 与其他算法的比较

7. 其他应用实例

8. 展望

网络节点组重要性排序是网络科学中的一个基本的重要问题，相信这一方法在众多的领域，譬如多层网络结构和动力学，网络的可靠性、鲁棒性、脆弱性，以及跨学科领域（疾病溯源和控制、工程问题、社会网络等），有着广泛的应用前景。目前这个删后矩阵最小特征值算法对于一般规模的网络具有明显的优点，但是在节点数目超大情况下，算法还需要进一步改进和发展。另外，对于一般的加权有向网络的节点组重要性排序还有待研究。

[1] M. Kitsak, L. K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H. E. Stanley, and H. A. Makse, “Identifification of influential spreaders in complex networks,” Nature Physics, vol. 6, no. 11, pp. 888–893, 2010

[2] L. C. Freeman, “A set of measures of centrality based on betweenness.” Sociometry, vol. 40, no. 1, pp. 35–41, 1977.

[3] K. Bryan and T. Leise, “The $ 25,000,000,000 eigenvector: The linear algebra behind google,” SIAM Review, vol. 48, no. 3, pp. 569–581, 2010

[4] Hirsch, J. E. (2005). An index toquantify an individual's scientific research output. Proceedings of theNational academy of Sciences of the United States of America, 102(46),16569-16572.

[5] L. Lü, T. Zhou, Q.-M. Zhang, H. E. Stanley, The H-index of a network nodeand its relation to degree and coreness, Nature Communication 7 (2016) 10168

[6] Xiaoqun Wu , Wenbin Wei, Longkun Tang , Jun’an Lu, and Jinhu Lü ,Coreness and h-Index for Weighted Networks, Transactions on Circuits and Systems–I: Regular Papers, VOL. 66, NO. 8, AUGUST 2019, 3113-3122

[7] Jin Zhou, Jun-an Lu and Jinhu Lü, “Pinning Adaptive Synchronization of A General Complex Dynamical Network,” Automatica, vol. 44, no. 4, pp. 996-1003, 2008.

[8]Hui Liu , Xuanhong Xu, Jun-An Lu, Guanrong Chen , and Zhigang Zeng ，Optimizing Pinning Control of Complex Dynamical Networks Based on Spectral Properties of Grounded Laplacian Matrices，IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS: SYSTEMS, VOL. 51, NO. 2,786-796  2021

[9]刘慧，王炳珺，陆君安，李增扬，复杂网络牵制控制优化选点算法及节点组重要性排序，物理学报 Acta Phys. Sin. Vol. 70, No. 5 (2021) 056401   

[10]R. B. Bapat, Graphs and Matrices. New Delhi, India: Hindustan Book Agency & Springer, 2010