IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v482y2017icp524-531.html
   My bibliography  Save this article

Fast asynchronous updating algorithms for k-shell indices

Author

Listed:
  • Lee, Yan-Li
  • Zhou, Tao

Abstract

Identifying influential nodes in networks is a significant and challenging task. Among many centrality indices, the k-shell index performs very well in finding out influential spreaders. However, the traditional method for calculating the k-shell indices of nodes needs the global topological information, which limits its applications in large-scale dynamically growing networks. Recently, Lü et al. [Nature Commun. 7 (2016) 10168] proposed a novel asynchronous algorithm to calculate the k-shell indices, which is suitable to deal with large-scale growing networks. In this paper, we propose two algorithms to select nodes and update their intermediate values towards the k-shell indices, which can help in accelerating the convergence of the calculation of k-shell indices. The former algorithm takes into account the degrees of nodes while the latter algorithm prefers to choose the node whose neighbors’ values have been changed recently. We test these two methods on four real networks and four artificial networks. The results suggest that the two algorithms can respectively reduce the convergence time up to 75.4% and 92.9% in average, compared with the original asynchronous updating algorithm.

Suggested Citation

  • Lee, Yan-Li & Zhou, Tao, 2017. "Fast asynchronous updating algorithms for k-shell indices," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 482(C), pages 524-531.
    • Handle: RePEc:eee:phsmap:v:482:y:2017:i:c:p:524-531
    DOI: 10.1016/j.physa.2017.04.088
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437117304144
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2017.04.088?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Cesar A. Hidalgo & Ricardo Hausmann, 2009. "The Building Blocks of Economic Complexity," Papers 0909.3890, arXiv.org.
    2. Liu, Jian-Guo & Ren, Zhuo-Ming & Guo, Qiang, 2013. "Ranking the spreading influence in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 392(18), pages 4154-4159.
    3. Andrew G. Haldane & Robert M. May, 2011. "Systemic risk in banking ecosystems," Nature, Nature, vol. 469(7330), pages 351-355, January.
    4. Linyuan Lü & Tao Zhou & Qian-Ming Zhang & H. Eugene Stanley, 2016. "The H-index of a network node and its relation to degree and coreness," Nature Communications, Nature, vol. 7(1), pages 1-7, April.
    5. Lü, Linyuan & Zhou, Tao, 2011. "Link prediction in complex networks: A survey," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 390(6), pages 1150-1170.
    6. Korn, A. & Schubert, A. & Telcs, A., 2009. "Lobby index in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 388(11), pages 2221-2226.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Fei, Liguo & Deng, Yong, 2017. "A new method to identify influential nodes based on relative entropy," Chaos, Solitons & Fractals, Elsevier, vol. 104(C), pages 257-267.
    2. Zhai, Li & Yan, Xiangbin & Zhang, Guojing, 2018. "Bi-directional h-index: A new measure of node centrality in weighted and directed networks," Journal of Informetrics, Elsevier, vol. 12(1), pages 299-314.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Wen Zhou & Jiayi Gu & Yifan Jia, 2018. "h-Index-based link prediction methods in citation network," Scientometrics, Springer;Akadémiai Kiadó, vol. 117(1), pages 381-390, October.
    2. Fei, Liguo & Zhang, Qi & Deng, Yong, 2018. "Identifying influential nodes in complex networks based on the inverse-square law," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 1044-1059.
    3. Guido Caldarelli & Matthieu Cristelli & Andrea Gabrielli & Luciano Pietronero & Antonio Scala & Andrea Tacchella, 2012. "A Network Analysis of Countries’ Export Flows: Firm Grounds for the Building Blocks of the Economy," PLOS ONE, Public Library of Science, vol. 7(10), pages 1-11, October.
    4. Paulo Ferreira & Éder J.A.L. Pereira & Hernane B.B. Pereira, 2020. "From Big Data to Econophysics and Its Use to Explain Complex Phenomena," JRFM, MDPI, vol. 13(7), pages 1-10, July.
    5. Beniamino Pisicoli, 2022. "Banking diversity, financial complexity and resilience to financial shocks: evidence from Italian provinces," International Review of Applied Economics, Taylor & Francis Journals, vol. 36(3), pages 338-402, May.
    6. Lu, Shan & Zhao, Jichang & Wang, Huiwen & Ren, Ruoen, 2018. "Herding boosts too-connected-to-fail risk in stock market of China," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 505(C), pages 945-964.
    7. Mahyar, Hamidreza & Hasheminezhad, Rouzbeh & Ghalebi K., Elahe & Nazemian, Ali & Grosu, Radu & Movaghar, Ali & Rabiee, Hamid R., 2018. "Compressive sensing of high betweenness centrality nodes in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 497(C), pages 166-184.
    8. Yu, Senbin & Gao, Liang & Xu, Lida & Gao, Zi-You, 2019. "Identifying influential spreaders based on indirect spreading in neighborhood," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 523(C), pages 418-425.
    9. Xu, Shuang & Wang, Pei, 2017. "Identifying important nodes by adaptive LeaderRank," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 469(C), pages 654-664.
    10. Xu, Shuqi & Mariani, Manuel Sebastian & Lü, Linyuan & Medo, Matúš, 2020. "Unbiased evaluation of ranking metrics reveals consistent performance in science and technology citation data," Journal of Informetrics, Elsevier, vol. 14(1).
    11. Lin, Li & Guo, Xin-Yu, 2019. "Identifying fragility for the stock market: Perspective from the portfolio overlaps network," Journal of International Financial Markets, Institutions and Money, Elsevier, vol. 62(C), pages 132-151.
    12. Hao Liao & Xiao-Min Huang & Xing-Tong Wu & Ming-Kai Liu & Alexandre Vidmer & Mingyang Zhou & Yi-Cheng Zhang, 2019. "Enhancing countries' fitness with recommender systems on the international trade network," Papers 1904.02412, arXiv.org.
    13. Zhong, Lin-Feng & Shang, Ming-Sheng & Chen, Xiao-Long & Cai, Shi-Ming, 2018. "Identifying the influential nodes via eigen-centrality from the differences and similarities of structure," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 510(C), pages 77-82.
    14. Bao, Zhong-Kui & Ma, Chuang & Xiang, Bing-Bing & Zhang, Hai-Feng, 2017. "Identification of influential nodes in complex networks: Method from spreading probability viewpoint," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 468(C), pages 391-397.
    15. Liu, Qiang & Zhu, Yu-Xiao & Jia, Yan & Deng, Lu & Zhou, Bin & Zhu, Jun-Xing & Zou, Peng, 2018. "Leveraging local h-index to identify and rank influential spreaders in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 379-391.
    16. Liu, Min & Ma, Yue & Cao, Zhulou & Qi, Xingqin, 2018. "ECP-Rank: A novel vital node identifying mechanism combining PageRank with link prediction index," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 1183-1191.
    17. Zareie, Ahmad & Sheikhahmadi, Amir & Fatemi, Adel, 2017. "Influential nodes ranking in complex networks: An entropy-based approach," Chaos, Solitons & Fractals, Elsevier, vol. 104(C), pages 485-494.
    18. Ye, Yucheng & Xu, Shuqi & Mariani, Manuel Sebastian & Lü, Linyuan, 2022. "Forecasting countries' gross domestic product from patent data," Chaos, Solitons & Fractals, Elsevier, vol. 160(C).
    19. Riccardo Di Clemente & Guido L Chiarotti & Matthieu Cristelli & Andrea Tacchella & Luciano Pietronero, 2014. "Diversification versus Specialization in Complex Ecosystems," PLOS ONE, Public Library of Science, vol. 9(11), pages 1-8, November.
    20. Merza, Ádám & London, András & Kiss, István Márton & Pelle, Anita & Dombi, József & Németh, Tamás, 2016. "A világkereskedelem hálózatelméleti vizsgálatának lehetőségeiről [The scope for analysis of world trade through network theory]," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(1), pages 79-98.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:phsmap:v:482:y:2017:i:c:p:524-531. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.