Long paths and cycles in dynamical graphs
(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:
https://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
- 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
- 2016-04-01 17:01:21
- date last changed
- 2022-04-23 02:10:18
@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}}, keywords = {{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}}, doi = {{10.1023/A:1021035131946}}, volume = {{110}}, year = {{2003}}, }