Identification of important nodes based on dynamic evolution of inter-layer isomorphism rate in temporal networks
-
摘要: 时序网络可以更加准确地描述网络节点在时空演化过程中的交互顺序变化和交互关联关系. 为辨识时序网络中的重要节点, 本文提出基于时序网络层间同构率动态演化的超邻接矩阵建模的重要节点辨识方法. 首先, 依托复杂网络的层间时序关联耦合关系, 定义了相邻与跨层网络综合逼近关系系数. 其次, 依据层内连接关系和层间逼近关系构建时序网络超邻接矩阵. 再次, 使用特征向量中心性方法对时序网络中的节点重要性排序, 分析计算时序全局效率差值, 通过肯德尔相关系数验证. 最后, 实证数据仿真显示: 与经典时序网络模型相比, 本文模型所得Kendall’s τ值在各时间层上平均提高, 最高为8.37%和2.99%, 结论表明时序网络层间同构率的度量方法科学有效.Abstract: The identification of important nodes can not only improve the research about the structure and function of the network, but also encourage people to widely promote the application fields such as in infectious disease prevention, power grid fault detection, information dissemination control, etc. Currently, numerous conclusions have been proved on the identification of important nodes based on the static-network, which may lead the general property to be weakened as resistivity and conductivity experience the dynamic evolution of the relationship between network nodes with time. Temporal network analysis can more accurately describe the change of interaction order and interaction relationship of network nodes in the process of spatio-temporal evolution, and establish an appropriate temporal network model, as well as provide scientific theoretical support for the identification of important nodes. In this paper, we pay attention to considering the intensity of adjacent and cross-layer coupling, and propose a super-adjacency matrix (ISAM) method based on inter-layer isomorphism rate to represent the temporal networks and measure the importance of nodes. And at the same time, it is given that the temporal network G has N nodes and T time layers, and the ISAM is a super adjacency matrix composed of intra-layer and inter-layer relationships of adjacent and cross-layer networks, and its size is NT × NT. We focus on the study of the coupling between adjacent and cross-layer networks. The traditional method (SAM) considers the isomorphism rate of adjacent layers as a constant. In the improved method (SSAM), the connection between layers is described by a neighbor topological overlap coefficient. In this paper, the concept of the compatible similarity between cross-layer networks is given first, and then, by combining the projection value of vectors in n-dimensional real space and the contribution value of node neighbors, the inter-layer approximation relation coefficient of temporal network is inferred and analyzed. Generally speaking, it ensures the difference in coupling degree among different nodes in the inter-layer relationship. We calculate the importance of nodes based on eigenvector centrality in temporal network, which presents the importance of node i progressing with time. Simultaneously, the robustness of temporal network is studied by making use of the difference in temporal global efficiency. In the end, the operator of Kendall correlation coefficient is used to evaluate the node ranking effect of different time layers between the eigenvector-based centrality and the difference of temporal global efficiency. According to the experimental results of ISAM, SSAM and SAM on Workspace and Email-eu-core data sets, the average Kendall τ of both ISAM methods considering adjacent and cross-layer network isomorphism rate can be increased by 8.37% and 2.99% respectively. The conclusions show that the measurement method of temporal network inter-layer isomorphism rate is reliable and effective.
-
图 3 基于时序网络层间同构率的超邻接矩阵模型
Figure 3. Super-adjacency matrix model based on inter-layer isomorphism rate in temporal networks.
图 4 特征向量中心性与单位时间时序全局效率差值的Kendall’s τ结果. 蓝色菱形为ISAM方法, 红色小正方形为SSAM方法, 其他为SAM方法取不同参数的结果 (a) Workspace数据基于层间同构率的超邻接矩阵方法和SSAM及经典超邻接矩阵方法不同参数的Kendall’s τ结果; (b) Email-eu-core数据相应的结果
Figure 4. Results of Kendall’s τ for eigenvector centrality and difference of temporal global efficien- cy. The blue diamond is the ISAM method, the red square is the SSAM method, and the others are the results of the SAM method with different parameters: (a) Result for Workspace by ISAM, SSAM and SAM method; (b) result for Email-eu-core by ISAM, SSAM and SAM method.
图 5 ISAM方法不同偏好系数β下相对SAM方法的Kendall’s τ值平均提高结果 (a) Workspace数据相应的结果; (b) Email-eu-core数据相应的结果
Figure 5. Results of average increase of Kendall’s τ for ISAM method under different preference coe- fficients β compared with SAM method: (a) Result for Workspace; (b) result for Email-eu-core.
表 1 实例网络中节点的特征向量中心性
Table 1. Eigenvector centrality of nodes in temporal network of Fig. 2.
文献[25] 文献[26] 本文方法 节点 G1 G2 G3 节点 G1 G2 G3 节点 G1 G2 G3 1 0.2809 0.4413 0.2392 1 0.3739 0.4742 0.2287 1 0.4119 0.4241 0.3230 2 0.0542 0.2444 0.1978 2 0.0 0.1986 0.1629 2 0.0 0.1413 0.1251 3 0.1934 0.3094 0.3184 3 0.276 0.3558 0.2695 3 0.3212 0.3150 0.3496 4 0.2189 0.4247 0.3233 4 0.2383 0.3621 0.2320 4 0.2030 0.2959 0.2391 
下载: 导出CSV
节点编号 1 2 3 4 1 0 2 1 1 2 ∞ 0 3 2 3 1 3 0 2 4 1 2 2 0
下载: 导出CSV
表 3 实证网络数据基本统计信息
Table 3. Basic statistical features of Workspace and Email-eu-core.
数据集 节点数 交互
次数边数 时序片段 时间
层数Workspace 92 9827 755 2013.6.24–
2013.7.310 Email-eu-core 986 332334 24929 360 d 12
下载: 导出CSV
-
[1] Holme P, Saramäki J 2012 Phys. Rep. 519 97 doi: 10.1016/j.physrep.2012.03.001 [2] Albert R, Jeong H, Barabasi 1999 Nature 401 130 doi: 10.1038/43601 [3] Freeman L C 1977 Sociometry 40 35 doi: 10.2307/3033543 [4] Borgatti S P, Everett M G 2006 Soc. Networks 28 466 doi: 10.1016/j.socnet.2005.11.005 [5] Phillip B 1972 J. Math. Sociol. 2 113 doi: 10.1080/0022250X.1972.9989806 [6] Kitsak M, Gallosl K, Havlin S, Liljeros F, Muchnik L, Stanley H, Makse H 2010 Nat. Phys. 6 888 doi: 10.1038/nphys1746 [7] 胡钢, 徐翔, 张维明, 周鋆 2019 电子学报 47 104 doi: 10.3969/j.issn.0372-2112.2019.02.015Hu G, Xu X, Zhang W M, Zhou J 2019 Acta Electronica Sin. 47 104 doi: 10.3969/j.issn.0372-2112.2019.02.015 [8] 于会, 刘尊, 李勇军 2013 物理学报 62 54 doi: 10.7498/aps.62.020204Yu K, Liu Z, Li Y J 2013 Acta Phys. Sin. 62 54 doi: 10.7498/aps.62.020204 [9] 胡钢, 徐翔, 过秀成 2018 浙江大学学报(工学版) 52 1989 doi: 10.3785/j.issn.1008-973X.2018.10.019Hu G, Xu X, Guo X C 2018 J. Zhejiang Univ.-(Eng. Sci.) 52 1989 doi: 10.3785/j.issn.1008-973X.2018.10.019 [10] 王凯莉, 邬春学, 艾均, 苏湛 2019 物理学报 68 196402 doi: 10.7498/aps.68.20190662Wang K L, Wu C X, Ai J, Su Z 2019 Acta Phys. Sin. 68 196402 doi: 10.7498/aps.68.20190662 [11] Li C, Wang L, Sun S W, Xia C Y 2018 Appl. Math. Computation 320 512 doi: 10.1016/j.amc.2017.10.001 [12] Ogura M, Preciado V M 2017 American Control Conference (ACC) Seattle, USA, May 24−26, 2017 p5001 [13] Tang J, Musolesi M, Mascolo C, Latora V 2009 Proceedings of the 2nd ACM Workshop on Online Social Networks Barcelona, Spain, August 17−17, 2009 p31 [14] Zhao G Y, Huang G Y, He H D, Wang Q 2019 IEEE Access 7 1 doi: 10.1109/ACCESS.2018.2876146 [15] Li H J, Bu Z, Wang Z, Cao J 2019 IEEE Trans. Ind. Inf. 16 5327 doi: 10.1109/tii.2019.2960835 [16] 代萌, 黄生志, 黄强, 王璐, 郭怿 2019 水力发电学报 38 15 doi: 10.11660/slfdxb.20190202Dai M, Huang S Z, Huang Q, Wang L, Guo Y 2019 J. Hydroelectric Eng. 38 15 doi: 10.11660/slfdxb.20190202 [17] Qu C Q, Zhan X X, Wang G H, Wu J L, Zhang Z K 2019 Chaos 29 033116 doi: 10.1063/1.5086059 [18] Wang X, Gu H B, Wang Q Y, Lv J H 2019 Sci. Chin. 62 98 doi: 10.1007/s11431-018-9287-0 [19] Tang D S, Du W B, Shekhtman L, Wang Y J, Havlin S, Cao X B, Yan G 2020 Natl. Sci. Rev. 7 929 doi: 10.1093/nsr/nwaa015 [20] Yang L M, Zhang W, Chen Y F 2015 Front. Inf. Technol. Electron. 16 805 doi: 10.1631/FITEE.1500025 [21] Schaub M T, Delvenne J C, Lambiotte R, Barahona M 2019 Phys. Rev. E 99 062308 doi: 10.1103/PhysRevE.99.062308 [22] 李志宇, 梁循, 徐志明, 齐金山, 陈燕方 2017 计算机学报 40 805 doi: 10.11897/SP.J.1016.2017.00805Li Z Y, Liang X, Xu Z M, Qi J S, Chen Y F 2017 Chin. J. Comput. 40 805 doi: 10.11897/SP.J.1016.2017.00805 [23] 郭强, 殷冉冉, 刘建国 2019 电子科技大学学报 48 296 doi: 10.3969/j.issn.1001-0548.2019.02.021Guo Q, Yin R R, Liu J G 2019 JEST 48 296 doi: 10.3969/j.issn.1001-0548.2019.02.021 [24] 邱路, 黄国妍 2020 物理学报 69 316138901 doi: 10.7498/aps.69.20200221Qiu L, Huang G Y 2020 Acta Phys. Sin. 69 316138901 doi: 10.7498/aps.69.20200221 [25] Taylor D, Myers S A, Clauset A, Porter M A 2017 Multiscale Model. Simul. 15 537 doi: 10.1137/16M1066142 [26] 杨剑楠, 刘建国, 郭强 2018 物理学报 67 048901 doi: 10.7498/aps.67.20172255Yang J N, Liu J G, Guo Q 2018 Acta Phys. Sin. 67 048901 doi: 10.7498/aps.67.20172255 [27] 朱义鑫, 张凤荔, 秦志光 2014 计算机应用 34 3184 doi: 10.11772/j.issn.1001-9081.2014.11.3184Zhu Y X, Zhang F L, Qin Z G 2014 J. Comput. Appl. 34 3184 doi: 10.11772/j.issn.1001-9081.2014.11.3184 [28] Holme P, Saramäki J 2013 Temporal Networks (Heidel-berg: Springer) pp1−2 [29] Hamers L 1989 Inf. Process. Manage. 25 315 doi: 10.1016/0306-4573(89)90048-4 [30] Zhou T, Lü L, Zhang Y C 2009 Eur. Phys. J. B 71 623 doi: 10.1140/epjb/e2009-00335-8 [31] Van D, Sluis A 1979 LAA 26 265 doi: 10.1016/0024-3795(79)90181-2 [32] Latora V, Marchiori M 2007 New J. Phys. 9 188 doi: 10.1088/1367-2630/9/6/188 [33] John T, Mirco M, Cecilia M, Vito L 2009 Proceedings of the 2 nd ACM Workshop on Online Social Networks Barcelona, Spain, August 17, 2009 p31 [34] Kendall M G 1945 Biometrika 33 239 doi: 10.1093/biomet/33.3.239 [35] Génois M, Vestergaard C L, Fournet J, Panisson A 2015 Networks Sci. 3 326 doi: 10.1017/nws.2015.10 [36] Ashwin P, Austin R B, Jure L 2017 In Proceedings of the Tenth ACM International Conference on Web Search and Data Mining Cambridge, United Kingdom, February 6−10, 2017 p601 -
下载:
点击查看大图
图(5) / 表(3)
计量
- 文章访问数: 243
- HTML全文浏览量: 202
- PDF下载量: 0
- 被引次数: 0
京公网安备 11010502036328号 京ICP备17033152号