搜索

x

留言板

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

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

基于时序网络层间同构率动态演化的重要节点辨识

胡钢 许丽鹏 徐翔

引用本文:
Citation:

基于时序网络层间同构率动态演化的重要节点辨识

胡钢, 许丽鹏, 徐翔

Identification of important nodes based on dynamic evolution of inter-layer isomorphism rate in temporal networks

Hu Gang, Xu Li-Peng, Xu Xiang
PDF
HTML
导出引用
  • 时序网络可以更加准确地描述网络节点在时空演化过程中的交互顺序变化和交互关联关系. 为辨识时序网络中的重要节点, 本文提出基于时序网络层间同构率动态演化的超邻接矩阵建模的重要节点辨识方法. 首先, 依托复杂网络的层间时序关联耦合关系, 定义了相邻与跨层网络综合逼近关系系数. 其次, 依据层内连接关系和层间逼近关系构建时序网络超邻接矩阵. 再次, 使用特征向量中心性方法对时序网络中的节点重要性排序, 分析计算时序全局效率差值, 通过肯德尔相关系数验证. 最后, 实证数据仿真显示: 与经典时序网络模型相比, 本文模型所得Kendall’s τ值在各时间层上平均提高, 最高为8.37%和2.99%, 结论表明时序网络层间同构率的度量方法科学有效.
    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.
      通信作者: 胡钢, hug_2004@126.com
    • 基金项目: 国家自然科学基金(批准号: 51368055, 61702006)资助的课题
      Corresponding author: Hu Gang, hug_2004@126.com
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 51368055, 61702006)
    [1]

    Holme P, Saramäki J 2012 Phys. Rep. 519 97Google Scholar

    [2]

    Albert R, Jeong H, Barabasi 1999 Nature 401 130Google Scholar

    [3]

    Freeman L C 1977 Sociometry 40 35Google Scholar

    [4]

    Borgatti S P, Everett M G 2006 Soc. Networks 28 466Google Scholar

    [5]

    Phillip B 1972 J. Math. Sociol. 2 113Google Scholar

    [6]

    Kitsak M, Gallosl K, Havlin S, Liljeros F, Muchnik L, Stanley H, Makse H 2010 Nat. Phys. 6 888Google Scholar

    [7]

    胡钢, 徐翔, 张维明, 周鋆 2019 电子学报 47 104Google Scholar

    Hu G, Xu X, Zhang W M, Zhou J 2019 Acta Electronica Sin. 47 104Google Scholar

    [8]

    于会, 刘尊, 李勇军 2013 物理学报 62 54Google Scholar

    Yu K, Liu Z, Li Y J 2013 Acta Phys. Sin. 62 54Google Scholar

    [9]

    胡钢, 徐翔, 过秀成 2018 浙江大学学报(工学版) 52 1989Google Scholar

    Hu G, Xu X, Guo X C 2018 J. Zhejiang Univ.-(Eng. Sci.) 52 1989Google Scholar

    [10]

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

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

    [11]

    Li C, Wang L, Sun S W, Xia C Y 2018 Appl. Math. Computation 320 512Google Scholar

    [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 1Google Scholar

    [15]

    Li H J, Bu Z, Wang Z, Cao J 2019 IEEE Trans. Ind. Inf. 16 5327Google Scholar

    [16]

    代萌, 黄生志, 黄强, 王璐, 郭怿 2019 水力发电学报 38 15Google Scholar

    Dai M, Huang S Z, Huang Q, Wang L, Guo Y 2019 J. Hydroelectric Eng. 38 15Google Scholar

    [17]

    Qu C Q, Zhan X X, Wang G H, Wu J L, Zhang Z K 2019 Chaos 29 033116Google Scholar

    [18]

    Wang X, Gu H B, Wang Q Y, Lv J H 2019 Sci. Chin. 62 98

    [19]

    Tang D S, Du W B, Shekhtman L, Wang Y J, Havlin S, Cao X B, Yan G 2020 Natl. Sci. Rev. 7 929Google Scholar

    [20]

    Yang L M, Zhang W, Chen Y F 2015 Front. Inf. Technol. Electron. 16 805Google Scholar

    [21]

    Schaub M T, Delvenne J C, Lambiotte R, Barahona M 2019 Phys. Rev. E 99 062308

    [22]

    李志宇, 梁循, 徐志明, 齐金山, 陈燕方 2017 计算机学报 40 805Google Scholar

    Li Z Y, Liang X, Xu Z M, Qi J S, Chen Y F 2017 Chin. J. Comput. 40 805Google Scholar

    [23]

    郭强, 殷冉冉, 刘建国 2019 电子科技大学学报 48 296Google Scholar

    Guo Q, Yin R R, Liu J G 2019 JEST 48 296Google Scholar

    [24]

    邱路, 黄国妍 2020 物理学报 69 316138901Google Scholar

    Qiu L, Huang G Y 2020 Acta Phys. Sin. 69 316138901Google Scholar

    [25]

    Taylor D, Myers S A, Clauset A, Porter M A 2017 Multiscale Model. Simul. 15 537Google Scholar

    [26]

    杨剑楠, 刘建国, 郭强 2018 物理学报 67 048901Google Scholar

    Yang J N, Liu J G, Guo Q 2018 Acta Phys. Sin. 67 048901Google Scholar

    [27]

    朱义鑫, 张凤荔, 秦志光 2014 计算机应用 34 3184Google Scholar

    Zhu Y X, Zhang F L, Qin Z G 2014 J. Comput. Appl. 34 3184Google Scholar

    [28]

    Holme P, Saramäki J 2013 Temporal Networks (Heidel-berg: Springer) pp1−2

    [29]

    Hamers L 1989 Inf. Process. Manage. 25 315Google Scholar

    [30]

    Zhou T, Lü L, Zhang Y C 2009 Eur. Phys. J. B 71 623Google Scholar

    [31]

    Van D, Sluis A 1979 LAA 26 265Google Scholar

    [32]

    Latora V, Marchiori M 2007 New J. Phys. 9 188Google Scholar

    [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 239Google Scholar

    [35]

    Génois M, Vestergaard C L, Fournet J, Panisson A 2015 Networks Sci. 3 326Google Scholar

    [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

  • 图 1  ISAM算法流程图

    Fig. 1.  Algorithm flowchart of ISAM model.

    图 2  基于层间同构率方法的时序网络建模实例

    Fig. 2.  An example of ISAM model for temporal network.

    图 3  基于时序网络层间同构率的超邻接矩阵模型

    Fig. 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数据相应的结果

    Fig. 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数据相应的结果

    Fig. 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]本文方法
    节点G1G2G3节点G1G2G3节点G1G2G3
    10.28090.44130.239210.37390.47420.228710.41190.42410.3230
    20.05420.24440.197820.00.19860.162920.00.14130.1251
    30.19340.30940.318430.2760.35580.269530.32120.31500.3496
    40.21890.42470.323340.23830.36210.232040.20300.29590.2391
    下载: 导出CSV

    表 2  图2时序网络中各节点之间的时序距离

    Table 2.  Temporal distance of nodes in temporal network of Fig. 2.

    节点编号1234
    10211
    2032
    31302
    41220
    下载: 导出CSV

    表 3  实证网络数据基本统计信息

    Table 3.  Basic statistical features of Workspace and Email-eu-core.

    数据集节点数交互
    次数
    边数时序片段时间
    层数
    Workspace 92 9827 755 2013.6.24–
    2013.7.3
    10
    Email-eu-core 986 332334 24929 360 d 12
    下载: 导出CSV
  • [1]

    Holme P, Saramäki J 2012 Phys. Rep. 519 97Google Scholar

    [2]

    Albert R, Jeong H, Barabasi 1999 Nature 401 130Google Scholar

    [3]

    Freeman L C 1977 Sociometry 40 35Google Scholar

    [4]

    Borgatti S P, Everett M G 2006 Soc. Networks 28 466Google Scholar

    [5]

    Phillip B 1972 J. Math. Sociol. 2 113Google Scholar

    [6]

    Kitsak M, Gallosl K, Havlin S, Liljeros F, Muchnik L, Stanley H, Makse H 2010 Nat. Phys. 6 888Google Scholar

    [7]

    胡钢, 徐翔, 张维明, 周鋆 2019 电子学报 47 104Google Scholar

    Hu G, Xu X, Zhang W M, Zhou J 2019 Acta Electronica Sin. 47 104Google Scholar

    [8]

    于会, 刘尊, 李勇军 2013 物理学报 62 54Google Scholar

    Yu K, Liu Z, Li Y J 2013 Acta Phys. Sin. 62 54Google Scholar

    [9]

    胡钢, 徐翔, 过秀成 2018 浙江大学学报(工学版) 52 1989Google Scholar

    Hu G, Xu X, Guo X C 2018 J. Zhejiang Univ.-(Eng. Sci.) 52 1989Google Scholar

    [10]

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

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

    [11]

    Li C, Wang L, Sun S W, Xia C Y 2018 Appl. Math. Computation 320 512Google Scholar

    [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 1Google Scholar

    [15]

    Li H J, Bu Z, Wang Z, Cao J 2019 IEEE Trans. Ind. Inf. 16 5327Google Scholar

    [16]

    代萌, 黄生志, 黄强, 王璐, 郭怿 2019 水力发电学报 38 15Google Scholar

    Dai M, Huang S Z, Huang Q, Wang L, Guo Y 2019 J. Hydroelectric Eng. 38 15Google Scholar

    [17]

    Qu C Q, Zhan X X, Wang G H, Wu J L, Zhang Z K 2019 Chaos 29 033116Google Scholar

    [18]

    Wang X, Gu H B, Wang Q Y, Lv J H 2019 Sci. Chin. 62 98

    [19]

    Tang D S, Du W B, Shekhtman L, Wang Y J, Havlin S, Cao X B, Yan G 2020 Natl. Sci. Rev. 7 929Google Scholar

    [20]

    Yang L M, Zhang W, Chen Y F 2015 Front. Inf. Technol. Electron. 16 805Google Scholar

    [21]

    Schaub M T, Delvenne J C, Lambiotte R, Barahona M 2019 Phys. Rev. E 99 062308

    [22]

    李志宇, 梁循, 徐志明, 齐金山, 陈燕方 2017 计算机学报 40 805Google Scholar

    Li Z Y, Liang X, Xu Z M, Qi J S, Chen Y F 2017 Chin. J. Comput. 40 805Google Scholar

    [23]

    郭强, 殷冉冉, 刘建国 2019 电子科技大学学报 48 296Google Scholar

    Guo Q, Yin R R, Liu J G 2019 JEST 48 296Google Scholar

    [24]

    邱路, 黄国妍 2020 物理学报 69 316138901Google Scholar

    Qiu L, Huang G Y 2020 Acta Phys. Sin. 69 316138901Google Scholar

    [25]

    Taylor D, Myers S A, Clauset A, Porter M A 2017 Multiscale Model. Simul. 15 537Google Scholar

    [26]

    杨剑楠, 刘建国, 郭强 2018 物理学报 67 048901Google Scholar

    Yang J N, Liu J G, Guo Q 2018 Acta Phys. Sin. 67 048901Google Scholar

    [27]

    朱义鑫, 张凤荔, 秦志光 2014 计算机应用 34 3184Google Scholar

    Zhu Y X, Zhang F L, Qin Z G 2014 J. Comput. Appl. 34 3184Google Scholar

    [28]

    Holme P, Saramäki J 2013 Temporal Networks (Heidel-berg: Springer) pp1−2

    [29]

    Hamers L 1989 Inf. Process. Manage. 25 315Google Scholar

    [30]

    Zhou T, Lü L, Zhang Y C 2009 Eur. Phys. J. B 71 623Google Scholar

    [31]

    Van D, Sluis A 1979 LAA 26 265Google Scholar

    [32]

    Latora V, Marchiori M 2007 New J. Phys. 9 188Google Scholar

    [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 239Google Scholar

    [35]

    Génois M, Vestergaard C L, Fournet J, Panisson A 2015 Networks Sci. 3 326Google Scholar

    [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

  • [1] 谷牧, 任栖锋, 周金梅, 廖胜. 基于地基观测的时序卫星红外光谱建模与分析. 物理学报, 2019, 68(5): 059501. doi: 10.7498/aps.68.20181933
    [2] 王凯莉, 邬春学, 艾均, 苏湛. 基于多阶邻居壳数的向量中心性度量方法. 物理学报, 2019, 68(19): 196402. doi: 10.7498/aps.68.20190662
    [3] 杨剑楠, 刘建国, 郭强. 基于层间相似性的时序网络节点重要性研究. 物理学报, 2018, 67(4): 048901. doi: 10.7498/aps.67.20172255
    [4] 苏臻, 高超, 李向华. 节点中心性对复杂网络传播模式的影响分析. 物理学报, 2017, 66(12): 120201. doi: 10.7498/aps.66.120201
    [5] 张露, 严璐瑶, 鲍洄含, 柴晓茜, 马丹丹, 吴倩楠, 夏凌晨, 姚丹, 钱静. 实现粒子布居高效转移的两种激光脉冲时序方案的理论研究. 物理学报, 2017, 66(21): 213301. doi: 10.7498/aps.66.213301
    [6] 徐明明, 陆君安, 周进. 两层星形网络的特征值谱及同步能力. 物理学报, 2016, 65(2): 028902. doi: 10.7498/aps.65.028902
    [7] 上官丹骅, 邓力, 李刚, 张宝印, 马彦, 付元光, 李瑞, 胡小利. 蒙特卡罗临界计算全局计数效率新算法研究. 物理学报, 2016, 65(6): 062801. doi: 10.7498/aps.65.062801
    [8] 高彦丽, 陈世明. 一种全局同质化相依网络耦合模式. 物理学报, 2016, 65(14): 148901. doi: 10.7498/aps.65.148901
    [9] 宋玉萍, 倪静. 网络集聚性对节点中心性指标的准确性影响. 物理学报, 2016, 65(2): 028901. doi: 10.7498/aps.65.028901
    [10] 张轶, 达新宇. 基于差分平稳时序的Ka波段雨衰预测. 物理学报, 2014, 63(6): 060203. doi: 10.7498/aps.63.060203
    [11] 江虹, 刘从彬, 伍春. 认知无线电网络中提高传输层端到端吞吐率的跨层参数配置. 物理学报, 2013, 62(3): 038804. doi: 10.7498/aps.62.038804
    [12] 苑卫国, 刘云, 程军军, 熊菲. 微博双向关注网络节点中心性及传播 影响力的分析. 物理学报, 2013, 62(3): 038901. doi: 10.7498/aps.62.038901
    [13] 李泽荃, 张瑞新, 杨曌, 赵红泽, 于健浩. 复杂网络中心性对灾害蔓延的影响. 物理学报, 2012, 61(23): 238902. doi: 10.7498/aps.61.238902
    [14] 田柳, 狄增如, 姚虹. 权重分布对加权网络效率的影响. 物理学报, 2011, 60(2): 028901. doi: 10.7498/aps.60.028901
    [15] 吕翎, 李钢, 张檬, 李雨珊, 韦琳玲, 于淼. 全局耦合网络的参量辨识与时空混沌同步. 物理学报, 2011, 60(9): 090505. doi: 10.7498/aps.60.090505
    [16] 魏雅娜, 杨世平. 以两种方法研究强激光场中的非时序双电离现象. 物理学报, 2010, 59(11): 7788-7795. doi: 10.7498/aps.59.7788
    [17] 魏雅娜, 杨世平. 分子核间距对非时序双电离的影响. 物理学报, 2010, 59(10): 7298-7305. doi: 10.7498/aps.59.7298
    [18] 王占山, 张化光, 王智良. 一类混沌神经网络的全局同步. 物理学报, 2006, 55(6): 2687-2693. doi: 10.7498/aps.55.2687
    [19] 肖方红, 阎桂荣, 韩宇航. 混沌时序相空间重构参数确定的信息论方法. 物理学报, 2005, 54(2): 550-556. doi: 10.7498/aps.54.550
    [20] 程愿应, 王又青, 胡 进, 李家熔. 一种新颖的用于光腔模式及光束传输模拟的特征向量法. 物理学报, 2004, 53(8): 2576-2582. doi: 10.7498/aps.53.2576
计量
  • 文章访问数:  6806
  • PDF下载量:  135
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-10-30
  • 修回日期:  2020-12-01
  • 上网日期:  2021-05-09
  • 刊出日期:  2021-05-20

/

返回文章
返回