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

doi:10.11959/j.issn.1000-436x.2020191

通信学报 ›› 2020, Vol. 41 ›› Issue (10): 211-221.doi: 10.11959/j.issn.1000-436x.2020191

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

陈晶^1,^2,³,祁子怡¹

¹ 燕山大学信息科学与工程学院，河北秦皇岛 066004
² 河北省虚拟技术与系统集成重点实验室，河北秦皇岛 066004
³ 河北省软件工程重点实验室，河北秦皇岛 066004

修回日期:2020-08-02 出版日期:2020-10-25 发布日期:2020-11-05
作者简介:陈晶（1976- ），女，河北秦皇岛人，博士，燕山大学副教授、硕士生导师，主要研究方向为对等网络、社会计算、Web服务|祁子怡（1995- ），女，河北石家庄人，燕山大学硕士生，主要研究方向为影响最大化
基金资助:
国家自然科学基金资助项目(61602401);国家自然科学基金资助项目(61871465);河北省高等学校科学技术研究项目(QN2018074);河北省高等学校科学技术研究项目(ZD2019004);河北省自然科学基金资助项目(F2019203157)

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

Jing CHEN^1,^2,³,Ziyi QI¹

¹ 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

Revised:2020-08-02 Online:2020-10-25 Published:2020-11-05
Supported by:
The National Natural Science Foundation of China(61602401);The National Natural Science Foundation of China(61871465);Science and Technology Research Project of Hebei Province Higher Education(QN2018074);Science and Technology Research Project of Hebei Province Higher Education(ZD2019004);The Natural Science Foundation of Hebei Province(F2019203157)

摘要/Abstract

摘要：

针对动态社交网络中节点存在的时序关系，提出了基于时序关系的社交网络影响最大化问题，即在时序社交网络上寻找k个节点使信息传播最大化。首先，通过改进度估计算法来计算节点间的传播概率；其次，针对静态社交网络的WCM传播模型无法适用于时序社交网络的问题，提出了IWCM传播模型，并以此为基础提出了TIM算法，该算法分别利用时序启发阶段和时序贪心阶段，选择影响力估计值 inf(u)最大的备选节点和影响力最大的种子节点；最后，通过实验验证了TIM算法的高效性和准确度。此外，所提算法结合了启发式算法和贪心算法的优点，将边际收益的计算范围由网络中所有节点缩减到了备选节点，在保证精度的前提下大大缩短了程序的运行时间。

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

Abstract:

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.

Key words: time sequential social network, influence maximization, information propagation model, greedy algorithm, heuristic algorithm

中图分类号:

TP399

陈晶,祁子怡. 基于时序关系的社交网络影响最大化算法研究[J]. 通信学报, 2020, 41(10): 211-221.

Jing CHEN,Ziyi QI. Research on social network influence maximization algorithm based on time sequential relationship[J]. Journal on Communications, 2020, 41(10): 211-221.

图/表 10

图1

图2

图3

图4

表1

图5

图6

图7

图8

表2

参考文献 25

[1]	RICHARDSON M , DOMINGOS P . Mining knowledge-sharing sites for viral marketing[C]// Proceedings of the International Conference on Knowledge Discovery and Data Mining. Piscataway:IEEE Press, 2002: 61-70.
[2]	KEMPE D , KLEINBERG J , ARDOS é . Maximizing the spread of influence through a social network[C]// Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2003: 137-146.
[3]	LESKOVEC J , KRAUSE A , GUESTRIN C ,et al. Cost-effective outbreak detection in networks[C]// Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2007: 420-429.
[4]	GOYAL A , LU W , LAKSHMANAN L V S . CELF++:optimizing the greedy algorithm for influence maximization in social networks[C]// Proceedings of the 20th International Conference Companion on World Wide Web. New York:ACM Press, 2011: 47-48.
[5]	CHEN W , WANG Y , YANG S . Efficient influence maximization in social networks[C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM Press, 2009: 199-208.
[6]	ZHOU F , GAO M . Influence maximization algorithm for social network based on combined impact probability[J]. Computer Engineering, 2018: 188-193,200.
[7]	李阅志, 祝园园, 钟鸣 . 基于k-核过滤的社交网络影响最大化算法[J]. 计算机应用, 2018,38(2): 464-470.
	LI Y Z , ZHU Y Y , ZHONG M . Social network influence maximization algorithm based on k-core filtering[J]. Journal of Computer Applications, 2018,38(2): 464-470.
[8]	仇丽青, 贾玮, 范鑫 . 基于重叠社区的影响力最大化算法[J]. 数据分析与知识发现, 2019,3(7): 94-102.
	QIU L Q , JIA W , FAN X . Algorithm for maximizing influence based on overlapping communities[J]. Data Analysis and Knowledge Discovery, 2019,3(7): 94-102.
[9]	SIYU R , DERONG S , YUE K ,et al. Topic-aware influence maximization across social networks[J]. Journal of Frontiers of Computer Science and Technology, 2018,8(6): 741-752.
[10]	LI Y , LI V O K . Pricing strategies with promotion time limitation in online social networks[C]// 2018 IEEE/WIC/ACM International Conference on Web Intelligence. Piscataway:IEEE Press, 2018: 254-261.
[11]	赵玉芳, 孙更新, 宾晟 . 基于MRLT模型的多关系社交网络影响力最大化研究[J]. 计算机应用研究, 2020,37(9): 1-6.
	ZHAO Y F , SUN G X , BIN S . Research on maximizing influence of multi-relational social network based on MRLT model[J]. Journal of Computer Application Research, 2020,37(9): 1-6.
[12]	KIM D , HYEON D , OH J ,et al. Influence maximization based on reachability sketches in dynamic graphs[J]. Information Sciences, 2017(394-395): 217-231.
[13]	WANG Y , FAN Q , LI Y ,et al. Real-time influence maximization on dynamic social streams[J]. Proceedings of the VLDB Endowment, 2017,10(7): 805-816.
[14]	ZHANG Y , LI J , YUE K ,et al. Influence maximization methods of correlated information propagation[J]. Journal of Frontiers of Computer Science and Technology, 2018,12(12): 1891-1902.
[15]	郭景峰, 吕加国 . 基于信息偏好的影响最大化算法研究[J]. 计算机研究与发展, 2015,52(2): 533-541.
	GUO J F , LYU J G . Research on influence maximization algorithm based on information preference[J]. Computer Research and Development, 2015,52(2): 533-541.
[16]	曹玖新, 闵绘宇, 王浩然 ,等. 竞争环境中基于主题偏好的利己信息影响力最大化算法[J]. 计算机学报, 2018,48(108): 1-18.
	CAO J X , MIN H Y , WANG H R ,et al. Algorithm for maximizing the influence of selfish information based on topic preference in a competitive environment[J]. Chinese Journal of Computers, 2018,48(108): 1-18.
[17]	吴安彪, 袁野, 乔百友 ,等. 大规模时序图影响力最大化的算法研究[J]. 计算机学报, 2019,42(12): 2647-2664.
	WU A B , YUAN Y , QIAO B Y ,et al. Research on algorithms for maximizing influence of large-scale time series diagrams[J]. Chinese Journal of Computers, 2019,42(12): 2647-2664.
[18]	魏磊 . 基于节点度与派系的影响力最大化研究[D]. 甘肃:兰州大学, 2019.
	WEI L . Research on maximizing influence based on node degree and faction[D]. Gansu:Lanzhou University, 2019.
[19]	LI Y , FAN J , WANG Y ,et al. Influence maximization on social graphs:a survey[J]. IEEE Transactions on Knowledge ＆ Data Engineering, 2018PP(99):1.
[20]	PANZARASA P , OPSAHL T , CARLEY K M . Patterns and dynamics of users’ behavior and interaction:network analysis of an online community[J]. Journal of the Association for Information Ence ＆Technology, 2010,60(5): 911-932.
[21]	PARANJAPE A , BENSON A R , LESKOVEC J . Motifs in temporal networks[C]// The Tenth ACM International Conference on Web Search and Data Mining. New York:ACM Press, 2017.
[22]	YASSERI T , SUMI R , J’ANOS K . Circadian patterns of wikipedia editorial activity:a demographic analysis[J]. PLoS One, 2012,7(1): 1-8.
[23]	陈晶, 刘贤 . 基于覆盖阈值的影响最大化算法的研究[J]. 高技术通讯, 2019,29(5): 438-448.
	CHEN J , LIU X . Research on influence maximization algorithm based on coverage threshold[J]. High Technology Letters, 2019,29(5): 438-448.
[24]	JUNG K , HEO W , CHEN W . IRIE:a scalable influence maximization algorithm for independent cascade model and its extensions[J]. Rev Crim, 2011,56(10): 1451-1455.
[25]	曹玖新, 董丹, 徐顺 . 一种基于k-核的社会网络影响最大化算法[J]. 计算机学报, 2015,38(2): 238-248.
	CAO J X , DONG D , XU S . A k-core based social network influence maximization algorithm[J]. Chinese Journal of Computers, 2015,38(2): 238-248.

数据集	节点数/个	时序边数/条	静态边数/条	时间跨度/天
CollegeMsg	1 899	59 835	20 296	193
Email-Eu-core	986	332 334	24 929	803
Math Overflow	21 688	107 581	90 489	2 350
Ask Ubuntu	75 555	356 822	178 210	2 418

算法	Email-Eu-core/s	CollegeMsg/s	Math Overflow/s	Ask Ubuntu/s
greedy算法	307.69	1 369.25	9 692.02	6 065.09
IEIR算法	4.56	16.99	4.55	10.05
CCA	0.61	2.29	3.67	1.46
IMIT算法	1.26	4.01	2.37	2.43
DegreeDiscount算法	0.031	0.25	0.25	0.13
CTMD算法	1.26	1.43	4.64	2.34
TIM算法	0.42	0.95	0.51	0.62

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

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

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 25

相关文章 5

Metrics

推荐阅读 0

[1]	苗春雨,陈丽娜,戴国勇,杨帆,陈庆章. 面向数量最少化的双层WSN中继节点部署算法[J]. 通信学报, 2016, 37(4): 139-148.
[2]	唐伟,郭伟. 多基站无线传感器网络中能量高效的基站位置优选算法[J]. 通信学报, 2010, 31(11): 65-72.
[3]	戴毅,曹健. 基于模糊控制的启发式工作流引擎负载均衡策略[J]. 通信学报, 2006, 27(11): 84-89.
[4]	付明磊,乐孜纯,陆敏. 基于权重均衡的光网络逻辑拓扑优化算法[J]. 通信学报, 2006, 27(10): 38-43.
[5]	吴家皋,杨音颖,陈益新,叶晓国. 支持延时约束的覆盖多播路由协议的研究[J]. 通信学报, 2005, 26(9): 13-20.