Degree distribution of large networks generated by the partial duplication model

Li, Si, Choi, Kwok Pui and Wu, Taoyang (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:	06 Feb 2025 01:24
URI:	https://ueaeprints.uea.ac.uk/id/eprint/42066
DOI:	10.1016/j.tcs.2012.12.045

Actions (login required)

View Item