Source-linked AI summary
Core-like groups result in invalidation of identifying super-spreader by k-shell decomposition
Ying Liu, Ming Tang, Tao Zhou, Younghae Do
TL;DR
The paper asks when k-shell coreness reliably identifies influential spreaders in real networks and when it fails. It evaluates coreness through spreading simulations, analyzes cross-shell connectivity, and introduces link entropy; the results distinguish diverse-linking true cores from locally connected core-like groups and locate the latter structurally.
Problem
The paper addresses limited evidence that high k-shell nodes are not consistently influential spreaders across real networks, despite the common use of k-shell decomposition for identifying them.
Method
The study uses SIR simulations to compare coreness and degree through imprecision, analyzes connectivity between shells, and defines link entropy to locate core-like groups.
Results
Coreness performs well in some networks but poorly where high-shell nodes form dense local groups; true cores link diversely across shells, whereas core-like groups link locally.
Takeaways & Limitations
Link entropy provides a structural way to distinguish true cores from core-like groups and locate core-like groups without extensive spreading simulations.
Takeaways & Limitations
Core-like groups may still contain some good spreaders, motivating methods that place nodes at their appropriate hierarchical positions, especially in networks with strong community structures.
Abstract
from arXiv · showhide
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.
Results
The study finds that k-shell coreness identifies influential spreaders reliably in some real networks but performs poorly where high-shell nodes form locally connected groups. Structural link diversity distinguishes true cores from core-like groups and supports locating these groups through link entropy.
- Evaluating spreading performance: SIR simulations compare coreness and degree using imprecision, where smaller values indicate more accurate identification of influential spreaders.The imprecision function compares average spreading efficiency among nodes ranked by coreness or degree with the optimal spreading efficiency.
- True cores: In Router, Emailcontact, and AS, coreness imprecision stays below 0.06 for 0.003 ≤ p ≤ 0.029 and is lower than degree imprecision.These networks therefore exhibit reliable coreness-based identification over the demonstrated range.
- Core-like groups: In Email, CA-Hep, and Hamster, coreness imprecision exceeds 0.2 and is higher than degree imprecision, including in the innermost core.The innermost cores of these networks contain many nodes that are not influential spreaders.
- Structural distinction: Rewiring that disrupts dense local core-like patterns improves coreness performance, supporting enhanced link diversity as the structural explanation for the improvement.The reported rewiring increases links from core-like shells to other shells and raises coreness performance.
- Structural distinction: The first group has diverse cross-shell connectivity, whereas the second has dense within-shell connectivity and comparatively fewer links from high shells to lower shells.In the second group, links within shells can exceed links to lower shells, indicating locally connected groups.
- Locating core-like groups: Link entropy identifies low-entropy shells as locally connected core-like groups, including non-innermost shells that coincide with rises in coreness imprecision.This provides a structural way to locate core-like groups without relying on extensive spreading simulations.
Discussion
The study finds that high-coreness groups can be locally connected rather than true network cores, limiting k-shell-based ranking of node importance. It argues that identifying these groups matters for selecting key spreaders and controlling spreading dynamics.
- True cores connect diversely to other shells, whereas core-like groups have dense, local internal connections.
- Core-like groups can have high coreness without occupying the network’s structurally central core.
- Some nodes within core-like groups may still be good spreaders, so their internal importance requires finer ranking.
- Locating core-like groups is important for identifying key players and designing spreading-control strategies.
Methods
The methods combine k-shell decomposition, SIR simulations, network randomization, and real-network data to evaluate spreading influence and structural explanations.
- K-shell decomposition recursively removes low-degree nodes, assigning each node a coreness index kS.
- The SIR model represents nodes as susceptible, infected, or recovered during simulated spreading.
- The infection probability is selected near the epidemic threshold so spreading efficiency reflects network-wide influence rather than uniform or localized transmission.
- Two rewiring schemes preserve degree sequence, with the second also preserving degree correlations while altering network structure.
- The study analyzes real networks including Internet, email, collaboration, and social-network datasets.
Figure legends
The figure legends compare k-shell and degree imprecision, shell-link structure, core link patterns, and link entropy across real networks and randomized counterparts.
- Figure 1 compares kS and degree imprecision as the calculated-node proportion p ranges from 0.003 to 0.029 across nine real networks.
- Figure 2 compares imprecision across kS-core shells, matching each shell’s node count with the highest-degree nodes.
- Figure 3 represents each shell’s link strength to lower, equal, and upper shells using Rl, Re, and Ru.
- Figure 4 shows a U-shaped innermost-core link-strength curve in Router, Emailcontact, and AS, versus a slope in Email, CA-Hep, and Hamster.
- Figure 5 compares innermost-core link entropy in real networks with degree-preserving randomized networks.
- Figure 6 uses shell link entropy and imprecision curves to outline densely connected core-like groups in PGP, Netsci, and Astro.
Additional information
The supplementary material documents additional figures, tables, datasets, and randomized-network analyses supporting the study of shell imprecision, link structure, entropy, and spreading efficiency.
- Table S1 defines d as a shell’s rank distance from the highest shell, with d = 0 denoting the highest shell.
- Supplementary analyses explain imprecision changes through shell sizes and spreading efficiencies in Router, Emailcontact, AS, Email, CA-Hep, Hamster, and Astro.
- In Astro, the 48-shell is described as a local group comprising 0.3% of the network, coinciding with a sharp imprecision rise near p ≈ 0.015.
- Randomized-network figures examine shell clustering, link strength, link entropy, and k-shell imprecision under degree or degree-correlation constraints.
- Spreading-efficiency figures compare shell infection populations across infection probabilities relative to the epidemic threshold.