基于节点中心性排序和交替乘子法的网络重构  

Network reconstruction based on node centrality sorting and alternating direction method of multipliers

作　　者：王建波 刘江华 杜占玮 李平[1] 许小可 Jianbo WANG;Jianghua LIU;Zhanwei DU;Ping LI;Xiaoke XU(School of Computer Science and Software Engineering,Southwest Petroleum University,Chengdu 610500,China;School of Public Health,The University of Hong Kong,Hong Kong 999077,China;Computational Communication Research Center,Beijing Normal University,Zhuhai 519087,China;School of Journalism and Communication,Beijing Normal University,Beijing 100875,China)

机构地区：[1]西南石油大学计算机与软件学院,成都610500 [2]香港大学公共卫生学院,中国香港999077 [3]北京师范大学计算传播学研究中心,珠海519087 [4]北京师范大学新闻传播学院,北京100875

出　　处：《中国科学:信息科学》2025年第4期949-966,共18页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:62173065);北京市自然科学基金(批准号:4242040);深港澳科技计划项目(C类项目)(批准号:SGDX20230821091559022);智慧警务与国家安全风险治理重点实验室2024年度开放课题重点项目(批准号:ZHKFZD2401)资助。

摘　　要：如何从观测时间序列来重构复杂网络结构是网络科学领域的热点和难点问题.近年来统计推断和压缩感知两类方法广泛用于网络重构,然而代表性重构方法的精度、速度和抗噪声性能均有大幅提升空间.本文在经典压缩感知算法的基础上,提出了一种基于节点中心性排序和交替乘子法的网络重构算法.首先对节点状态特征矩阵按照节点中心性的判断方法重新排序重构节点的顺序,然后利用压缩感知对排序后的节点时间状态特征矩阵进行处理,最后引入交替乘子法优化矩阵实现网络拓扑结构的重构.理论分析证明,所提算法的复杂度低于代表性的压缩感知重构方法.实验结果表明,本文将所提算法相比于现有代表性重构方法,提升了重构精度,减少了重构时间,具有更高的抗噪声鲁棒性.本研究提升了网络重构算法应用于大规模网络的准确性、适用性和可靠性,并可在未来扩展到不同类型约束的加权网络重构中.Reconstructing complex network structures from observational time series is a prominent and challenging issue in network science.Recent advancements have seen extensive application of statistical inference and compressed sensing methods for network reconstruction.However,there remains significant room for improvement in terms of the accuracy,speed,and noise robustness of existing representative reconstruction methods.Building on classical compressed sensing algorithms,this paper introduces a network reconstruction algorithm that leverages node centrality ranking and the alternating direction method of multipliers(ADMM).The algorithm first reorders the node state feature matrix based on node centrality assessments,then applies compressed sensing to the reordered matrix,and finally employs ADMM to optimize the matrix for network topology reconstruction.Theoretical analysis demonstrates that the proposed algorithm has lower complexity compared to representative compressed sensing reconstruction methods.Experimental results show that the proposed algorithm enhances reconstruction accuracy,reduces reconstruction time,and offers greater noise robustness compared to existing methods.This research advances the accuracy,applicability,and reliability of network reconstruction algorithms for large-scale networks and has the potential for extension to weighted network reconstruction with various constraints in the future.

关 键 词：网络重构 压缩感知 时间序列 节点中心性 交替乘子法 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]