Continuous-time independent edge-Markovian random graph process

Abstract

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.

Keywords

Complex networks / Random graph / Random graph process / Stationary distribution / Independent edge-Markovian random graph process

References

[1] Barabasi A. L.. Linked: The New Science of Networks, 1979, Massachusotts: Persus Publishing

[2] Watts D. J.. The “new” science of networks. Annual Review of Sociology, 2004, 30: 243-270

[3] Jodan J.. The degree sequences and spectra of scale-free random graph. Random Structures and Algorithms, 2006, 29: 226-242

[4] An L., Liu X. R.. The stability analysis of random growing networks. Journal of Hebei University of Technology, 2010, 39: 17-19

[5] Cao Y.. The degree distribution of random k-trees. Theoretical Computer Science, 2009, 410: 688-695

[6] Han D.. The stationary distribution of a continuous-time random graph process with interacting edges. Acta Math. Phy. Sinica, 1994, 14: 98-102

[7] Avin C., Koucky M., Lotker Z.. How to explore a fast-changing world. Proc. of the 35th International Colloquium on Automata, Languages and Programming, 2008, Berlin: Springer-Verlag 121-132

[8] Clementi A. E. F., Macci C., Monnti M. Flooding time in edge-markovian dynamic graphs. Proc. of the 27th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 2008, New York: ACM Press 213-222

[9] Herv B., Pierluigi C., Pierre F.. Parsimonious flooding in dynamic graphs. Proc. of the 28th ACM Symposium on Principles of Distributed Computing, 2009, USA: Calgary, ACM Press 260-269

[10] Cai Q. S., Niu J. W.. Opportunity network time evolution graph model based on the edge independent evolution. Computer Engineering, 2011, 37(15): 17-22

[11] Du C. F.. Markov chain model of the random network. Science Technology and Engineering, 2010, 10(30): 7380-7383