基于全局的引文网络影响力最大化算法

doi:10.3969/j.issn.0253-2778.2020.08.003

中国科学技术大学学报 ›› 2020, Vol. 50 ›› Issue (8): 1058-1063.DOI: 10.3969/j.issn.0253-2778.2020.08.003

基于全局的引文网络影响力最大化算法

张文静，班志杰

1.内蒙古大学计算机学院，内蒙古自治区社会计算与数据处理重点实验室，内蒙古呼和浩特 010000； 2.呼和浩特市规划展览馆，内蒙古呼和浩特 010000

收稿日期:2020-06-05 修回日期:2020-07-28 接受日期:2020-07-28 出版日期:2020-08-31 发布日期:2020-07-28
通讯作者: 班志杰
作者简介:张文静，女，硕士，研究方向：数据挖掘. E-mail: 2501648350@qq.com
基金资助:
国家自然科学基金（61662053）资助.

Citation network’s influence maximization algorithm based on global influence

ZHANG Wenjing, BAN Zhijie

1. Inner Mongolia A.R. Key Laboratory of Data Mining and Knowledge Engineering, College of Computer, Inner Mongolia University, Hohhot 010000, China; 2. Hohhot Historical and Cultural City and Intangible Cultural Heritage Protection Center, Hohhot 010000, China

Received:2020-06-05 Revised:2020-07-28 Accepted:2020-07-28 Online:2020-08-31 Published:2020-07-28

摘要/Abstract

摘要： 从大量的期刊论文中搜寻出最具有影响力的若干篇论文对于学术研究具有重要意义，但现有影响力最大化算法需要结合贪心算法，时间复杂度较高.依据论文引用网络中引用关系的时间单向性和无环特征，提出一种基于节点全局影响力的影响力最大化算法.该算法主要包括： ①计算所有节点的全局影响力.结合引文网络的发表时间特性，构造上三角稀疏影响方阵.在线性阈值传播模型的基础上，利用节点间的直接、间接路径影响以及累积计算规则模拟影响力在网络上的传播过程.方阵每进行一次运算，会将全部节点的影响向下传播一跳，得到下一个路径的影响，并统计全部影响，最终得到表示所有节点全局影响力的方阵;②将全部节点按全局影响力排序.选择前n个节点作为候选节点来选取k个种子节点，在选取的过程中避免影响力较大节点的聚集情况.以真实的学术引文网络数据集为实验数据，将提出的算法与两种基准算法从激活范围和运行时间两个方面进行对比.实验结果表明，该算法大大降低了时间复杂度，且激活范围接近于贪心算法.

关键词: 引文网络, 社交网络, 影响力最大化, 传播模型

Abstract: It is of great significance for academic researches to search out the most influential papers from a huge number of Journal papers. However, the existing algorithms for maximizing influence need to be combined with greedy algorithm, which increases the time complexity. According to the time unidirectional and acyclic features of the citation relationship in the citation network, an algorithm is proposed to maximize the influence based on the global influence of nodes. The algorithm mainly includes: ①Calculating the global influence of all nodes. Combined with the publication time characteristics of the citation network, the upper triangular sparse influence matrix is constructed. On the basis of the linear threshold propagation model, the direct and indirect path effects between nodes and the cumulative calculation rule are used to simulate the propagation process of influence on the network. Every time the square matrix is calculated, the influence of all nodes will be propagated down one hop to get the influence of the next path, and all the influences will be counted to finally get the square matrix representing the global influence of all nodes; ②All nodes will be ranked according to the global influence, and the first n nodes will be selected as candidate nodes to select k seed nodes. By the cumulative calculation rule, the proposed algorithm avoids the overlapping of influence among nodes during the process of selecting seed nodes. The real academic citation network data set is taken as the experimental sample, and our algorithm is compared with the two benchmark algorithms in terms of activation range and running time. Experimental results show that the proposed algorithm greatly reduces the time complexity, and that the activation range is close to the greedy algorithm.

Key words: citation network, social network, influence maximization, propagation model

中图分类号:

TP391

张文静，班志杰. 基于全局的引文网络影响力最大化算法[J]. 中国科学技术大学学报, 2020, 50(8): 1058-1063.

ZHANG Wenjing, BAN Zhijie. Citation network’s influence maximization algorithm based on global influence[J]. Journal of University of Science and Technology of China, 2020, 50(8): 1058-1063.

参考文献

［1］
GRANOVETTER M. Threshold models of collective behavior [J]. American Journal of Sociology, 1978, 83(6):1420-1443.
[2] KEMPE D, KLEINBERG J, TARDOS E. Maximizing the spread of influence through a social network [C]// Ninth ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. Washington DC: ACM, 2003:137-146.
[3] RICHARDSON M. Mining the network value of customers [C]// Seventh ACM SIGKDD Conference on Knowledge Discovery and Data Mining, San Francisco, CA: ACM, 2001: 57-66.
[4] RICHARDSON M, DOMINGOS P, GLANCE N. Knowledge-sharing sites for viral marketing [C]// Eighth ACM SIGKDD Conference on Knowledge Discovery and Data Mining,Edmonton, AB: ACM, 2002: 61-70.
[5] WATTS D J. A simple model of global cascades on random networks [J]. Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(9):5766-5771.
[6] LESKOVEC J，KRAUSE A, GUESTRIN C, et al. Cost-effective outbreak detection in network[C]// 13th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, San Jose California: ACM, 2007:420-429.
[7] GOYAL A, LU W, LAKSHMANAN L V. Celf++: optimizing the greedy algorithm for influence maximization in social networks[C]//20th International Conference on World Wide Web, New York: Association for Computing Machinery, 2011:47-48.
[8] CHEN W, WANG Y, YANG S. Efficient influence maximization in social networks [C]// 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Paris: ACM, 2009:199-208.
[9] 田家堂, 王轶彤, 冯小军. 一种新型的社会网络影响最大化算法[J]. 计算机学报, 2011, 34(10):1956-1965.
[10] 陈浩, 王轶彤. 基于阈值的社交网络影响力最大化算法[J]. 计算机研究与发展, 2012, 49(10):2181-2188.
[11] AGARWAL S, MEHTA S. Social influence maximization using genetic algorithm with dynamic probabilities[C]// Seventh International Conference on Contemporary Computing, India: IEEE, 2018:1-6.
[12] WENG X, LIU Z, LI Z. An efficient influence maximization algorithm considering both positive and negative relationships[C]// 2016 IEEE TRUSTCOM/BIGDATASE/ISP, Tian Jin: IEEE, 2016:1931-1936.
[13] LIX, CHENG X, SU S, et al. Community-based seeds selection algorithm for location aware influence maximization [J]. NeuroComputing, 2018, 275:1601-1613.
[14] CUI L, HU H, SHUI Y, et al. DDSE: A novel evolutionary algorithm based on degree-descending search strategy for influence maximization in social networks [J]. Journal of Network & Computer Applications, 2018, 103:119-130.
[15] CHEN W, WAND C, WANG Y. Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]// 16th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining，Washington DC: ACM, 2010：1029-1038.
[16] 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-455.
[17] RADICCHI F, FORTUNATO S, VESPIGNANI A. Citation Networks [J]. UnderstandingComplex Systems, 2012:233-257.
[18] DING Y, YAN E, FRAZHO A, et al. Pagerank for ranking authors in co-citationnetworks [J]. Journal of the American Society for Information Science & Technology, 2014, 60(11):2229-2243.
[19] DING Y. Scientific collaboration and endorsement:Network analysis of coauthorship and citation networks[J]. Journal of Informetrics, 2011, 5(1):187-203.
[20] GUAN J, YAN Y, ZHANG J J. The impact of collaboration and knowledge networks on citations [J]. Journal of Informetrics, 2017, 11(2):407-422.
[21] GOLOSOVSKY M, SOLOMON S. Growing complex network of citations of scientific papers:Modeling and measurements [J]. Physical Review E, 2017, 95(1):012324.
[22] 学术社会网络分析与挖掘系统[EB/OL]. [2018-03]. https://www.aminer.cn.

()
()

[1]	崔文泉，王青芳. 基于双编码器利用在线社交网络信息的股票价格预测[J]. 中国科学技术大学学报, 2020, 50(8): 1093-1101.
[2]	江海洋，王莉. 一种建模社交化点过程序列预测算法[J]. 中国科学技术大学学报, 2019, 49(2): 149-158.
[3]	孙更新，宾晟. 多关系社交网络中基于兴趣匹配的网络舆情传播模型[J]. 中国科学技术大学学报, 2018, 48(9): 730-738.
[4]	罗维佳，乔少杰，韩楠，元昌安，闭应洲，舒红平. 面向LBSN的k-medoids聚类算法[J]. 中国科学技术大学学报, 2017, 47(1): 70-79.
[5]	刘建伟，李为宇，孙钰. 社交网络安全问题及其解决方案[J]. 中国科学技术大学学报, 2011, 41(7): 565-575.

基于全局的引文网络影响力最大化算法

Citation network’s influence maximization algorithm based on global influence

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价