Source-linked AI summary
Ranking spreaders by decomposing complex networks
An Zeng, Cheng-Jun Zhang
TL;DR
The paper asks how to rank all nodes by spreading ability when k-shell overlooks links to removed nodes. It proposes MDD, which combines residual and exhausted degree, and reports more accurate rankings than k-shell and degree methods in real-network epidemic simulations.
Problem
K-shell can give many nodes identical ranks and can mis-rank strongly spreadable nodes because it ignores links to removed nodes.
Method
MDD ranks nodes by repeatedly decomposing the network with a tunable mixed degree that considers residual and exhausted degree.
Results
MDD performs more accurately than k-shell and degree methods in ranking node spreadability on real networks.
Takeaways & Limitations
MDD provides more detailed node rankings and can separate influential nodes that k-shell assigns the same rank.
Abstract
from arXiv · showhide
Ranking the nodes' ability for spreading in networks is a fundamental problem which relates to many real applications such as information and disease control. In the previous literatures, a network decomposition procedure called k-shell method has been shown to effectively identify the most influential spreaders. In this paper, we find that the k-shell method have some limitations when it is used to rank all the nodes in the network. We also find that these limitations are due to considering only the links between the remaining nodes (residual degree) while entirely ignoring all the links connecting to the removed nodes (exhausted degree) when decomposing the networks. Accordingly, we propose a mixed degree decomposition (MDD) procedure in which both the residual degree and the exhausted degree are considered. By simulating the epidemic process on the real networks, we show that the MDD method can outperform the k-shell and the degree methods in ranking spreaders. Finally, the influence of the network structure on the performance of the MDD method is discussed.
I. INTRODUCTION
The paper examines how to rank individual nodes by spreadability, identifying limitations in k-shell ranking and proposing MDD to address them.
- Motivation: Node spreadability measures how many nodes are ultimately covered when spreading starts from that node.This information supports disease control, information dissemination, and identification of initial spreaders.
- Existing method: The k-shell method removes low-residual-degree nodes recursively, assigning nodes to shells based on their remaining connections.Residual degree counts links to remaining nodes, while exhausted degree counts links to removed nodes.
- Limitations: K-shell can assign identical ranks to nodes with very different spreading performance, including all nodes in some tree and Barabasi-Albert networks.It can also assign insufficiently high ranks to influential nodes in some network structures.
- Contribution: These limitations arise because k-shell ignores links connecting remaining nodes to removed nodes during decomposition.MDD therefore incorporates both residual and exhausted degree.
- Results: Epidemic simulations on real networks show that MDD ranks node spreadability more accurately than k-shell and degree methods.The paper also examines how real-network structure affects MDD performance.
II. METHOD
MDD ranks nodes using a tunable combination of residual and exhausted degree, repeatedly removing nodes according to their mixed degree. Its endpoints recover k-shell and degree centrality.
- Motivation: K-shell assumes nodes in the same layer connect homogeneously to removed nodes, which can mis-rank nodes attached to large removed branches.A low-layer node connected to a large tree-like branch may be more spreadable than nodes in higher layers.
- MDD procedure: MDD removes nodes according to a mixed degree that incorporates information about both remaining-node and removed-node connections.The method is designed to produce more accurate spreadability rankings.
- MDD procedure: The decomposition uses km = kr + λ ∗ ke, where λ is tunable between 0 and 1.Residual and exhausted degree are combined through the parameter λ.
- Procedure: At each iteration, nodes with the smallest mixed degree are removed, assigned to a shell, and the mixed degrees of remaining nodes are updated recursively.Nodes with updated mixed degree no greater than the current threshold are assigned to the same shell.
- Special cases: When λ = 0, MDD becomes k-shell; when λ = 1, it becomes degree centrality.For intermediate λ, MDD shell values may be decimal rather than integer.
- Illustration: Figure 1 illustrates MDD with removed nodes and exhausted links shown using dashed lines and λ = 0.7.The example visualizes the decomposition's treatment of exhausted links.
III. RESULT
Across real networks, MDD produces finer node rankings and higher agreement with SIR-based spreadability than k-shell and degree methods. Its improvement varies with network structure, while an optimal λ exists across social and nonsocial networks.
- Ranking resolution: MDD generates substantially more distinct ranks than k-shell and degree centrality, distinguishing node differences more finely.With λ = 0.7, the number of MDD ranks can be even ten times larger than the degree-based count.
- Evaluation: The study evaluates topology-based rankings against SIR spreadability using Kendall’s tau across infection rates p ∈ (0, 0.5].Results are averaged over 100 independent realizations for the plotted networks.
- Ranking accuracy: Across the considered infection rates, MDD outperforms both k-shell and degree centrality in Kendall’s tau.The comparison shown uses λ = 0.7.
- Parameter selection: Each network has an optimal λ* that maximizes the aggregate ⟨τ⟩, and this optimum occurs across both social and nonsocial networks.The aggregate ⟨τ⟩ sums τ over infection rates p from 0 to 0.5.
- Performance variation: MDD’s relative improvement in ⟨τ⟩ ranges from 5% to 60% across networks, with absolute τ improvement reaching 0.188 in some networks.The relative improvement is measured against k-shell performance.
- Network structure: MDD tends to improve more in networks with homogeneous degrees, negative assortativity, low clustering, and large average shortest-path length.The reported relationships include negative correlation with degree heterogeneity and greater effectiveness in large-diameter networks.
IV. CONCLUSION
The paper concludes that MDD addresses key limitations of k-shell ranking by incorporating exhausted links alongside residual links. It improves spreadability ranking, while remaining computationally non-optimal and sensitive to network structure.
- MDD incorporates exhausted links with residual links to address k-shell's failure to distinguish nodes and its occasional under-ranking of strong spreaders.
- MDD significantly improves spreadability-ranking accuracy and has an optimal λ for each network.
- The method's performance depends on network structure, which the paper investigates in detail.
- MDD is not optimal because path-based rankings may be more accurate, though they can have much higher computational complexity.
- More effective and efficient spreader-ranking methods remain an open direction for further investigation.