基于时序关系的社交网络影响最大化算法研究  

Research on social network influence maximization algorithm based on time sequential relationship

作　　者：陈晶[1,2,3] 祁子怡 CHEN Jing;QI Ziyi(School of Information Science and Engineering,Yanshan University,Qinhuangdao 066004,China;Hebei Key Laboratory of Virtual Technology and System Integration,Qinhuangdao 066004,China;Hebei Key Laboratory of Software Engineering,Qinhuangdao 066004,China)

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

出　　处：《通信学报》2020年第10期211-221,共11页Journal on Communications

基　　金：国家自然科学基金资助项目(No.61602401,No.61871465);河北省高等学校科学技术研究项目(No.QN2018074,No.ZD2019004);河北省自然科学基金资助项目(No.F2019203157)。

摘　　要：针对动态社交网络中节点存在的时序关系,提出了基于时序关系的社交网络影响最大化问题,即在时序社交网络上寻找k个节点使信息传播最大化。首先,通过改进度估计算法来计算节点间的传播概率;其次,针对静态社交网络的WCM传播模型无法适用于时序社交网络的问题,提出了IWCM传播模型,并以此为基础提出了TIM算法,该算法分别利用时序启发阶段和时序贪心阶段,选择影响力估计值inf(u)最大的备选节点和影响力最大的种子节点;最后,通过实验验证了TIM算法的高效性和准确度。此外,所提算法结合了启发式算法和贪心算法的优点,将边际收益的计算范围由网络中所有节点缩减到了备选节点,在保证精度的前提下大大缩短了程序的运行时间。For the time sequential relationship between nodes in a dynamic social network,social network influence maximization based on time sequential relationship was proved.The problem was to find k nodes on a time sequential social network to maximize the spread of information.Firstly,the propagation probability between nodes was calculated by the improved degree estimation algorithm.Secondly,in order to solve the problem that WCM models based on static social networks could not be applied to time sequential social networks,an IWCM propagation model was proposed and based on this,a two-stage time sequential social network influence maximization algorithm was proposed.The algorithm used the time sequential heuristic phase and the time sequential greedy phase to select the candidate node with the largest influence estimated value inf(u)and the most influential seeds.At last,the efficiency and accuracy of the TIM algorithm were proved by experiments.In addition,the algorithm combines the advantages of the heuristic algorithm and the greedy algorithm,reducing the calculation range of the marginal revenue from all nodes in the network to the candidate nodes,and greatly shortens the running time of the program while ensuring accuracy.

关 键 词：时序社交网络 影响最大化 信息传播模型 贪心算法 启发式算法 

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