jalu的个人博客分享 http://blog.sciencenet.cn/u/jalu

博文

[转载]网络节点组重要性指标:删后矩阵最小特征值

已有 656 次阅读 2021-6-3 10:40 |系统分类:论文交流|文章来源:转载

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

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

收录于话题


图片


导语


节点重要性排序是复杂网络研究的重要问题。以往研究多针对网络单个节点重要性,并开发出多种评价指标。最近的新工作则从节点组的角度讨论节点重要性,并提出「删后矩阵最小特征值」这一指标。该研究在多层网络、网络可靠性、鲁棒性、脆弱性及许多跨学科领域中有广泛的应用前景。

图片

陆君安、刘慧 | 作者

邓一雪 | 编辑



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


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

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

image.png  

图1

image.png

图2

节点介数(betweenness)也是衡量节点重要性的指标[2],它指通过该节点最短路径的数目,反映了节点在网络中的枢纽性。节点介数越大, 说明删除这样的节点会造成大量节点对之间的最短路径变长。度大的节点介数不一定大,度小的节点介数也不一定小,如图2。而在搜索引擎中网页的重要性通过PageRank 算法,它的基本思想就是由较多重要的网页链接的网页必定是重要的网页[3],Google 的成功很大程度上决定于网页排序的PageRank 算法。另外,在评价研究者学术影响力中有H-index[4],即高被引文章数,你的引用数就是你的度,引用你朋友中至少与你一样厉害的人数就是你的一阶 H-index,如图3,二阶H-index就是你朋友中一阶 H-index比你高的人数, 所以H-index反映引用你的人中高被引数高不高,这比单纯看文章数目更反映学术影响力。[5]定义一个算子H,H算子作用得到H2H3指数,依次类推最后收敛到核数。从而三个节点度量指标:度、H指数和核数,可以通过算子H连接起来了。[6]将这一结果推广到了加权网络

image.png

图3


image.png

图4


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. 删后矩阵最小特征值


最近我们在[7, 8]中提出一种网络节点组重要性指标——删后矩阵最小特征值。网络可以用Laplacian矩阵表示,它的每一行之和为0,对角线元素为节点的度数,如果我们关心某些点组成的节点组的重要性,首先将Laplacian矩阵删去节点组对应的行和列,余下的主子矩阵称为删后矩阵(the grounded matrix)。Laplacian矩阵的删后矩阵特征值均为正的,我们关注的是其中最小特征值。

通过图5我们很容易掌握中删后矩阵最小特征值的计算过程。考虑网络 I 和 网络 II 中节点4的重要性,首先写出网络的Laplacian矩阵,再删去节点4,这里虽然删后的图相同,但是它们的删后矩阵是不同的,其最小特征值也不同,分别为1和0.4679,因此节点4在网络 I 中比在网络 II 中更重要。同时我们看到,删后矩阵保留了原来图(矩阵)的信息,因此图的节点删除过程中对历史是有记忆的。

image.png

图5


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


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


图片

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

得到牵制控制成功的一个重要的充分条件 image.png,不等式左边是删后矩阵最小特征值,右边常数α由动力学f和内连矩阵P决定,c是网络的耦合强度。对于网络线性反馈牵制控制问题同样也有上述结果。所以,不等式image.png表明删后主子矩阵最小特征值是牵制控制的关键,它的值越大表示牵制的节点越重要,因此删后矩阵最小特征值成为节点组重要性的指标[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分别表示严格从度大和从度小优先控制。从图中看出,在控制节点较少时应控制度大节点,才能够保证删后矩阵最小特征值比较大,而在控制节点较多时恰恰相反,只有控制度小节点才能够保证删后矩阵最小特征值比较大。


image.png

图6


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


实际网络的规模一般都比较大,要枚举地计算所有可能的删后矩阵最小特征值,然后比较哪个最大从而确定最重要的节点组,则是一个NP-hard问题,为此根据[8]中的一个不等式(即删后主子矩阵的最小特征值不超过节点组外的节点与节点组的平均连边数),我们提出一种筛选算法[9],大大减小了计算量。

例 1 N= 1000,  q= 5 的 BA 无标度网络,见图7。

牵制控制两个节点(即确定最重要的2个节点),如果枚举法需计算998阶矩阵的最小特征值,共计算499500次!根据筛选算法只要计算21次。

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


image.png
图7

6. 与其他算法的比较


例 2 利用Dolphin 网络实际数据,选用:1)度选点,2)BC(betweenness centrality),3)K-shell 算法,4)最近提出的基于ESI 指标的算法,与5)删后矩阵最小特征值筛选算法[9]比较如下:

图片
表1

图片
图8

例 3 利用Email网络实际数据比较如下:


image.png

表2

图片
图9

从这两个实际网络数据的不同选点方法比较可见,删后矩阵最小特征值筛选算法有明显的优势。

注:Dolphin 网络及 Email 网络数据来自:
[Physicians  network  dataset,  KONECT  http://konect.uniko blenz.de/networks/ [2017.9.9]


7. 其他应用实例


例 4 一根水平樑如何选择两个基点将它吊起,假设樑长度为 1,然后作细等分(只要细分足够密,离散网络的节点组排序可逼近连续问题的基点选择),分点视为节点,便成为一个链状网络。设N= 82,根据对称性,第一个基点节点从节点1到41中选,另一个从82到42中选。当两个节点选取(21,62)时特征值取得最大值。当两个节点都取两端(1,82)或者中间(41,42)时,删后矩阵最小特征值达最小值。也就是说对于链状图最优节点接近在1/4和3/4的位置。

如果取N=302的链,经计算最优节点为(76,227),也符合上述1/4和3/4的规律。

例 5 寻找正方形中最重要的2个和4个节点。

图片
图片
图10

例 6  比较三个社团在网络中的重要性

红色 8个节点,蓝色 7 个节点,绿色 6 个节点。它们的 Laplacian 矩阵的删后主子矩阵最小特征值分别为 0.1905,0.1792,0.1597,说明红色组最重要,其次为蓝色,最后为绿色。


image.png

图11

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



作者简介:
陆君安(武汉大学数学与统计学院)
刘慧(华中科技大学人工智能与自动化学院)





https://wap.sciencenet.cn/blog-211414-1289498.html

上一篇:[转载]武汉大学新闻网【战“疫”人物】陆君安:75岁教授科研助力疫情防控

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-8-1 11:57

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部