pith. sign in

arxiv: 2606.04131 · v1 · pith:JKXVJQ6Nnew · submitted 2026-06-02 · 💻 cs.SI · math.PR

Network node immunization: improving Netshield algorithm through random rooted forests

Luca Avena , Alexandre Gaudilli\`ere , Irina Gurewitsch , Ador\'e Randriamandroso , Alessio Troiani This is my paper

Pith reviewed 2026-06-28 07:44 UTC · model grok-4.3

classification 💻 cs.SI math.PR
keywords node immunizationNetshieldK-shieldrandom spanning forestsrandom walk kernelsspectral radiussubmodular optimization
0
0 comments X

The pith

K-shield uses random rooted forests to improve Netshield's selection of nodes for minimizing a network's largest eigenvalue.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper seeks a better solution to the multiple-node immunization problem: select and remove k nodes from a graph so that the largest eigenvalue of the remaining adjacency matrix is as small as possible. It does this by introducing the K-shield algorithm, which draws on random walk kernels and the random spanning forests they induce to optimize the existing shield-value functional more effectively than the reference Netshield procedure. The new method keeps the same computational complexity. A reader would care because improved node choices could more reliably slow the spread of a virus modeled on the graph.

Core claim

By constructing a procedure from random walk kernels and the associated random rooted forests, the K-shield algorithm achieves a more effective optimization of the shield-value than Netshield while retaining identical computational cost, thereby producing node sets whose removal yields smaller largest eigenvalues on the reduced graphs.

What carries the argument

Random rooted forests generated from random walk kernels, which supply a new search procedure for optimizing the submodular shield-value functional.

If this is right

  • K-shield returns node sets whose removal reduces the largest eigenvalue more than the sets returned by Netshield.
  • The computational cost remains the same as that of Netshield.
  • The random-forest construction supplies theoretical justification that may apply to other submodular optimization tasks on graphs.
  • Numerical tests on benchmark networks confirm the performance gain.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same forest-based construction could be substituted into other greedy algorithms that rely on similar submodular proxies.
  • Direct comparison of the actual eigenvalues after removal on large real-world networks would give a practical test of the method.
  • The approach may link to existing matrix-forest theorems and thereby suggest extensions to weighted or directed graphs.

Load-bearing premise

That improvements in optimizing the shield-value functional translate into actual reductions in the largest eigenvalue of the graph after the chosen nodes are removed.

What would settle it

On a concrete graph, run both algorithms to select their k-node sets, delete those nodes, compute the largest eigenvalue of each reduced adjacency matrix, and check whether the K-shield set consistently produces the smaller value.

read the original abstract

We are interested in the so-called multiple-node immunization problem for complex networks under attack by a viral agent. It consists in identifying and removing a set of nodes of size $k$ in a graph to maximize the impeding of virus spread. A few approaches have been proposed in the literature based on numerical and theoretical insights on how classical models for virus spread evolve on graphs. Based on the analysis of these models, the maximal eigenvalue of the adjacency matrix of the graph has become a classical measure of how resilient the network is. Thus, a clear, well-explored approach for multiple-node immunization consists of identifying a set of $k$ nodes in such a way that the reduced network, obtained by removing these nodes, has a minimal largest eigenvalue. This spectral optimization problem turns out to be a computationally hard problem for which only greedy algorithms offer good solutions at efficient computational time. Among those, the so-called Netshield algorithm represents one of the reference choices. The latter is, in fact, a clearly defined algorithm aiming at optimizing a certain sub-modular functional, called shield-value, which approximates the original optimization problem. We propose here a novel procedure, based on random walk kernels and related random spanning forests, to build a new algorithm, referred to as K-shield, which enhances Netshield searching performance at the same computational complexity. We give theoretical insights behind this novel method, which could also be used for other optimization problems, and then test it via numerical showcase experiments on various benchmarks.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes K-shield, a new procedure based on random walk kernels and random rooted forests, to improve the search for high shield-value node sets in the multiple-node immunization problem relative to the existing Netshield algorithm, while preserving the same computational complexity. Theoretical justification is supplied for the construction, and numerical experiments on benchmarks are used to illustrate the performance gain.

Significance. If the reported gains on the shield-value surrogate are reproducible and translate to the underlying spectral objective, the work supplies a practical, same-complexity enhancement to a standard greedy baseline for network immunization. The explicit link to random spanning forests is a methodological strength that could extend to other submodular graph optimization tasks.

major comments (2)
  1. [Abstract] Abstract: the central claim that K-shield 'enhances Netshield searching performance' is asserted without any quantitative metrics, tables, or error bars; the load-bearing performance comparison therefore cannot be evaluated from the given material.
  2. [Experiments section] Experiments (presumed §4–5): because the shield-value is only a surrogate for the true objective (minimizing the largest eigenvalue after removal), the manuscript must report the effect of the selected sets on the actual spectral radius, not solely on the surrogate value; otherwise the immunization claim remains unverified.
minor comments (2)
  1. [Theoretical development] Clarify the precise definition of the random-walk kernel and its relation to the rooted-forest sampling procedure in the theoretical section.
  2. [Complexity analysis] Add a short complexity table comparing Netshield and K-shield operation counts on the benchmark graphs.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. We address the two major comments below. Both points identify areas where the manuscript can be strengthened with additional quantitative detail, and we will incorporate the suggested changes in the revised version.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that K-shield 'enhances Netshield searching performance' is asserted without any quantitative metrics, tables, or error bars; the load-bearing performance comparison therefore cannot be evaluated from the given material.

    Authors: We agree that the abstract, as a standalone summary, should convey the magnitude of the reported improvement rather than a purely qualitative statement. In the revision we will add a concise quantitative statement (e.g., “K-shield yields an average X% higher shield-value than Netshield across the tested benchmarks while retaining the same O(nk) complexity”) drawn from the experimental results already present in §4–5. This will allow readers to evaluate the central claim without consulting the full text. revision: yes

  2. Referee: [Experiments section] Experiments (presumed §4–5): because the shield-value is only a surrogate for the true objective (minimizing the largest eigenvalue after removal), the manuscript must report the effect of the selected sets on the actual spectral radius, not solely on the surrogate value; otherwise the immunization claim remains unverified.

    Authors: The referee is correct that shield-value is an approximation; therefore the ultimate validation of the immunization procedure requires direct measurement of the spectral radius of the residual graph. We will augment the experimental section with a table (or additional panels) that reports, for each benchmark and each k, the largest eigenvalue λ₁ after removal of the k nodes returned by K-shield versus Netshield. This will explicitly demonstrate that the observed gains in shield-value translate to the true objective. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper introduces K-shield as a new search procedure for the pre-existing shield-value functional (itself a submodular surrogate for spectral immunization from prior literature) by leveraging standard random-walk kernels and random spanning forests. No derivation step equates a claimed prediction or result to its own inputs by construction, no fitted parameter is relabeled as a prediction, and no load-bearing premise reduces to a self-citation chain or imported uniqueness theorem. The central claim is an algorithmic improvement at fixed complexity whose validity is asserted via external benchmarks rather than internal self-reference.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The approach rests on the classical identification of spectral radius with network vulnerability and on the submodularity of the shield-value proxy; both are imported from prior literature rather than derived here.

axioms (2)
  • domain assumption The largest eigenvalue of the adjacency matrix is a classical and reliable scalar measure of network resilience under viral attack.
    Explicitly invoked in the abstract as the quantity whose reduction is the optimization target.
  • domain assumption The shield-value is a submodular functional whose maximization yields a good approximation to the original spectral immunization problem.
    Stated as the basis for the greedy Netshield algorithm that K-shield aims to improve.

pith-pipeline@v0.9.1-grok · 5816 in / 1345 out tokens · 18480 ms · 2026-06-28T07:44:59.297571+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

32 extracted references · 1 canonical work pages

  1. [1]

    Avena, F

    L. Avena, F. Castell, A. Gaudillière, and C. Mélot. Random forests and networks analysis. Journal of Statistical Physics, 173(3-4):985–1027, 2018. Node immunization through random rooted forests 21

    2018

  2. [2]

    Avena, F

    L. Avena, F. Castell, A. Gaudillière, and C. Mélot. Intertwining wavelets or multiresolution analysis on graphs through random forests.Applied and Computational Harmonic Analysis, 48(3):949–992, 2020

    2020

  3. [3]

    Avena and A

    L. Avena and A. Gaudillière. Two applications of random spanning forests.Journal of Theoretical Probability, 31(4):1975–2004, 2018

    1975

  4. [4]

    D. B. Barlow. Loop erased walks and uniform spanning trees.MSJ Memoirs, 34:1–32, 2016

    2016

  5. [5]

    Barrat, M

    A. Barrat, M. Barthlemy, and A. Vespignani.Dynamical Processes on Complex Networks. Cambridge University Press, New York, NY, USA, 2008

    2008

  6. [6]

    Barthelmé, F

    S. Barthelmé, F. Castell, A. Gaudillière, C. Melot, M. Quattropani, and N. Tremblay. Esti- mating a graph’s spectrum via random kirchhoff forests.arXiv preprint arXiv:2503.24236, 2025

    work page arXiv 2025

  7. [7]

    Chakrabarti, Y

    D. Chakrabarti, Y. Wang, C. Wang, J. Leskovec, and C. Faloutsos. Epidemic thresholds in real networks.ACM Transact. on Information and System Security (TISSEC), 10, 2008

    2008

  8. [8]

    C. Chen, H. Tong, B. A. Prakash, C. E. Tsourakakis, T. Eliassi-Rad, T. Faloutsos, and D. H. Chau. Node immunization on large graphs: Theory and algorithms.IEEE Transact. on Knowledge and Data Engineering, 28:113–126, 2016

    2016

  9. [9]

    Y. Chen, G. Paul, S. Havlin, F. Liljeros, and H. E. Stanley. Finding a better immunization strategy.PHYSICAL REVIEW LETTERS, 101, 2008

    2008

  10. [10]

    Colizza, R

    V. Colizza, R. Pastor-Satorras, and A. Vespignani. Reaction–diffusion processes and metapopulation models in heterogeneous networks.Nature Physics, 3(4):276–282, 2007

    2007

  11. [11]

    Draief and L

    M. Draief and L. Massoulié.Epidemics and Rumours in Complex Networks. Cambridge University Press, New York, NY, USA, 2010

    2010

  12. [12]

    Hoogervorst, E

    R. Hoogervorst, E. van der Hurk, and D. Pisinger. Simulation-optimization approaches for the network immunization problem with quarantining.European Journal of Operational Research, 2026

    2026

  13. [13]

    Y. Huang. Multi-relational network layer node immunization strategy based on multi- particle random walk.5th International Conference on Big Data & Artificial Intelligence & Software Engineering (ICBASE), Wenzhou, China, pages 217–220, 2024

    2024

  14. [14]

    Isella, J

    L. Isella, J. Stehlé, A. Barrat, C. Cattuto, J. Pinton, and W. Van den Broeck. What’s in a crowd? analysis of face-to-face behavioral networks.Journal of Theoretical Biology, 271(1):166–180, 2011

    2011

  15. [15]

    Kirchhoff

    G. Kirchhoff. über di auflösung der gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer ströme geführt wird.Ann. Phys. Chem., 72:497–508, 1847

  16. [16]

    I. Z. Kiss, J. C. Miller, and P. L. Simon.Mathematics of Epidemics on Networks. Springer, 2017

    2017

  17. [17]

    Krause and D

    A. Krause and D. Golovin.Submodular Function Maximization, page 71–104. Cambridge University Press, 2014

    2014

  18. [18]

    L Pellis, L

    F. L Pellis, L. amd Ball, K. Bansal, T. Eames, T. House, V. Isham, and P. Trapman. Eight challenges for network epidemic models.Epidemics, 10:58–62, 2010

    2010

  19. [19]

    T. M. Liggett.Interacting particle systems, volume 2. Springer, 1985. Node immunization through random rooted forests 22

    1985

  20. [20]

    L. Ma, C. Ma, H. Zhang, and B. Wang. Identifying influential spreaders in complex networks based on gravity formula.Physica a-Statistical Mechanics and Its Applications, 451:205–212, 2016

    2016

  21. [21]

    P. Marchal. Loop-erased random walks, spanning trees and hamiltonian cycles.Electron. Commun. Probab., 5:39–50, 2000

    2000

  22. [22]

    Maulana, M

    A. Maulana, M. Kefalas, and M. Emmerich. Immunization of networks using genetic al- gorithms and multiobjective metaheuristics.IEEE Symposium Series on Computational Intelligence (SSCI), page 1–8, 2017

    2017

  23. [23]

    Nepusz, A

    T. Nepusz, A. Petróczi, L. Négyessy, and F. Bazsó. Fuzzy communities and the concept of bridgeness in complex networks.Physical Review E, 77(1):016107, Jan. 2008

    2008

  24. [24]

    Opsahl, F

    T. Opsahl, F. Agneessens, and J. Skvoretz. Node centrality in weighted networks: General- izing degree and shortest paths.Social networks, 32(3):245–251, 2010

    2010

  25. [25]

    Pastor-Satorras, C

    R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespignani. Epidemic processes in complex networks.REVIEWS OF MODERN PHYSICS, 87, 2015

    2015

  26. [26]

    Torres, K

    L. Torres, K. S. Chan, H. Tong, and T. Eliassi-Rad. Nonbacktracking eigenvalues under node removal: X-centrality and targeted immunization.SIAM J. MATH. DATA SCI, 3:656–675, 2021

    2021

  27. [27]

    Tremblay, S

    N. Tremblay, S. Barthelmé, K. Usevich, and P.-O. Amblard. Extended l-ensembles: a new representation for determinantal point processes.The Annals of Applied Probability, 33:613–640, 2023

    2023

  28. [28]

    Van Mieghem, K

    P. Van Mieghem, K. Devriendt, and H. Cetinay. Pseudoinverse of the laplacian and best spreader node in a network.PHYSICAL REVIEW E, 96, 2017

    2017

  29. [29]

    Vanhems, A

    P. Vanhems, A. Barrat, C. Cattuto, J.-F. Pinton, N. Khanafer, C. Régis, B.-a. Kim, B. Comte, and N. Voirin. Estimating potential infection transmission routes in hospital wards using wearable proximity sensors.PloS one, 8(9):e73970, 2013

    2013

  30. [30]

    Onlowerboundsforthelargesteigenvalueofasymmetric matrix.Linear Algebra and its Applications, 429:519–526, 2008

    S.G.WalkerandP.VanMieghem. Onlowerboundsforthelargesteigenvalueofasymmetric matrix.Linear Algebra and its Applications, 429:519–526, 2008

    2008

  31. [31]

    D. B. Wilson. Generating random spanning trees more quickly than the cover time.Pro- ceedings of the Twenty-eighth Annual ACM Symposium on the Theory of Computing, pages 296–303, 1996

    1996

  32. [32]

    conference 1

    W. W. Zachary. An information flow model for conflict and fission in small groups.Journal of anthropological research, 33(4):452–473, 1977. A Graphs details The benchmark graphs considered in the paper that have been used to test the K-shield algorithm are described below: karate: Zachary’s karate club graph with 34 nodes and 77 unoriented edges introduce...

    1977