We are interested in the so-called multiple-node immunization for complex networks under attack of a viral agent. The latter is a hot topic in network science and it consists of identifying and removing a set of nodes of a given size in a graph to maximally impede the agent spread. Several approaches have been proposed in the literature based on numerical and theoretical insights on how classical models for virus spread (so-called compartmental models) evolve on graphs.
Based on the stability analysis of these compartmental models, the maximal eigenvalue of the adjacency matrix of the graph has been proposed as a measure for how resilient the network is. Thus one of the most common approaches for immunization consists in identifying the set of nodes of a given cardinality, for which the reduced network, obtained by removing these nodes, has minimal largest eigenvalue. This optimization problem turns out to be a computationally hard problem in the well known NP class and the available exact or proxy algorithms offer good solutions and performances only for small data sets.
We propose a novel randomized flexible method to efficiently identify these sets of nodes based on random walk kernels and random rooted forests. We explain the theoretical results underlying the method, and present experimental results where we test method and performances on classical synthetic and real-world benchmarks.
Joint work with Michael Emmerich, Alex Gaudilliere and Irina Gurewitsch