The infection time of graphs (Q858307): Difference between revisions
From MaRDI portal
Set profile property. |
Normalize DOI. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / DOI | |||
Property / DOI: 10.1016/j.dam.2006.04.026 / rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.dam.2006.04.026 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1974210749 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Eigenvalues and expanders / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Spreading rumors rapidly despite an adversary / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4436058 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distributed communication algorithms for ad hoc mobile networks. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Collisions Among Random Walks on a Graph / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5541610 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4265490 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4702188 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Attack propagation in networks / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Markov Chains / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: How to withstand mobile virus attacks (extended abstract) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast information sharing in a complete network / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4284630 / 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
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