×

Continuous-time independent edge-Markovian random graph process. (English) Zbl 1333.05270

Summary: In this paper, the continuous-time independent edge-Markovian random graph process model is constructed. The authors also define the interval isolated nodes of the random graph process, study the distribution sequence of the number of isolated nodes and the probability of having no isolated nodes when the initial distribution of the random graph process is stationary distribution, derive the lower limit of the probability in which two arbitrary nodes are connected and the random graph is also connected, and prove that the random graph is almost everywhere connected when the number of nodes is sufficiently large.

MSC:

05C80 Random graphs (graph-theoretic aspects)
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barabasi, A. L., Linked: The New Science of Networks, Persus Publishing, Massachusotts, 1979.
[2] Watts, D. J., The “new” science of networks, Annual Review of Sociology, 30, 2004, 243-270. · doi:10.1146/annurev.soc.30.020404.104342
[3] Jodan, J., The degree sequences and spectra of scale-free random graph, Random Structures and Algorithms, 29, 2006, 226-242. · Zbl 1108.05083 · doi:10.1002/rsa.20101
[4] An, L. and Liu, X. R., The stability analysis of random growing networks, Journal of Hebei University of Technology, 39, 2010, 17-19.
[5] Cao, Y., The degree distribution of random k-trees, Theoretical Computer Science, 410, 2009, 688-695. · Zbl 1175.68076 · doi:10.1016/j.tcs.2009.04.006
[6] Han, D., The stationary distribution of a continuous-time random graph process with interacting edges, Acta Math. Phy. Sinica, 14, 1994, 98-102.
[7] Avin, C.; Koucky, M.; Lotker, Z., How to explore a fast-changing world, 121-132 (2008), Berlin · Zbl 1152.68476 · doi:10.1007/978-3-540-70575-8_11
[8] Clementi, A. E. F.; Macci, C.; Monnti, M.; etal., Flooding time in edge-markovian dynamic graphs, 213-222 (2008), New York · Zbl 1301.05308
[9] Herv, B.; Pierluigi, C.; Pierre, F., Parsimonious flooding in dynamic graphs, 260-269 (2009), USA · Zbl 1291.68292
[10] Cai, Q. S. and Niu, J. W., Opportunity network time evolution graph model based on the edge independent evolution, Computer Engineering, 37(15), 2011, 17-22.
[11] Du, C. F., Markov chain model of the random network, Science Technology and Engineering, 10(30), 2010, 7380-7383.
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.