大规模时序图中种子节点挖掘算法研究  

Research on seed node mining algorithm in large-scale temporal graph

作　　者：邹晓红[1,2] 许成伟 陈晶 宋彪[1] 王明月 ZOU Xiaohong;XU Chengwei;CHEN Jing;SONG Biao;WANG Mingyue(School of Information Science and Engineering,Yanshan University,Qinhuangdao 066004,China;Hebei Key Laboratory of Computer Virtual Technology and System Integration,Qinhuangdao 066004,China)

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004 [2]河北省计算机虚拟技术与系统集成重点实验室,河北秦皇岛066004

出　　处：《通信学报》2022年第9期157-168,共12页Journal on Communications

基　　金：国家自然科学基金资助项目(No.62172352,No.61871465);河北省自然科学基金资助项目(No.F2019203157);河北省高等学校科学技术研究资助项目(No.ZD2019004);河北省创新能力提升计划项目(No.22567626H)。

摘　　要：针对现有基于时序图的影响力最大化算法多因时间效率低或影响范围窄,不适用于大规模网络的问题,提出了一种融合启发式算法和贪心策略的种子节点挖掘算法(CHG)。首先,基于时序图中信息传播的时序性,给出了节点二阶度概念,并以此对节点影响力进行启发式评估;其次,根据影响力评估结果对节点进行初步过滤筛选,构建候选种子节点集;最后,通过计算候选种子节点的边际效应,解决节点间影响范围重叠问题,保证获取最优种子节点组合。在3个不同规模的时序网络数据集上进行了实验,实验结果表明,所提算法在相对较短的运行时间下,仍能够保证所得种子节点集具有较高的网络全局影响力,在时间效率与种子节点集影响范围2个方面取得了更好的平衡。Most of the existing maximizing influence algorithms based on temporal graph were not applicable for large-scale networks due to the low time efficiency or narrow influence range.Therefore,the seed node mining algorithm named CHG combining heuristic algorithm and greedy strategy was proposed.Firstly,based on the time sequence characteristics of information diffusion in temporal graph,the concept of two-order degree of nodes was given,and the influence of nodes was heuristically evaluated.Secondly,the nodes were filtered according to the influence evaluation results,and the candidate seed node set was constructed.Finally,the marginal effect of candidate seed nodes was calculated to solve the overlap of influence ranges between nodes to ensure the optimal combination of seed nodes.The experiments were carried out on three different scale data sets,and the results show that the proposed algorithm can ensure the high influence of the seed node set even though its running time is relatively shorter.And it can achieve a better trade-off between the time efficiency and the influence range of the seed node set.

关 键 词：时序图 影响力最大化 种子节点挖掘 信息传播 边际效应 

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