When Markov chains meet: a continuous-time model of network evolution. (English) Zbl 1343.60114

Summary: We suggest a novel approach to model continuous time processes of the interactions of independent elements. The model assumes a finite number of independent Markov chains, each representing an element. Chains move among a common space of states. Sometimes chains intersect, being in the same state at the same time. These intersections relate the chains with each other and imply many interesting processes. In this paper, we examine our new approach in the context of network evolution. Our analytic study achieves a closed solution for the expected time until a node has any specific degree. Our numerical study demonstrates properties which are in agreement with real world networks. Thus we show the potential of our approach.


60J27 Continuous-time Markov processes on discrete state spaces
60J28 Applications of continuous-time Markov processes on discrete state spaces
60K35 Interacting random processes; statistical mechanics type models; percolation theory
90B15 Stochastic network models in operations research
65C40 Numerical analysis or methods applied to Markov chains
Full Text: DOI


[1] Acquisti, A., Gross, R., 2006. Imagined communities: awareness, information sharing and privacy on the Facebook. In: Proceedings of the 6th Workshop on Privacy Enhancing Technologies, Cambridge, UK.
[2] Adamic, L. A.; Huberman, B. A., Growth dynamics of the world wide web, Nature, 401, 131, (1999)
[3] Barabasi, A. L., Linked: the new science of networks, (2002), Perseus Cambridge, MA
[4] Barabasi, A. L.; Albert, R., Emergence of scaling in random networks, Science, 286, (1999) · Zbl 1226.05223
[5] Cancho, R. F.; Solè, R. V., The small world of human language, Proc. R. Soc. London B, 268, 2261-2265, (2001)
[6] Doyle, J. C.; Alderson, D. L.; Li, L.; Low, S.; Roughan, M.; Shalunov, S.; Tanaka, R.; Willinger, W., The “robust yet fragile” nature of the Internet, Proc. Natl. Acad. Sci., 102, 14497-14502, (2005)
[7] Enns, E. G., Derivation of the time dependent probability that a subset of identical units is operational, Proc. Inst. Electr. Electron. Eng. (IEEE), 54, (1966)
[8] Erdös, P.; Renyi, A., On the evolution of random graphs, Publ. Math. Inst. Hung. Acad. Sci., 5, (1960)
[9] Hebb, D. O., The organization of behavior: A neuropsychological theory, (1949), Wiley-Interscience New York
[10] Hopfield, J. J., Neural networks and physical systems with emergent collective computational abilities, Nat. Acad. Sci., 79, 2554-2558, (1982) · Zbl 1369.92007
[11] Karlin, S.; McGregor, J., Ehrenfest urn models, J. Appl. Probab., 2, 352-376, (1965) · Zbl 0143.40501
[12] Montoya, J. M.; Pimm, S. L., Ecological networks and their fragility, Nature, 442, 259-264, (2006)
[13] Uppuluri, V.R.R., Wright, T., 1981. A note on a further generalization of the Ehrenfest urn model, Proceedings of the American Statistical Association.
[14] Wasserman, S.; Faust, K., Social network analysis: methods and applications, (1994), Cambridge University Press Cambridge, UK
[15] Watts, D., The “new” science of networks, Annu. Rev. Sociol., 30, 243-270, (2004)
[16] Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, (1998) · Zbl 1368.05139
[17] Yook, S. H.; Jeong, H.; Barabasi, A. L., Modeling the internet’s large-scale topology, Proc. Natl. Acad. Sci., 99, 13382-13386, (2001)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.