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

Jing CHEN; Ziyi QI

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

您当前的位置：

首页 >

文章列表页 >

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

Correspondences | 更新时间：2024-06-05

- Research on social network influence maximization algorithm based on time sequential relationship
- Journal on Communications Vol. 41, Issue 10, Pages: 211-221(2020)
- 作者机构：
  
  1. 燕山大学信息科学与工程学院，河北秦皇岛 066004
  2. 河北省虚拟技术与系统集成重点实验室，河北秦皇岛 066004
  3. 河北省软件工程重点实验室，河北秦皇岛 066004
- 作者简介：
- 基金信息：
  
  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)
- DOI：10.11959/j.issn.1000-436x.2020191
  CLC： TP399
- Online First：2020-10，
  
  Published：25 October 2020
- 稿件说明：
移动端阅览
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.
DOI：

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. DOI： 10.11959/j.issn.1000-436x.2020191.

摘要

针对动态社交网络中节点存在的时序关系，提出了基于时序关系的社交网络影响最大化问题，即在时序社交网络上寻找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.

关键词

Keywords

references

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 .

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 .

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 .

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 .

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 .

ZHOU F , GAO M . Influence maximization algorithm for social network based on combined impact probability [J ] . Computer Engineering , 2018 : 188 - 193 ,200.

李阅志 , 祝园园 , 钟鸣 . 基于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 .

仇丽青 , 贾玮 , 范鑫 . 基于重叠社区的影响力最大化算法 [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 .

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 .

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 .

赵玉芳 , 孙更新 , 宾晟 . 基于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 .

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 .

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 .

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 .

郭景峰 , 吕加国 . 基于信息偏好的影响最大化算法研究 [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 .

曹玖新 , 闵绘宇 , 王浩然 , 等 . 竞争环境中基于主题偏好的利己信息影响力最大化算法 [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 .

吴安彪 , 袁野 , 乔百友 , 等 . 大规模时序图影响力最大化的算法研究 [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 .

魏磊 . 基于节点度与派系的影响力最大化研究 [D ] . 甘肃:兰州大学 , 2019 .

WEI L . Research on maximizing influence based on node degree and faction [D ] . Gansu:Lanzhou University , 2019 .

LI Y , FAN J , WANG Y , et al . Influence maximization on social graphs:a survey [J ] . IEEE Transactions on Knowledge ＆ Data Engineering , 2018 PP( 99 ):1.

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 .

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 .

YASSERI T , SUMI R , J’ANOS K . Circadian patterns of wikipedia editorial activity:a demographic analysis [J ] . PLoS One , 2012 , 7 ( 1 ): 1 - 8 .

陈晶 , 刘贤 . 基于覆盖阈值的影响最大化算法的研究 [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 .

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 .

曹玖新 , 董丹 , 徐顺 . 一种基于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 .

Views

1468

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Delay constraint supported overlay multicast routing protocol

Related Author

WU Jia-gao

YANG Yin-ying

CHEN Yi-xin

YE Xiao-guo

Related Institution

Department of Computer Science and Engineering, Southeast University

Key Laboratory of Computer Network and Information Integration

AI问答

⁰