Abstract:
Let AA be a finite set of vertices and λa>0λa>0 be the intensity of the vertex a∈Aa∈A. A random time-dependent graph GL(A∣t) is defined as follows: at time t=0 all the vertices are isolated; the probability that at time t>0 vertices a and b are connected equals 1−e−λaλbt, and the connections appear independently for different pairs, let PL(A∣t) be the probability that the random graph GL(A∣t) is connected.
In the paper, an explicit expression for PL(A∣t) is found, a number of combinatorial relations including the probabilities PL(A∣t) is obtained, and it is proved that if the set of vertices A, intensities of vertices λa, and time t are changed in a certain way, then, under some conditions, PL(A∣t)eμ(A∣t)→1, where
μ(A∣t)=∑a∈Aexp{−tλaL(A)}andL(A)=∑a∈Aλa.
Citation:
V. E. Stepanov, “Combinatorial algebra and random graphs”, Teor. Veroyatnost. i Primenen., 14:3 (1969), 393–420; Theory Probab. Appl., 14:3 (1969), 373–399
\Bibitem{Ste69}
\by V.~E.~Stepanov
\paper Combinatorial algebra and random graphs
\jour Teor. Veroyatnost. i Primenen.
\yr 1969
\vol 14
\issue 3
\pages 393--420
\mathnet{http://mi.mathnet.ru/tvp1195}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=263129}
\zmath{https://zbmath.org/?q=an:0239.05124}
\transl
\jour Theory Probab. Appl.
\yr 1969
\vol 14
\issue 3
\pages 373--399
\crossref{https://doi.org/10.1137/1114052}
Linking options:
https://www.mathnet.ru/eng/tvp1195
https://www.mathnet.ru/eng/tvp/v14/i3/p393
This publication is cited in the following 21 articles:
Nicola Galli, “Average Costs of a Graph Exploration: Upper and Lower Bounds”, Journal of Algorithms, 34:1 (2000), 148
David J. Aldous, Boris Pittel, “On a random graph with immigrating vertices: Emergence of the giant component”, Random Struct. Alg., 17:2 (2000), 79
Brian D. Jones, Boris G. Pittel, Joseph S. Verducci, “Tree and forest weights and their application to nonuniform random graphs”, Ann. Appl. Probab., 9:1 (1999)
Michael O. Ball, Charles J. Colbourn, J. Scott Provan, Handbooks in Operations Research and Management Science, 7, Network Models, 1995, 673
M. Lomonosov, “On Monte Carlo Estimates in Network Reliability”, Prob. Eng. Inf. Sci., 8:2 (1994), 245
Philippe Blanchard, Georg F. Bolz, Tyll Krüger, Lecture Notes in Physics, 355, Dynamics and Stochastic Processes Theory and Applications, 1990, 55
Lajos Takács, “A generalization of an inequality of Stepanov”, Journal of Combinatorial Theory, Series B, 48:2 (1990), 289
A. F. Ronzhyn, “Goodness-of-Fit Test for Generalized Urn Models Based on Divisible Statistics”, Theory Probab. Appl., 33:1 (1988), 86–95
A. D. Korshunov, “The main properties of random graphs with a large number of vertices and edges”, Russian Math. Surveys, 40:1 (1985), 121–198
Béla Bollobás, Andrew Thomason, North-Holland Mathematics Studies, 118, Random Graphs '83, Based on lectures presented at the 1st Poznań Seminar on Random Graphs, 1985, 47
W. Kordecki, “Some recurrence formulas for probability of connectednes of random graphs”, Theory Probab. Appl., 30:3 (1986), 630–632
Michał Karoński, “A review of random graphs”, Journal of Graph Theory, 6:4 (1982), 349
Donald E. Knuth, Arnold Schönhage, “The expected linearity of a simple equivalence algorithm”, Theoretical Computer Science, 6:3 (1978), 281
Ove Frank, “Survey sampling in graphs”, Journal of Statistical Planning and Inference, 1:3 (1977), 235
Yu. D. Burtin, “On extreme metric parameters of a random graph, I”, Theory Probab. Appl., 19:4 (1975), 710–725
I. N. Kovalenko, “Theory of random graphs”, Cybern Syst Anal, 7:4 (1974), 575
G. I. Ivchenko, “The Strength of Connectivity of a Random Graph”, Theory Probab. Appl., 18:2 (1973), 396–403
A. K. Kel'mans, “Asymptotic formulas for the probability of k-connectedness of random graphs”, Theory Probab. Appl., 17:2 (1973), 243–254
V. E. Stepanov, “Random mappings with one attracting center”, Theory Probab. Appl., 16:1 (1971), 155–162
V. E. Stepanov, “Phase transitions in random graphs”, Theory Probab. Appl., 15:2 (1970), 187–203