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

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

Abstract

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

CLC Number:

TP399

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.

Figures/Tables 10

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

数据集	节点数/个	时序边数/条	静态边数/条	时间跨度/天
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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 25

Related Articles 7

Metrics

Recommended 0

[1]	Xiaohong ZOU, Chengwei XU, Jing CHEN, Biao SONG, Mingyue WANG. Research on seed node mining algorithm in large-scale temporal graph [J]. Journal on Communications, 2022, 43(9): 157-168.
[2]	Xuan WANG, Yu ZHANG, Junfeng ZHOU, Ziyang CHEN. Influence maximization algorithm based on social network [J]. Journal on Communications, 2022, 43(8): 151-163.
[3]	Lin-han FENG,Zhi-hong QIAN,Dong-cheng JIN. Research on enhanced channel assignment scheme in wireless mesh network [J]. Journal on Communications, 2012, 33(10): 44-50.
[4]	Wei TANG,Wei GUO. Energy efficient optimal sink position selection algorithm for multi-sink wireless sensor networks [J]. Journal on Communications, 2010, 31(11): 65-72.
[5]	Feng ZENG,Zhi-gang CHEN,Xiao-heng DENG. Minimum-cost gateway placement in wireless mesh networks with QoS constraints [J]. Journal on Communications, 2009, 30(6): 80-88.
[6]	Yi DAI,Jian CAO. Fuzzy control-based heuristic algorithm for load balancing in workflow engine [J]. Journal on Communications, 2006, 27(11): 84-89.
[7]	Jia-gao WU,Yin-ying YANG,Yi-xin CHEN,Xiao-guo YE. Delay constraint supported overlay multicast routing protocol [J]. Journal on Communications, 2005, 26(9): 13-20.