论文摘要
影响力最大化问题在社交网络中有着广泛的应用,一般地可以将社交网络抽象为静态图,影响力最大化问题是指在图中找出k个最有影响力的顶点,使得信息最大化传播.近年来对此问题的研究主要基于静态图,但是在现实中某些特定网络不可简单地被抽象为静态图,如社交网络及路网中节点间只在某些特定时间存在联系,即节点间的联系是具有时序性的.因此,本文研究了时序图影响力最大化问题,即在时序图上寻找k个顶点使得信息在特定的时间段内最大化传播.传播模型的选择和节点间传播概率的计算是影响力最大化问题的基础,由于基于静态图的IC(Independent Cascade model)传播模型无法应用于时序图,因此本文首先对IC模型进行改进,并提出了ICT(Independent Cascade model on Temporal graph)传播模型,使信息可以通过ICT传播模型在时序图上进行传播.而后通过改进PageRank算法来进行计算节点间的传播概率.然后在此基础上将时序图影响力最大化问题分为两步来进行实现.第一步首先研究时序图节点影响力的计算,并提出了用来计算节点影响力的SIC(Single Node Influence Computation)算法,然后通过对时序图中节点联系时序性这一特性的研究提出了一种改进算法ISIC(Improved SIC).第二步是在第一步结果的基础上来寻找k个种子节点,首先提出了一种基本的时序图影响力最大化算法BIMT(Basic Method for IMTG).但BIMT难以高效解决大规模时序图影响力最大化问题,因此通过优化节点边际效应的计算时间,提出了高效的AIMT(Advanced Method for IMTG)算法,然后通过避免某些节点边际效应的重复计算,对AIMT算法进行改进,从而提出了IMIT(Improved Method for IMTG)算法.最后通过大量实验验证了AIMT和IMIT两种算法高效性和扩展性,相比于BIMT算法,AIMT和IMIT可以更加快速地解决大规模时序图影响力最大化问题.
论文目录
文章来源
类型: 期刊论文
作者: 吴安彪,袁野,乔百友,王一舒,马玉亮,王国仁
关键词: 时序图,影响力最大化,信息传播模型,边际效应,社交网络
来源: 计算机学报 2019年12期
年度: 2019
分类: 信息科技,基础科学
专业: 数学
单位: 东北大学计算机科学与工程学院,北京理工大学计算机学院
基金: 国家重点研发计划项目（2016YFC1401900）,国家自然科学基金（61572119,61622202,U1401256,61732003,61729021）,中央高校基本科研业务费专项资金（N1150402005）资助~~
分类号: O157.5
页码: 2647-2664
总页数: 18
文件大小: 3321K
下载量: 407