Event details from: General Mathematics Colloquium

Date
7 June 2022
Time
16:00 – 16:45

Title

A randomized k-centrality measure & applications to networks node immunization

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.

Location

Science Park 107, Room F3.20, or hybrid