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

Marius Eidsaa and Eivind Almaas

Physica A: Statistical Mechanics and its Applications, 2016, vol. 449, issue C, 111-125

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.

Keywords: Complex networks; Weighted networks; Network decomposition; k-core analysis; k-shell analysis; s-core analysis (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0378437115011528
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

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:phsmap:v:449:y:2016:i:c:p:111-125

DOI: 10.1016/j.physa.2015.12.115

Access Statistics for this article

Physica A: Statistical Mechanics and its Applications is currently edited by K. A. Dawson, J. O. Indekeu, H.E. Stanley and C. Tsallis

More articles in Physica A: Statistical Mechanics and its Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().