The infection time of graphs (Q858307): Difference between revisions

From MaRDI portal
ReferenceBot (talk | contribs)
Changed an Item
Normalize DOI.
 
Property / DOI
 
Property / DOI: 10.1016/j.dam.2006.04.026 / rank
Normal rank
 
Property / DOI
 
Property / DOI: 10.1016/J.DAM.2006.04.026 / rank
 
Normal rank

Latest revision as of 05:45, 10 December 2024

scientific article
Language Label Description Also known as
English
The infection time of graphs
scientific article

    Statements

    The infection time of graphs (English)
    0 references
    0 references
    0 references
    0 references
    9 January 2007
    0 references
    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.
    0 references
    random walk
    0 references
    Markov chain
    0 references
    infection time
    0 references
    interacting particle system
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references