Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T11:40:52.719Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic Properties of a Random Graph with Duplications

Part of: Graph theory Stochastic processes

Published online by Cambridge University Press:  30 January 2018

Ágnes Backhausz  and
Tamás F. Móri
Ágnes Backhausz*
Affiliation:
Eötvös Loránd University
Tamás F. Móri*
Affiliation:
Eötvös Loránd University
*
∗ Postal address: MTA Alfréd Rényi Institute of Mathematics, Pázmány P. s. 1/C, H-1117, Budapest, Hungary. Email address: [email protected]
∗∗ Postal address: Department of Probability Theory and Statistics, Pázmány P. s. 1/C, H-1117, Budapest, Hungary. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We deal with a random graph model evolving in discrete time steps by duplicating and deleting the edges of randomly chosen vertices. We prove the existence of an almost surely asymptotic degree distribution, with stretched exponential decay; more precisely, the proportion of vertices of degree d tends to some positive number cd > 0 almost surely as the number of steps goes to ∞, and cd ~ (eπ)1/2d1/4e-2√d holds as d → ∞.

Keywords

Scale-freeduplicationdeletionrandom graphmartingale

MSC classification

Primary: 60G42: Martingales with discrete parameter
Secondary: 05C80: Random graphs
Type
Research Article
Information
Journal of Applied Probability , Volume 52 , Issue 2 , June 2015 , pp. 375 - 390
Copyright
© Applied Probability Trust 

References

Backhausz, Á. and Móri, T. F. (2014). A random model of publication activity. Discrete Appl. Math. 162, 78–89.Google Scholar
Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286, 509–512.Google Scholar
Cooper, C. and Frieze, A. (2003). A general model of web graphs. Random Structures Algorithms 22, 311–335.Google Scholar
Bebek, G. et al. (2006). The degree distribution of the generalized duplication model. Theoret. Comput. Sci. 369, 239–249.CrossRefGoogle Scholar
Bollobás, B., Riordan, O., Spencer, J. and Tusnády, G. (2001). The degree sequence of a scale-free random graph process. Random Structures Algorithms 18, 279–290.CrossRefGoogle Scholar
Chung, F., Lu, L., Dewey, T. G. and Galas, D. J. (2003). Duplication models for biological networks. J. Comput. Biol. 10, 677–687.Google Scholar
Cohen, N., Jordan, J. and Voliotis, M. (2010). Preferential duplication graphs. J. Appl. Prob. 47, 572–585.Google Scholar
de Solla Price, D. (1976). A general theory of bibliometric and other cumulative advantage processes. J. Amer. Soc. Inf. Sci. 27, 292–306.Google Scholar
Dong, R., Goldschmidt, C. and Martin, J. B. (2006). Coagulation-fragmentation duality, Poisson–Dirichlet distributions and random recursive trees. Ann. Appl. Prob. 16, 1733–1750.Google Scholar
Faloutsos, M., Faloutsos, P. and Faloutsos, C. (1999). On power-law relationships of the internet topology. In Proceedings of the Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, SIGCOMM '99, ACM, New York, pp. 251–262.Google Scholar
Hamdi, M., Krishnamurthy, V. and Yin, G. (2014). Tracking a Markov- modulated stationary degree distribution of a dynamic random graph, IEEE Trans. Inf. Theory 60, 6609–6625.Google Scholar
Jordan, J. (2011). Randomised reproducing graphs. Electron. J. Prob. 16, 1549–1562.Google Scholar
Kim, J., Krapivsky, P. L., Kahng, B. and Redner, S. (2002). Infinite-order percolation and giant fluctuations in a protein interaction network. Phys. Rev. E 66, 055101(R).Google Scholar
Pastor-Satorras, R., Smith, E. and Solé, R. V. (2003). Evolving protein interaction networks through gene duplication. J. Theoret. Biol. 222, 199–210.Google Scholar
Ráth, B. and Tóth, B. (2009). Erdős–Rényi random graphs + forest fires = self-organized criticality. Electron. J. Prob. 14, 1290–1327.Google Scholar
Shiryaev, A. N. (1996). Probability, 2nd edn. Springer, New York.Google Scholar
Simon, H. A. (1955). On a class of skew distribution functions. Biometrika 42, 425–440.Google Scholar
Sridharan, A., Gao, Y., Wu, K. and Nastos, J. (2011). Statistical behavior of embeddedness and communities of overlapping cliques in online social networks. In Proc. IEEE INFOCOM 2011, IEEE, New York, pp. 546–550.Google Scholar
Szymańsky, J. (1987). On a nonuniform random recursive tree, In Random Graphs '85 (Ann. Discrete Math. 33, North-Holland, Amsterdam, pp. 297–306.Google Scholar
van der Hofstad, R. Random graphs and complex networks. Preprint, Eindhoven University of Technology. Available at {http://www.win.tue.nl/rhofstad/NotesRGCN.pdf}.Google Scholar
Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature 393, 440–442.Google Scholar
Willinger, W., Alderson, D. and Doyle, J. C. (2009). Mathematics and the Internet: a source of enormous confusion and great potential. Notices Amer. Math. Soc. 56, 586–599.Google Scholar
Yule, G. U. (1925). A mathematical theory of evolution, based on the conclusions of Dr. J. C. Willis, F.R.S. Philos. Trans. R. Soc. London B. 213, 21–87.Google Scholar