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

陈晶; 祁子怡

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

您当前的位置：

首页 >

文章列表页 >

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

学术通信 | 更新时间：2024-06-05

- 基于时序关系的社交网络影响最大化算法研究
- Research on social network influence maximization algorithm based on time sequential relationship
- 通信学报 2020年41卷第10期页码：211-221
- 作者机构：
  
  1. 燕山大学信息科学与工程学院，河北秦皇岛 066004
  2. 河北省虚拟技术与系统集成重点实验室，河北秦皇岛 066004
  3. 河北省软件工程重点实验室，河北秦皇岛 066004
- 作者简介：
  
  [ "陈晶（1976- ），女，河北秦皇岛人，博士，燕山大学副教授、硕士生导师，主要研究方向为对等网络、社会计算、Web服务" ]
  [ "祁子怡（1995- ），女，河北石家庄人，燕山大学硕士生，主要研究方向为影响最大化" ]
- 基金信息：
  
  国家自然科学基金资助项目(61602401);国家自然科学基金资助项目(61871465);河北省高等学校科学技术研究项目(QN2018074);河北省高等学校科学技术研究项目(ZD2019004);河北省自然科学基金资助项目(F2019203157)
- DOI：10.11959/j.issn.1000-436x.2020191
  中图分类号： TP399
- 网络出版日期：2020-10，
  
  纸质出版日期：2020-10-25
- 稿件说明：
移动端阅览
陈晶, 祁子怡. 基于时序关系的社交网络影响最大化算法研究[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.
陈晶, 祁子怡. 基于时序关系的社交网络影响最大化算法研究[J]. 通信学报, 2020,41(10):211-221. DOI： 10.11959/j.issn.1000-436x.2020191.

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 .

浏览量

792

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

支持延时约束的覆盖多播路由协议的研究