Citation network’s influence maximization algorithm based on global influence

doi:10.3969/j.issn.0253-2778.2020.08.003

Abstract

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

CLC Number:

TP391

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.

References

［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]	CUI Wenquan, WANG Qingfang. A dual encoder-based approach to predicting stock price by leveraging online social network [J]. Journal of University of Science and Technology of China, 2020, 50(8): 1093-1101.
[2]	Wan Liang, Fang Wenpei, Wang Chengyuan, Wang Shanyong. A literature review of enterprise green transformation from the perspective of complex social network and prospects [J]. Journal of University of Science and Technology of China, 2020, 50(10): 1330-1342.
[3]	JIANG Haiyang, WANG Li. A modeling socialization point process sequence prediction algorithm [J]. Journal of University of Science and Technology of China, 2019, 49(2): 149-158.
[4]	SUN Gengxin, BIN Sheng. Network public opinion propagation model based on interest matching in multiple relationship social network [J]. Journal of University of Science and Technology of China, 2018, 48(9): 730-738.
[5]	WANG Yuan, SUN Yingjun, WANG Bo, YANG Chaozhou, YANG Liang. Visual analysis of semantic measuring of online social relationships [J]. Journal of University of Science and Technology of China, 2018, 48(4): 314-321.
[6]	LUO Weijia, QIAO Shaojie, HAN Nan, YUAN Changan, BI Yingzhou, SHU Hongping. A k-medoids based clustering algorithm in location based social networks [J]. Journal of University of Science and Technology of China, 2017, 47(1): 70-79.
[7]	LIU Jianwei, LI Weiyu, SUN Yu. Security issues and solutions on social networks [J]. Journal of University of Science and Technology of China, 2011, 41(7): 565-575.