Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-15T09:11:16.462Z Has data issue: false hasContentIssue false
  • English
  • Français

Epidemic processes on digraphs of random mappings

Part of:Graph theoryCombinatorics

Published online by Cambridge University Press:  14 July 2016

Jerzy Jaworski
Jerzy Jaworski*
Affiliation:
Adam Mickiewicz University
*
∗ Postal address: Department of Discrete Mathematics, Adam Mickiewicz University, Matejki 48/49, 60–769 Poznań, Poland. Email address: jaworski@main.amu.edu.pl
Get accessRights & Permissions [Opens in a new window]

Abstract

A random mapping (T n ;q) of a finite set V, V = {1,2,…,n}, into itself assigns independently to each i ∊ V its unique image j ∊ V with probability q if i = j and with probability P = (1-q)/(n−1) if i ≠ j. Three versions of epidemic processes on a random digraph G T representing (T n ;q) are studied. The exact probability distributions of the total number of infected elements as well as the threshold functions for these epidemic processes are determined.

Keywords

Random mappingsepidemic processesthreshold functionsAbel sumsgeneralized Stirling numbers

MSC classification

Primary:05C80: Random graphs05A19: Combinatorial identities, bijective combinatorics

Information

Type
Research Papers
Information
Journal of Applied Probability , Volume 36 , Issue 3 , September 1999, pp. 780 - 798
Copyright
Copyright © Applied Probability Trust 1999 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Barton, D. E., and David, F. N. (1962). Combinatorial Chance. Charles Griffin, London.Google Scholar
Berg, S. (1981). On snowball sampling, random mappings and related problems. J. Appl. Prob. 18, 283–290.Google Scholar
Berg, S. (1983). Random contact processes, snowball sampling and factorial series distributions. J. Appl. Prob. 20, 31–46.Google Scholar
Berg, S., and Jaworski, J. (1992). Probability distributions related to the local structure of a random mapping. In Random Graphs'89. Wiley, New York, pp. 1–21.Google Scholar
Berg, S., and Mutafchiev, L. (1990). Random mappings with an attracting center: Lagrangian distributions and a regression function. J. Appl. Prob. 27, 622–636.Google Scholar
Bollobás, B. (1985). Random Graphs. Academic Press, London.Google Scholar
Burtin, Y. D. (1980). On a simple formula for random mappings and its applications. J. Appl. Prob. 17, 403–414.Google Scholar
Frank, H., and Frisch, I. (1971). Communication, Transmission and Transportation Networks. Addison-Wesley, Reading, MA.Google Scholar
Gertsbakh, I. B. (1977). Epidemic process on a random graph: some preliminary results. J. Appl. Prob. 14, 427–438.Google Scholar
Harris, B. (1960). Probability distributions related to random mappings. Ann. Math. Statist. 31, 1045–1062.Google Scholar
Ivchenko, G. I. and Medvedev, Yu. I. (1965). Asymptotic representations of finite differences of a power function at an arbitrary point. Theory Prob. Appl. 10, 139–144.Google Scholar
Jaworski, J. (1985). Random mappings. Unpublished Dissertation, Adam Mickiewicz University, Poznań (in Polish).Google Scholar
Jaworski, J. (1986). Epidemic processes on graphs of random mappings. Graph Theory Notes of New York 11, 19–21.Google Scholar
Jaworski, J. (1990). Random mappings with independent choices of images. In Random Graphs'87. Wiley, New York, pp. 89–101.Google Scholar
Katz, L. (1955). Probability of indecomposability of a random mapping function. Ann. Math. Statist. 26, 512–517.Google Scholar
Koutras, M. (1982). Non-central Stirling numbers and some applications. Discrete Math. 42, 73–89.Google Scholar
Mutafchiev, L. (1981). Epidemic processes on random graphs and their threshold function. Serdica 7, 153–159.Google Scholar
Mutafchiev, L. (1982). A limit distribution related to random mappings and its application to an epidemic process. Serdica 8, 197–203.Google Scholar
Pittel, B. (1983). On distributions related to transitive closures of random finite mappings. Ann. Prob. 11, 428–441.Google Scholar
Riordan, J. (1968). Combinatorial Identities. Wiley, New York.Google Scholar