Journal of Applied Mathematics
Volume 2008 (2008), Article ID 190836, 14 pages
doi:10.1155/2008/190836
Research Article
A Markov Chain Approach to Randomly Grown Graphs
Bioinformatics Research Center, University of Aarhus, Høegh-Guldbergs Gade 10, Building 1090, Århus C 8000, Denmark
Received 29 June 2007; Accepted 3 January 2008
Academic Editor: Rahul Roy
Copyright © 2008 Michael Knudsen and Carsten Wiuf. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract
A Markov chain approach to the study of randomly grown graphs is
proposed and applied to some popular models that have found use in biology
and elsewhere. For most randomly grown graphs used in biology,
it is not known whether the graph or properties of the graph converge (in
some sense) as the number of vertices becomes large. Particularly, we study
the behaviour of the degree sequence, that is, the number of vertices with
degree 0,1,…,
in large graphs, and apply our results to the partial duplication
model. We further illustrate the results by application to real data.