Advanced

Long paths and cycles in dynamical graphs

Turova, Tatyana LU (2003) In Journal of Statistical Physics 110(1-2). p.385-417
Abstract
We study the large-time 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 mean-field 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:
author
organization
publishing date
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
1-2
pages
385 - 417
publisher
Springer
external identifiers
  • wos:000179169100014
  • scopus:0037210434
ISSN
1572-9613
DOI
10.1023/A:1021035131946
language
English
LU publication?
yes
id
41b2de7a-327e-4765-9386-8d8d082c97ce (old id 323409)
date added to LUP
2007-09-23 13:15:28
date last changed
2018-01-07 09:42:01
@article{41b2de7a-327e-4765-9386-8d8d082c97ce,
  abstract     = {We study the large-time 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 mean-field 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         = {1572-9613},
  keyword      = {randomly grown networks,phase transition,branching processes,dynamical random graphs},
  language     = {eng},
  number       = {1-2},
  pages        = {385--417},
  publisher    = {Springer},
  series       = {Journal of Statistical Physics},
  title        = {Long paths and cycles in dynamical graphs},
  url          = {http://dx.doi.org/10.1023/A:1021035131946},
  volume       = {110},
  year         = {2003},
}