Luca Avena (LEI) – A randomized k-centrality measure & applications to networks node immunization

Tuesday, the 6^th of December, 15:45 – 16:45, MetaForum MF11/12

ABSTRACT:

Have you ever thought how you can “immunize” a network from an attack of a viral agent? This is a hot topic in network science and it consists in identifying and removing a set of nodes of a given size in a graph to maximally impede the virus spread. Based on the stability analysis of so-called compartmental models (classical simple models for contagion which will be briefly recalled and discussed), the maximal eigenvalue of the adjacency matrix of the graph has been proposed as a measure for how much 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 and their incident edges) has smallest maximal eigenvalue.

The question is, how can we efficiently identify such a set of nodes?

We present a new flexible algorithm based on random walks which may also have applications in other network optimization problems.

Joint work with Michael Emmerich, Alex Gaudilliere and Irina Gurewitsch.