ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen 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:
https://doi.org/10.3969/j.issn.0253-2778.2020.08.003
  • Received Date: 05 June 2020
  • Accepted Date: 28 July 2020
  • Rev Recd Date: 28 July 2020
  • Publish Date: 31 August 2020
    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)
  • loading
    • References(22)
  • [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.)
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    |
    Get Citation
    PDF
    XML
    [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.)
    Recommended articles
    TrendMD
    Volume 50 Issue 8 page: 1058-1063
    Cover

    Article Metrics

    Article views (75) PDF downloads(103)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return