Long paths and cycles in dynamical graphs
(2003) In Journal of Statistical Physics 110(12). p.385417 Abstract
 We study the largetime dynamics of a Markov process whose states are finite directed graphs. The number of the vertices is described by a supercritical branching process, and the edges follow a certain meanfield dynamics determined by the rates of appending and deleting. We find sufficient conditions under which asymptotically a.s. the order of the largest component is proportional to the order of the graph. A lower bound for the length of the longest directed path in the graph is provided as well. We derive an explicit formula for the limit as time goes to infinity, of the expected number of cycles of a given finite length. Finally, we study the phase diagram.
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/323409
 author
 Turova, Tatyana ^{LU}
 organization
 publishing date
 2003
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 randomly grown networks, phase transition, branching processes, dynamical random graphs
 in
 Journal of Statistical Physics
 volume
 110
 issue
 12
 pages
 385  417
 publisher
 Springer
 external identifiers

 wos:000179169100014
 scopus:0037210434
 ISSN
 15729613
 DOI
 language
 English
 LU publication?
 yes
 id
 41b2de7a327e476593868d8d082c97ce (old id 323409)
 date added to LUP
 20070923 13:15:28
 date last changed
 20180529 09:28:24
@article{41b2de7a327e476593868d8d082c97ce, abstract = {We study the largetime dynamics of a Markov process whose states are finite directed graphs. The number of the vertices is described by a supercritical branching process, and the edges follow a certain meanfield dynamics determined by the rates of appending and deleting. We find sufficient conditions under which asymptotically a.s. the order of the largest component is proportional to the order of the graph. A lower bound for the length of the longest directed path in the graph is provided as well. We derive an explicit formula for the limit as time goes to infinity, of the expected number of cycles of a given finite length. Finally, we study the phase diagram.}, author = {Turova, Tatyana}, issn = {15729613}, keyword = {randomly grown networks,phase transition,branching processes,dynamical random graphs}, language = {eng}, number = {12}, pages = {385417}, publisher = {Springer}, series = {Journal of Statistical Physics}, title = {Long paths and cycles in dynamical graphs}, url = {http://dx.doi.org/}, volume = {110}, year = {2003}, }