Degree distribution of large networks generated by the partial duplication model

Li, Si, Choi, Kwok Pui and Wu, Taoyang ORCID: https://orcid.org/0000-0002-2663-2001 (2013) Degree distribution of large networks generated by the partial duplication model. Theoretical Computer Science, 476. pp. 94-108.

Full text not available from this repository. (Request a copy)

Abstract

In this paper, we present a rigorous analysis on the limiting behavior of the degree distribution of the partial duplication model, a random network growth model in the duplication and divergence family that is popular in the study of biological networks. We show that for each non-negative integer k, the expected proportion of nodes of degree k approaches a limit as the network becomes large. This fills in a gap in previous studies. In addition, we prove that p=1/2, where p is the selection probability of the model, is the phase transition for the expected proportion of isolated nodes converging to 1, and hence answer a question raised in Bebek et al. [G. Bebek, P. Berenbrink, C. Cooper, T. Friedetzky, J. Nadeau, S.C. Sahinalp, The degree distribution of the generalized duplication model, Theoret. Comput. Sci. 369 (2006) 239–249]. We also obtain asymptotic bounds on the convergence rates of degree distribution. Since the observed networks typically do not contain isolated nodes, we study the subgraph consisting of all non-isolated nodes contained in the networks generated by the partial duplication model, and show that p=1/2 is again a phase transition for the limiting behavior of its degree distribution.

Item Type:	Article
Faculty \ School:	Faculty of Science > School of Computing Sciences
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Computational Biology > Phylogenetics (former - to 2018) Faculty of Science > Research Centres > Centre for Ecology, Evolution and Conservation Faculty of Science > Research Groups > Data Science and AI
Depositing User:	Users 2731 not found.
Date Deposited:	03 Apr 2013 20:57
Last Modified:	10 Dec 2024 01:17
URI:	https://ueaeprints.uea.ac.uk/id/eprint/42066
DOI:	10.1016/j.tcs.2012.12.045

Actions (login required)

View Item