Core-like groups result in invalidation of identifying super-spreader by k-shell decomposition

Abstract

Identifying the most influential spreaders is an important issue in understanding and controlling spreading processes on complex networks. Recent studies showed that nodes located in the core of a network as identified by the k-shell decomposition are the most influential spreaders. However, through a great deal of numerical simulations, we observe that not in all real networks do nodes in high shells are very influential: in some networks the core nodes are the most influential which we call true core, while in others nodes in high shells, even the innermost core, are not good spreaders which we call core-like group. By analyzing the k-core structure of the networks, we find that the true core of a network links diversely to the shells of the network, while the core-like group links very locally within the group. For nodes in the core-like group, the k-shell index cannot reflect their location importance in the network. We further introduce a measure based on the link diversity of shells to effectively distinguish the true core and core-like group, and identify core-like groups throughout the networks. Our findings help to better understand the structural features of real networks and influential nodes.

Figure 1. The imprecision of k_S and k as a function of p for nine real networks.

The k_S imprecision (black squares) and k imprecision (red circles) are compared in each network. p is the proportion of nodes calculated, ranging from 0.003 to 0.029. See Fig. S1 for large p plots in SI.

Figure 2. The imprecision of k_S and k as a function of k_S for six real networks.

The k_S imprecision (black squares) and k imprecision (red circles) are compared in each network. Each square represents the k_S imprecision of nodes in k_S-core, and each circle represents the k imprecision of n highest degree nodes, where n equals to the number of nodes in k_S-core. k_S is an integer representing the shell index, ranging from the smallest k_S value to the largest k_S value in the network.

Figure 3. Link strength of shells for the real networks.

The link strength of each shell to its lower shells (black squares), equal shell (red circles) and upper shells (blue triangles) are represented. k_S ranges from the smallest k_S value to the largest k_S value in the network.

Figure 4. Link strength of the innermost core to each shell of the network.

(a) The link strength of the innermost core to each shell exhibits a U-shape curve in Router (black squares), Emailcontact (red circles) and AS (blue triangles) networks. (b) The link strength of the innermost core to each shell exhibit a slope in Email (black squares), CA-Hep (red circles) and Hamster (blue triangles) networks. k_S ranges from the smallest k_S value to the largest k_S value in the network.

Figure 5. Link entropy of the innermost core for the real networks and their randomized version.

(a) Link entropy of the innermost core for the real networks. (b) Link entropy of the innermost core for the degree-preserving randomized networks. is the largest k_S value in the network. is the link entropy of the innermost core.

Figure 6. Locating core-like groups in real networks by link entropy.

(a)–(c) The imprecision of k_S and k as a function of k_S for three real networks. The k_S imprecision(black squares) and k imprecision(red circles) are compared. Link entropy of shells in three networks. is the link entropy of k_S shell. Hollow red circles outline the shells which are densely connected core-like groups. These are 21-shell, 16-shell and 15-shell in PGP, 7-shell and 6-shell in Netsci and 48-shell and 30-shell in Astro. k_S ranges from the smallest k_S value to the largest k_S value in the network.