Investigating the relationship between kk-core and ss-core network decompositions

• A systematic study of the transition between kk-core and ss-core analysis is proposed.
• The node content in innermost kk-cores and ss-cores is similar for many network topologies and link-weight combinations.
• For scale-free networks with positively correlated link weights, the innermost ss-cores are robust to link-weight discretization.

Network decomposition methods, such as the much used kk-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. kk-core analysis, recent works have introduced network decomposition methods that apply to weighted networks. Here, we investigate the relationship between kk-core decomposition for unweighted networks and ss-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 ss-core decompositions with respect to discretization levels. (2) For negatively correlated link-weight distributions, the resulting ss-core decomposition has no similarity to the kk-cores. Since several combinations of network topology and link-weight distributions give rise to a core-structure that is highly similar to the full ss-core for a large range of link-discretization levels, it is possible to significantly speed up the numerical ss-core analysis for these situations.