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

Investigating the relationship between k-core and s-core network decompositions

Author

Listed:
  • Eidsaa, Marius
  • Almaas, Eivind

Abstract

Network decomposition methods, such as the much used k-core analysis, are able to identify globally central regions of networks. The decomposition approaches are hierarchical and identify nested sets of nodes with increasing centrality properties. While most studies have been concerned with unweighted networks, i.e. k-core analysis, recent works have introduced network decomposition methods that apply to weighted networks. Here, we investigate the relationship between k-core decomposition for unweighted networks and s-core decomposition for weighted networks by systematically employing a link-weight scheme that gradually discretizes the link weights. We applied this approach to the Erdős–Rényi model and the scale-free configuration model for five different weight distributions, and two empirical networks, the US air traffic network and a Facebook network. We find that (1) both uniformly random and positively correlated link-weight distributions give rise to highly stable s-core decompositions with respect to discretization levels. (2) For negatively correlated link-weight distributions, the resulting s-core decomposition has no similarity to the k-cores. Since several combinations of network topology and link-weight distributions give rise to a core-structure that is highly similar to the full s-core for a large range of link-discretization levels, it is possible to significantly speed up the numerical s-core analysis for these situations.

Suggested Citation

  • Eidsaa, Marius & Almaas, Eivind, 2016. "Investigating the relationship between k-core and s-core network decompositions," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 449(C), pages 111-125.
  • Handle: RePEc:eee:phsmap:v:449:y:2016:i:c:p:111-125
    DOI: 10.1016/j.physa.2015.12.115
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437115011528
    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.2015.12.115?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. Zhang Bin & Horvath Steve, 2005. "A General Framework for Weighted Gene Co-Expression Network Analysis," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 4(1), pages 1-45, August.
    2. Wei, Bo & Liu, Jie & Wei, Daijun & Gao, Cai & Deng, Yong, 2015. "Weighted k-shell decomposition for complex networks based on potential edge weights," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 420(C), pages 277-283.
    3. Bae, Joonhyun & Kim, Sangwook, 2014. "Identifying and ranking influential spreaders in complex networks by neighborhood coreness," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 395(C), pages 549-559.
    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. Li, Jiaman & Dong, Xiucheng & Jiang, Qingzhe & Dong, Kangyin & Liu, Guixian, 2021. "Natural gas trade network of countries and regions along the belt and road: Where to go in the future?," Resources Policy, Elsevier, vol. 71(C).

    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. Namtirtha, Amrita & Dutta, Animesh & Dutta, Biswanath, 2018. "Identifying influential spreaders in complex networks based on kshell hybrid method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 499(C), pages 310-324.
    2. Al-Azim, Nouran Ayman R. Abd & Gharib, Tarek F. & Afify, Yasmine & Hamdy, Mohamed, 2020. "Influence propagation: Interest groups and node ranking models," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 553(C).
    3. Wang, Yan & Li, Haozhan & Zhang, Ling & Zhao, Linlin & Li, Wanlan, 2022. "Identifying influential nodes in social networks: Centripetal centrality and seed exclusion approach," Chaos, Solitons & Fractals, Elsevier, vol. 162(C).
    4. Wei, Bo & Liu, Jie & Wei, Daijun & Gao, Cai & Deng, Yong, 2015. "Weighted k-shell decomposition for complex networks based on potential edge weights," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 420(C), pages 277-283.
    5. Yixuan Qiu & Jing Lei & Kathryn Roeder, 2023. "Gradient-based sparse principal component analysis with extensions to online learning," Biometrika, Biometrika Trust, vol. 110(2), pages 339-360.
    6. Ruiz Vargas, E. & Mitchell, D.G.V. & Greening, S.G. & Wahl, L.M., 2014. "Topology of whole-brain functional MRI networks: Improving the truncated scale-free model," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 405(C), pages 151-158.
    7. Ahrum Son & Hyunsoo Kim & Jolene K. Diedrich & Casimir Bamberger & Daniel B. McClatchy & Stuart A. Lipton & John R. Yates, 2024. "Using in vivo intact structure for system-wide quantitative analysis of changes in proteins," Nature Communications, Nature, vol. 15(1), pages 1-17, December.
    8. Wang, Xiaojie & Slamu, Wushour & Guo, Wenqiang & Wang, Sixiu & Ren, Yan, 2022. "A novel semi local measure of identifying influential nodes in complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 158(C).
    9. Yan Guo & Hui Yu & Haocan Song & Jiapeng He & Olufunmilola Oyebamiji & Huining Kang & Jie Ping & Scott Ness & Yu Shyr & Fei Ye, 2021. "MetaGSCA: A tool for meta-analysis of gene set differential coexpression," PLOS Computational Biology, Public Library of Science, vol. 17(5), pages 1-15, May.
    10. Xue Jiang & Han Zhang & Xiongwen Quan & Zhandong Liu & Yanbin Yin, 2017. "Disease-related gene module detection based on a multi-label propagation clustering algorithm," PLOS ONE, Public Library of Science, vol. 12(5), pages 1-17, May.
    11. Mandel, Antoine & Landini, Simone & Gallegati, Mauro & Gintis, Herbert, 2015. "Price dynamics, financial fragility and aggregate volatility," Journal of Economic Dynamics and Control, Elsevier, vol. 51(C), pages 257-277.
    12. Fink, Christian G. & Fullin, Kelly & Gutierrez, Guillermo & Omodt, Nathan & Zinnecker, Sydney & Sprint, Gina & McCulloch, Sean, 2023. "A centrality measure for quantifying spread on weighted, directed networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 626(C).
    13. Yingzhi Zhang & Shubin Liang & Jialin Liu & Peilong Cao & Lan Luan, 2021. "Evaluation for machine tool components importance based on improved LeaderRank," Journal of Risk and Reliability, , vol. 235(3), pages 331-337, June.
    14. Zhe Li & Xinyu Huang, 2023. "Identifying Influential Spreaders Using Local Information," Mathematics, MDPI, vol. 11(6), pages 1-14, March.
    15. Peter Langfelder & Rui Luo & Michael C Oldham & Steve Horvath, 2011. "Is My Network Module Preserved and Reproducible?," PLOS Computational Biology, Public Library of Science, vol. 7(1), pages 1-29, January.
    16. Zhang, Ling & Wen, Shaobo, 2024. "The influence of global gallium trade network dynamics on price: A complex network and panel regression approach," Resources Policy, Elsevier, vol. 93(C).
    17. Faxu Li & Hui Xu & Liang Wei & Defang Wang, 2023. "RETRACTED ARTICLE: Identifying vital nodes in hypernetwork based on local centrality," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-13, January.
    18. Elva María Novoa-del-Toro & Efrén Mezura-Montes & Matthieu Vignes & Morgane Térézol & Frédérique Magdinier & Laurent Tichit & Anaïs Baudot, 2021. "A multi-objective genetic algorithm to find active modules in multiplex biological networks," PLOS Computational Biology, Public Library of Science, vol. 17(8), pages 1-24, August.
    19. 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.
    20. Matias Nehuen Iglesias, 2021. "The Overlooked Insights from Correlation Structures in Economic Geography," Papers in Evolutionary Economic Geography (PEEG) 2105, Utrecht University, Department of Human Geography and Spatial Planning, Group Economic Geography, revised Jan 2021.

    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:449:y:2016:i:c:p:111-125. 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.