Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.tcs.2012.12.045
Title: Degree distribution of large networks generated by the partial duplication model
Authors: Li, S.
Choi, K.P. 
Wu, T. 
Keywords: Computational proteomics
Degree distribution
Limiting behavior
Power law
Random graph
Issue Date: 11-Mar-2013
Source: Li, S., Choi, K.P., Wu, T. (2013-03-11). Degree distribution of large networks generated by the partial duplication model. Theoretical Computer Science 476 : 94-108. ScholarBank@NUS Repository. https://doi.org/10.1016/j.tcs.2012.12.045
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.
Source Title: Theoretical Computer Science
URI: http://scholarbank.nus.edu.sg/handle/10635/52862
ISSN: 03043975
DOI: 10.1016/j.tcs.2012.12.045
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

1
checked on Dec 14, 2017

WEB OF SCIENCETM
Citations

1
checked on Nov 17, 2017

Page view(s)

54
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.