The infection time of graphs
type: Item
instance of: scholarly article
title: The infection time of graphs
zbMATH Open document ID: 1119.60079
author: Tassos Dimitriou
author: Sotiris E. Nikoletseas
author: P. G. Spirakis
published in: Discrete Applied Mathematics
publication date: 2007-01-09T00:00:00Z
review text: Consider a graph with \(n\) vertices and \(k\leq n\) particles performing \(k\) independent random walks on the graph. Initially, one particle is red and all the others are white, and each vertex of the graph has at most one particle. When a red particle meets one or more white particle(s) then the white one(s) turn(s) red. This is an infection rule and is a model for several real life phenomena, like the spread of a virus in a computer networks, information spreading (rumor, gossip) and mobile communication. For an initial distribution \(\varphi_k\) of the particles, let \(T_{\varphi_k}\) be the first time at which all particles are red. The infection time \(T_k\) is the worst expected value \(E(T_{\varphi_k}| \varphi_k)\) over all distributions \(\varphi_k\) such that each particle is assigned to a single vertex with probability 1. The authors study the infection time for various families of unweighted, undirected finite graphs. First of all, they prove the following upper bound (valid for all graphs): \(T_k\leq em^*(2+\log k)\), where \(m^*=\max_{i,j}M_{i,j}\), and \(M_{i,j}\) is the first time that two independent random walks on the graph meet if they start from positions \(i\) and \(j\) (that is, \(m^*\) is the expected meeting time). They also show that this bound is tight for a family of lollipop graphs. Then they give more tight bounds for two special classes of graphs: cliques and expander graphs. In the last part of the paper, the authors discuss several computer simulations that, in particular, show that their results for expander graphs are tight. A final conjecture is that good expanders have small infection time. Future work in this direction might lead to a characterization of expansion through infection time.
reviewed by: Fabio Scarabotti
Mathematics Subject Classification ID: 60K35
Mathematics Subject Classification ID: 60G50
Mathematics Subject Classification ID: 60J25
Mathematics Subject Classification ID: 60J27
Mathematics Subject Classification ID: 82C22
zbMATH DE Number: 5082761
zbMATH Keywords: random walk
zbMATH Keywords: Markov chain
zbMATH Keywords: infection time
zbMATH Keywords: interacting particle system
describes a project that uses: LEDA
MaRDI profile type: Publication
full work available at URL: j.dam.2006.04.026
OpenAlex ID: W1974210749
cites work: Eigenvalues and expanders
cites work: Spreading rumors rapidly despite an adversary
cites work: Q4436058
cites work: Distributed communication algorithms for ad hoc mobile networks.
cites work: Collisions Among Random Walks on a Graph
cites work: Q5541610
cites work: Q4265490
cites work: Q4702188
cites work: Attack propagation in networks
cites work: Markov Chains
cites work: How to withstand mobile virus attacks (extended abstract)
cites work: Fast information sharing in a complete network
cites work: Q4284630
DOI: 10.1016/J.DAM.2006.04.026
Recommended article: Q5235962
Recommended article: Infection in hypergraphs
Recommended article: Infection Spread in Random Geometric Graphs
Recommended article: Spread of Infection over P.A. random graphs with edge insertion
Recommended article: The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree
Recommended article: Susceptible-infected epidemics on evolving graphs
Recommended article: On an epidemic model on finite graphs
Recommended article: Exact computation for meeting times and infection times of random walks on graphs
Recommended article: Dynamics of epidemic spreading on connected graphs
description: scientific article; zbMATH DE number 5082761