Citation network’s influence maximization algorithm based on global influence

ZHANG Wenjing; BAN Zhijie

doi:10.3969/j.issn.0253-2778.2020.08.003

JUSTC > 2020 > 50(8): 1058. > DOI: 10.3969/j.issn.0253-2778.2020.08.003 CSTR: 32290.14.j.issn.0253-2778.2020.08.003

PDF (1106 KB)

Open Access JUSTC Original Paper

Citation network’s influence maximization algorithm based on global influence

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

Cite this: JUSTC, 2020, 50(8): 1058-1063

https://doi.org/10.3969/j.issn.0253-2778.2020.08.003

CSTR: 32290.14.j.issn.0253-2778.2020.08.003

More Information

Received Date: June 04, 2020
Revised Date: July 27, 2020
Accepted Date: July 27, 2020
Published Date: August 30, 2020

Full text PDF

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.

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.

FullText(HTML)

References (22)

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.)

Cited By

Track Citations

Get Citation

{{if article.articleBusiness.pdfLink && article.articleBusiness.pdfLink != ''}} {{else}} {{/if}}PDF

XML

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.)

TrendMD

Volume 50 Issue 8 PP. 1058-1063

Cover

Keywords

Article Metrics

Article views PDF downloads

Citation network’s influence maximization algorithm based on global influence

Abstract

Abstract

References

Catalog

References

Related Articles

TrendMD

Article Metrics

Authors

Browse

Contact Us

About

Citation network’s influence maximization algorithm based on global influence

Share

Tools

Abstract

Abstract

References

Catalog

References

Related Articles

TrendMD

Article Metrics

Authors

Browse

Contact Us

About

Export File

Citation

Format

Content