基于关键节点的影响力最大化算法

吉林大学学报(信息科学版) ›› 2019, Vol. 37 ›› Issue (2): 162-167.

基于关键节点的影响力最大化算法

王越群^1a，于健^1a，邹跃鹏^1a，李永丽²，董立岩^1a，1b

1．吉林大学a．计算机科学与技术学院; b．符号计算与知识工程教育部重点实验室，长春130012; 2．东北师范大学信息科学与技术学院，长春130117

收稿日期:2018-12-20 出版日期:2019-03-25 发布日期:2019-06-11
通讯作者: 董立岩( 1966— ) ，男，长春人，吉林大学教授，博士生导师，主要从事数据挖掘研究，(Tel) 86-15943013891( E-mail) dongly@ jlu． edu． cn。 E-mail:dongly@ jlu． edu． cn
作者简介:王越群( 1992— ) ，男，吉林四平人，吉林大学博士研究生，主要从事数据挖掘的研究，( Tel) 86-17704346663( E-mail)1004046354@ qq． com; 通讯作者: 董立岩( 1966— ) ，男，长春人，吉林大学教授，博士生导师，主要从事数据挖掘研究，( Tel) 86-15943013891( E-mail) dongly@ jlu． edu． cn。
基金资助:
国家自然科学基金资助项目( 61272209)

Influence of Key-Nodes Based Maximization Algorithm

WANG Yuequn^1a，YU Jian^1a，ZOU Yunpeng^1a，LI Yongli²，DONG Liyan^{1a，1 b}

1a． College of Computer Science and Technology; 1b． Key Laboratory of Symbolic Computation and Knowledge
Engineering of Ministry of Education，Jilin University，Changchun 130012，China;
2． School of Information Science and Technology，Northeast Normal University，Changchun 130117，China

Received:2018-12-20 Online:2019-03-25 Published:2019-06-11

摘要/Abstract

摘要： 为解决LDAG( DAG Algorithm Based on Linear Threshold) 算法在处理关于社会网络影响力最大化过程中，优先考虑网络影响力传播模型、忽视社会网络的拓扑结构问题，利用社交网络社区的结构，有针对性地选择影响力传播的关键节点，对LDAG 算法进行了改进。利用关键节点简化了有向无环图的构造过程，保证了其高精度与运行效率高的特点，同时也优化了算法的时间复杂度和空间复杂度。通过两个有效的实验数据集对算法进行验证，结果表明改进的算法可以大幅度降低算法的运行时间，且对算法的精度影响很小。

关键词: 社交网络, 关键节点, LDAG 算法

Abstract: LDAG( DAG algorithm based on linear threshold) algorithm is a heuristic algorithm for maximizing the influence of social networks． It has the characteristics of high accuracy and high efficiency． When solving the problem of maximizing the influence of social networks，the network influence propagation model is given priority，and then the topological structure of social networks is ignored． In this paper，the LDAG algorithm is improved by using the structure of social network community to select the key nodes of influence propagation．The key nodes are used to simplify the construction process of directed acyclic graph，optimize the time complexity and space complexity of the algorithm，and validate the rationality of the algorithm by using two effective experimental data sets．

Key words: social network, key nodes, LDAG algorithm

中图分类号:

TP301． 6

王越群, 于健, 邹跃鹏, 李永丽, 董立岩. 基于关键节点的影响力最大化算法[J]. 吉林大学学报(信息科学版), 2019, 37(2): 162-167.

WANG Yuequn, YU Jian, ZOU Yunpeng, LI Yongli, DONG Liyan. Influence of Key-Nodes Based Maximization Algorithm[J]. Journal of Jilin University (Information Science Edition), 2019, 37(2): 162-167.