Source-linked AI summary
Improving the accuracy of the k-shell method by removing redundant links-from a perspective of spreading dynamics
Ying Liu, Ming Tang, Tao Zhou, Younghae Do
TL;DR
The paper addresses inaccurate k-shell coreness caused by locally dense core-like groups with low spreading efficiency. It defines edge diffusion importance, removes redundant links, and reapplies k-shell decomposition; the resulting renewed coreness better reflects spreading efficiency and identifies influential spreaders more accurately.
Problem
Core-like groups can have large k-shell indices but low spreading efficiency, limiting k-shell coreness as an indicator of node influence.
Method
The method quantifies edge diffusion importance from outward links at both endpoints, filters low-importance redundant links, and reapplies k-shell decomposition to the residual network.
Results
Renewed coreness is much more accurate than original coreness for identifying influential spreaders and better predicts shell spreading efficiency.
Takeaways & Limitations
Removing redundant links helps decompose network cores more accurately from a spreading-dynamics perspective.
Abstract
from arXiv · showhide
Recent study shows that the accuracy of the k-shell method in determining node coreness in a spreading process is largely impacted due to the existence of core-like group, which has a large k-shell index but a low spreading efficiency. Based on analysis of the structure of core-like groups in real-world networks, we discover that nodes in the core-like group are mutually densely connected with very few out-leaving links from the group. By defining a measure of diffusion importance for each edge based on the number of out-leaving links of its both ends, we are able to identify redundant links in the spreading process, which have a relatively low diffusion importance but lead to form the locally densely connected core-like group. After filtering out the redundant links and applying the k-shell method to the residual network, we obtain a renewed coreness for each node which is a more accurate index to indicate its location importance and spreading influence in the original network. Moreover, we find that the performance of the ranking algorithms based on the renewed coreness are also greatly enhanced. Our findings help to more accurately decompose the network core structure and identify influential nodes in spreading processes.
Results
The study identifies locally dense core-like groups as a source of k-shell inaccuracies and removes low-diffusion-importance links before recomputing coreness. Across real-world networks, renewed coreness better tracks spreading efficiency and identifies influential spreaders.
- Structural feature: Core-like groups are locally dense but poorly connected outward, so their high k-shell indices can correspond to relatively low spreading efficiency.In contrast, true-core nodes connect densely among themselves and broadly to the surrounding network.
- Diffusion importance: The study defines each edge’s diffusion importance from the outward links reachable through both endpoints, averaging its potential spreading influence in both directions.For edge eij, the measure uses the links extending beyond the nearest neighborhood after traversal from either endpoint.
- Filtering method: Edges with diffusion importance below Dthr are filtered as redundant, and k-shell decomposition is then applied to the residual network to obtain renewed coreness.The residual network retains all nodes while keeping only edges whose diffusion importance meets the threshold.
- Validation: The renewed coreness is much more accurate than original coreness for identifying influential spreaders, while random deletion can leave core-like groups in the residual network.Random deletion shows only slight improvement in some networks because it may select redundant links by chance.
- Validation: Renewed coreness produces shell spreading-efficiency trends that are generally more concordant and less fluctuating than those based on the original coreness.Across the studied networks, renewed coreness is described as a better predictor of spreading efficiency from the core to the periphery.
S as a function of shell index. ko
Filtering redundant links and applying k-shell decomposition to the residual network yields renewed coreness that more accurately identifies influential spreaders, while preserving performance where the original method already works well.
- Method: The method defines edge diffusion importance from the out-leaving links of both endpoints and removes redundant links before recomputing coreness.The removed links form locally dense structures but contribute little to spreading.
- Results: Renewed coreness from the residual network is much more accurate than original coreness for identifying influential spreaders.The renewed coreness also generally assigns higher spreading efficiency to nodes with higher values.
- Ranking applications: Filtering redundant links greatly improves ranking accuracy for IRA and neighborhood-coreness algorithms based on renewed coreness.The neighborhood coreness algorithm sums the coreness values of a node’s neighbors.
- Boundary condition: On networks without core-like groups, filtering redundant links leaves coreness performance nearly unchanged, consistent with k-shell robustness to random edge deletion.The reported robustness includes random deletion of up to 50% of edges.
S as a function of shell index. ko
The paper evaluates renewed coreness after redundant-link removal against original and random-deletion coreness, using network structure and spreading efficiency as measures of accuracy.
- Results: The renewed coreness is reported as less imprecise than original-network coreness, while random-deletion coreness serves as a baseline comparison.The supplied results state that the residual-network measure’s imprecision is smaller than the original measure’s.
- Method: The k-shell decomposition iteratively removes low-degree nodes and assigns shell indices, organizing nodes from peripheral shells toward the core.Nodes with degree k = 1 are removed first, followed by nodes with degree k ≤ 2 and progressively higher thresholds.
- Core-like groups: Low-entropy shells relative to adjacent shells identify locally connected core-like groups with limited links leaving the shell.Link entropy is based on how links from nodes in one shell connect to other shells.
- Spreading evaluation: The SIR model estimates each node’s spreading efficiency by averaging the final recovered fraction over 100 spreading simulations.The infection begins from one seed node, with µ = 1; the final recovered proportion is treated as spreading capability.
Figure legends
The figure legends contrast core-like and true cores, relate spreading efficiency to out-leaving links, and compare imprecision for original and residual-network coreness.
- Figure 1: Core-like groups have dense internal connections but few out-leaving links, whereas true cores connect broadly to nodes outside the core.The comparison is illustrated using the core neighborhoods of CA-Hep and Router.
- Figure 2: A positive correlation is shown between spreading efficiency and the number of out-leaving links across core-like-group and highest-efficiency-shell nodes.Blue squares denote core-like-group nodes and red circles denote nodes in the highest spreading-efficiency shell.
- Figure 3: Figure 3 compares original-network coreness k_o^S with residual-network coreness k_r^S through imprecision as a function of shell index.Both shell indices are normalized by the maximum shell index.
- Figure 3: Residual-network coreness has obviously smaller imprecision than original-network coreness in the reported shell-index comparison.The comparison concerns the ability of coreness to indicate spreading efficiency.
- Figure 4: Figure 4 relates shell spreading efficiency to distance from the innermost core, with distance zero denoting the innermost core.The legend distinguishes coreness obtained from the original and residual networks.
Additional information
The additional information documents the study’s figures, imprecision measure, threshold analysis, and redundant-link proportions used to assess renewed coreness.
- Figure S1: Supplementary Figure S1 contrasts CA-Hep’s locally confined innermost core with Router’s innermost core, whose nodes have many links to external neighbors.CA-Hep’s innermost core contains 32 nodes at k-shell index 31, while Router’s contains 26 nodes at maximal index 7.
- Imprecision measure: The imprecision measure compares average spreading efficiency among nodes ranked highest by coreness with that among nodes having the largest spreading efficiency.Smaller imprecision indicates a more accurate coreness measure for predicting spreading efficiency.
- Threshold analysis: For Email, CA-Hep, and Astro, imprecision remains stable when D_thr ≥ 0.5, whereas Blog and PGP show decreasing imprecision as the threshold increases.The supplied passage reports these threshold-dependent patterns for selected networks.
- Redundant-link proportions: Within D_thr ≤ 3, the percentage of identified redundant links is generally within 30%, except for PGP.Table S1 lists redundant-link proportions under different diffusion thresholds.
S as a function of Dthr for nine real-world networks. kr
The supplementary material defines the redundant-link threshold and presents a figure for renewed-coreness imprecision across shell indices.
- Imprecision figure: The supplementary figure reports imprecision of residual-network coreness as a function of shell index.The supplied figure passage identifies the plotted quantity but does not provide numerical values.
- Threshold definition: Table S1 defines D_thr = 0.5 as identifying an edge as redundant when its diffusion importance D_ij is below 0.5.The table reports redundant-link percentages for different diffusion thresholds.
S as a function of p for six real-world networks . ko
Across six real-world networks, residual-network coreness kᵣ is more accurate than original-network coreness kₒ for identifying influential spreaders.
- The comparison evaluates ranking imprecision as a function of p, the proportion of top-ranked nodes under consideration.Here, p ranges from 0.001 to 0.05.
- kᵣ-based coreness is much more accurate than kₒ-based coreness for identifying influential spreaders.
S as a function of shell index for six real-world networks. ko
Shell-index analyses compare original and residual-network coreness across six real-world networks, using normalized shell indices and imprecision measures.
- The supplementary figures report imprecision of kₒ and related measures as functions of shell index.
- The shell-index analysis compares kₒ and kᵣ using normalized shell indices ranging from 0 to kSmax.The residual-network coreness is obtained after removing links of small weight.
S as a function of p for six real-world networks. ko
Across six real-world networks, kᵣ generally yields lower ranking imprecision than kₒ, and renewed coreness also enhances neighborhood-coreness ranking accuracy.
- Ranking imprecision based on kᵣ is obviously lower than that based on kₒ across the studied networks.
- kᵣ-based ranking imprecision is less than 0.1 for all p in the demonstrated range, with only small exceptions in Email and Hamster.The comparison uses p values from 0.001 to 0.05.
- Using kᵣ greatly enhances the ranking accuracy of neighborhood coreness Cnc.
- For Router, the original network’s 1−core contains all nodes, whereas residual-network processing creates nodes with kS = 0 during edge removal.
S as a function of p for three real-world networks with no core-like groups. ko
In three real-world networks without core-like groups, original and residual-network coreness show nearly identical imprecision and shell-level spreading-efficiency trends.
- The imprecision of kₒ and kᵣ is almost the same in all three networks.The comparison uses p from 0.001 to 0.05.
- The supplementary figure examines spreading efficiency of each shell as a function of d in networks without core-like groups.
- Spreading efficiency changes monotonically with shell distance in nearly the same way for kₒ and kᵣ.M is the average spreading efficiency of nodes in each shell, and d is shell distance from the innermost core.