LRIE: A greedy approach to dynamic control against epidemics in networks

Introduction

This document provides additional material for the research paper with the title “A Greedy Approach for Dynamic Control of Diffusion Processes in Networks“, co-authored by Kevin Scaman, Argyris Kalogeratos, and Nicolas Vayatis, and published in ICTAI 2015 [1]. It also presents the software release of the DRA simulator (shortcut to download section).

The paper proposes the Largest Reduction of Infectious Edges (LRIE) strategy for the Dynamic Resource Allocation (DRA) in a network for suppressing an SIS diffusion process (e.g. the epidemic of a virus). A preliminary version of this work, mostly focused on the empirical analysis of the LRIE, was presented in [3].

Practical application domains for DRA strategies could be the control of any type of social interaction that can be modeled with SIS, for which there exist resources that -if provided- can accelerate the recovery of an infected agent/person. Thus, we may mention as more specific example domains the epidemiology, the social behavioral and information networks (electronic or contact network) where one may want to suppress/contain the spread of a virus, or some information/behavioral diffusion among the members of a network.

In the rest of this page you can find:

Demonstration videos about the SIS diffusion processes taking place in an artificial contact network, also comparing LRIE strategy against some of the other methods discussed in [1] for suppressing such an epidemic.
The supplementary technical material referred to by [1].
A release of the DRA simulator, the software developed in MATLAB R2014b by Argyris Kalogeratos and Kevin Scaman for that research work.

1. Description

The intuition behind LRIE criterion, and the respective strategy which was also shown in [1] to be theoretically optimal in a greedy setting, is that the healing resources should be spent on nodes that highly diffusive (i.e. threaten as many healthy one-hop neighbors as possible, while at the same time being as safe as possible in the sense that, once recovered, their reinfection from their infected neighbors is little probable (i.e. they have as few infected neighbors as possible).

This idea is better conceptualized by realizing that the infectious edges are those edges on which the epidemic can spread by infecting new nodes, as they connect infected and healthy nodes. In this spirit, the proposed strategy called Largest Reduction in Infectious Edges (LRIE), does exactly what it states: it distributes the healing resources to the nodes whose recovery would lead to the largest reduction of edges and, hence, reduces the threat of infection spread.

Fig. 1 comes from [1] and shows the infection state of a small network. Node h is the most connected, d has the highest diffusion rate (three healthy neighbors), e and h are the least and most probable to get reinfected if they recover. Scores that would give emphasis to properties like node centrality or degree, would tend to assign the highest priority to node h, while a strategy focusing on the most diffusive nodes would prefer to give a higher priority to node d. LRIE would evaluate both d and e as nodes of equal treatment priority.

Toy example
Fig. 1: Example network with healthy (white) and infected (red) nodes. Dashed edges denote infectious edges on which the disease might spread.

2. Demonstration videos

A video playlist is provided below that contains three demos that visualize continuous-time SIS diffusion processes starting from a single node on an artificial contact network. The purpose is to show indicative one-vs-one comparisons of the evolution of SIS diffusion under the effect of different dynamic treatment allocation strategies that distribute the available healing resources to the network nodes in order to help them for a quicker recovery.

The demonstrated diffusion instances are:

(a) SIS without control with treatment allocation.
(b) SIS under the effect of Most Neighbors (MN, left) and Largest Reduction in Infectious Edges (LRIE, right) strategies.
(c) SIS under Largest Reduction of Spectral Radius (LRSR, left) and Largest Reduction in Infectious Edges (LRIE, right) strategies.

Notation: Healthy nodes are in white color, infected nodes are in black, and red color denotes the infected nodes that receive the treatment resources. Each video shows the state of the network at regular time intervals in which more than one changes may have happened in the network nodes.

The contact network: The structure is artificially generated as a spatial network. First, random points are uniformly created in a square [0,1]-surface, and then, assuming a fixed node degree for all nodes, each node ‘chooses’ its connecting neighbors with a probability proportional to its respective pairwise distance. Therefore, long edges are less probable than short ones.

3. Simulation software

The DRA simulator software that is made available here was developed by Argyris Kalogeratos and Kevin Scaman to perform part of their simulation experiments for [1]. The software is written in MATLAB R2014b and is maintained in a git repository. Contact the authors of the package at the emails: {kalogeratos [/or\] scaman} [/at\] cmla [/dot\] ens-cachan [/dot\] fr.

Visit the git repository Download the latest version (.zip)

Project contents:

./Datasets/*

a folder for the dataset files.

./EvalMetric/*

functions that compute the evaluation metrics used to asses the quality of the compared control strategies.

./GraphModels/*

functions that generate random networks.

./InfectionSeeds/*

functions that initialize the infection in a network.

./Strategies/*

functions that implement the various node ranking criteria that are used to decide for the resource treatment allocation.

./Var/*

various helper functions

./Visualization/*

helper functions related with the visualization of the simulation results.

In the root of the project there is the file DRAsimulator.m which is the main script to run. This is responsible to run all the experimental pipeline: environment initialization, experimental setup, run a set of experiments, illustrate comparative results. Some settings can be changed by editing the prepareWorkspace.m.

3.1. Dependencies and third-party components

The package depends on the following Matlab Toolboxes: Curve Fitting, Image Processing, Parallel Computing, Matlab Distributed Computing Server (the last two only needed in the case where the simulations are run in parallel).

Very few simple utility functions come from other open-source releases. We redistribute them with respect to the terms their distribution licenses.

Apart from the random network generators, the package redistributes the USAir97 network dataset. It is a directed air traffic network with the connections between 332 US cities from the year 1997 (source).

3.2. Installation and testing

No special installation is required. Place the files to a folder and open the main script DRAsimulator.m. Some initialization settings can be changed by editing the script prepareWorkspace.m.

5. How to cite this work

You may directly cite the paper in [1] using the following bibtex file. You may also cite this specific wep-page by its url as the source of the additional material related to that work.

6. License

Copyright (C) 2015, Argyris Kalogeratos and Kevin Scaman. The Material and Software Release for SIS Epidemic Simulation v.0.1 are free to use. Specifically for the software and the demo videos, you can redistribute them and/or modify them under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

All included material is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this software in the file LICENSE.txt. If not, see here.

Brief overview of the GNU GPL:

Provides copyright protection: True
Can be used in commercial applications: True
Bug fixes / extensions must be released to the public domain: True
Provides an explicit patent license: False
Can be used in proprietary (closed source) applications: False
Is a viral license: True

Other resources for the license:

7. Thanks

We want to thank Prof. Nicolas Vayatis for his useful comments and support in the development of this package. Moreover, the authors of the software should also thank those previously contributed to any of the third-party components that were used and are redistributed by this package.

References

[1] A Greedy Approach for Dynamic Control of Diffusion Processes in Networks, Kevin Scaman, Argyris Kalogeratos, and Nicolas Vayatis, IEEE International Conference on Tools with Artificial Intelligence, pp. xx-xx, 2015 [pdf][bib].

[2] Supplementary material with technical proofs (for the above paper), Kevin Scaman, Argyris Kalogeratos, and Nicolas Vayatis, 2015 [supplementary material].

[3] Dynamic Treatment Allocation for Epidemic Control in Arbitrary Networks, Kevin Scaman, Argyris Kalogeratos, and Nicolas Vayatis, In WSDM 2014 Diffusion in Networks and Cascade Analytics (DiffNet) Workshop, February 2014 [workshop link][pdf][slides][poster][bib].