×

The infection time of graphs. (English) Zbl 1119.60079

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.

MSC:

60K35 Interacting random processes; statistical mechanics type models; percolation theory
60G50 Sums of independent random variables; random walks
60J25 Continuous-time Markov processes on general state spaces
60J27 Continuous-time Markov processes on discrete state spaces
82C22 Interacting particle systems in time-dependent statistical mechanics

Software:

LEDA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] D. Aldous, J. Fill, Reversible Markov chains and random walks on graphs, unpublished manuscript, \( \langle;\) http://stat-www.berkeley.edu/users/aldous/book.html \(\rangle;\); D. Aldous, J. Fill, Reversible Markov chains and random walks on graphs, unpublished manuscript, \( \langle;\) http://stat-www.berkeley.edu/users/aldous/book.html \(\rangle;\)
[2] Alon, N., Eigenvalues and expanders, Combinatorica, 6, 83-96 (1986) · Zbl 0661.05053
[3] J. Aspnes, W. Hurwood, Spreading rumors rapidly despite an adversary, in: Proceedings of the 15th ACM Symposium on Principles of Distributed Computing, PODC96, 1996.; J. Aspnes, W. Hurwood, Spreading rumors rapidly despite an adversary, in: Proceedings of the 15th ACM Symposium on Principles of Distributed Computing, PODC96, 1996. · Zbl 1321.68059
[4] Chatzigiannakis, I.; Nikoletseas, S., Design and analysis of an efficient communication strategy for hierarchical and highly changing ad-hoc mobile networks, ACM/Baltzer Mobile Networks J., Special Issue on Parallel Processing Issues in Mobile Computing, Guest Editors: A. Zomaya, M. Kumar, MONET, 9, 4, 319-332 (2004)
[5] I. Chatzigiannakis, S. Nikoletseas, P. Spirakis, An efficient communication strategy for ad-hoc mobile networks, in: Proceedings of the 15th International Symposium on Distributed Computing—DISC’01, Lecture Notes in Computer Science, vol. 2180, Springer, Berlin, 2001, pp. 285-299, Also Brief Announcement, in: Proceedings of the 20th Annual Symposium on Principles of Distributed Computing—PODC’01, ACM Press, New York, 2001, pp. 320-322.; I. Chatzigiannakis, S. Nikoletseas, P. Spirakis, An efficient communication strategy for ad-hoc mobile networks, in: Proceedings of the 15th International Symposium on Distributed Computing—DISC’01, Lecture Notes in Computer Science, vol. 2180, Springer, Berlin, 2001, pp. 285-299, Also Brief Announcement, in: Proceedings of the 20th Annual Symposium on Principles of Distributed Computing—PODC’01, ACM Press, New York, 2001, pp. 320-322. · Zbl 1024.68502
[6] Chatzigiannakis, I.; Nikoletseas, S.; Spirakis, P., Distributed communication and control algorithms for ad-hoc mobile networks, J. Parallel and Distributed Comput., Special Issue on Mobile Ad-hoc Networking and Computing, 63, 58-74 (2003) · Zbl 1048.68013
[7] Coppersmith, D.; Tetali, P.; Winkler, P., Collisions among random walks on a graph, SIAM J. Discrete Math., 6, 3, 363-374 (1993) · Zbl 0776.60083
[8] T. Dimitriou, S. Nikoletseas, P. Spirakis, Analysis of the information propagation time among mobile hosts, in: Proceedings of the Third International Conference on Ad Hoc Networks and Wireless Networks (ADHOC-NOW), Lecture Notes in Computer Science, Springer, Berlin, 2004, pp. 122-134.; T. Dimitriou, S. Nikoletseas, P. Spirakis, Analysis of the information propagation time among mobile hosts, in: Proceedings of the Third International Conference on Ad Hoc Networks and Wireless Networks (ADHOC-NOW), Lecture Notes in Computer Science, Springer, Berlin, 2004, pp. 122-134.
[9] S. Even, B. Monien, On the number of rounds needed to disseminate information, in: Proceedings of the 1st ACM Symposium on Parallel Algorithms and Architectures, SPAA89, 1989.; S. Even, B. Monien, On the number of rounds needed to disseminate information, in: Proceedings of the 1st ACM Symposium on Parallel Algorithms and Architectures, SPAA89, 1989.
[10] Feller, W., An Introduction to Probability Theory and its Applications (1957), Wiley: Wiley New York · Zbl 0158.34902
[11] M.R. Jerrum, A. Sinclair, Conductance and the rapid mixing property of Markov chains: the approximation of the permanent resolved, in: Proceedings of the 20th ACM Symposium on Theory of Computing (STOC), 1988, pp. 235-244.; M.R. Jerrum, A. Sinclair, Conductance and the rapid mixing property of Markov chains: the approximation of the permanent resolved, in: Proceedings of the 20th ACM Symposium on Theory of Computing (STOC), 1988, pp. 235-244.
[12] J. Kephard, S. White, Directed-graph epidemiological models of computer viruses, in: Proceedings of the IEEE Symposium on Security and Privacy, 1991, Also IBM Technical Report.; J. Kephard, S. White, Directed-graph epidemiological models of computer viruses, in: Proceedings of the IEEE Symposium on Security and Privacy, 1991, Also IBM Technical Report.
[13] Liggett, T., Stochastic Interacting Systems: Contact, Voter and Exclusion Processes (1999), Springer: Springer Berlin · Zbl 0949.60006
[14] Mehlhorn, K.; Naher, S., LEDA: A Platform for Combinatorial and Geometric Computing (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0976.68156
[15] S. Nikoletseas, G. Prasinos, P. Spirakis, C. Zaroliagis, Attack propagation in networks, in: Theory Comput. Systems J., Special Issue on the Thirteenth (13th) Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2001), 36, 2003, pp. 553-574.; S. Nikoletseas, G. Prasinos, P. Spirakis, C. Zaroliagis, Attack propagation in networks, in: Theory Comput. Systems J., Special Issue on the Thirteenth (13th) Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA 2001), 36, 2003, pp. 553-574. · Zbl 1101.68346
[16] Norris, J. R., Markov Chains (1997), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0873.60043
[17] R. Ostrofsky, M. Yung, How to withstand mobile virus attacks, in: Proceedings of the 10th ACM Symposium on Principles of Distributed Computing—PODC91, 1991, p. 51-59.; R. Ostrofsky, M. Yung, How to withstand mobile virus attacks, in: Proceedings of the 10th ACM Symposium on Principles of Distributed Computing—PODC91, 1991, p. 51-59. · Zbl 1314.68132
[18] Sunderam, V. S.; Winkler, P., Disc. Appl. Math., 42, 75-86 (1993)
[19] Tetali, P.; Winkler, P., Simultaneous reversible Markov chains, (Miklos, D.; Sos, V. T.; Szonyi, T., Combinatorics, Paul Erd os is Eighty, vol. 1 (1993), Janos Bolyai Mathematics Institute: Janos Bolyai Mathematics Institute Budapest), 433-452 · Zbl 0791.60055
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.