Advanced

Dynamical random graphs with memory

Turova, Tatyana LU (2002) In Physical Review E 65(6).
Abstract
We study the large-time dynamics of a Markov process whose states are finite but unbounded graphs. The number of 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: the older an edge is, the lesser is the probability that it is still in the graph. The lifetime of any edge is distributed exponentially. We call its mean value (common for all edges) a parameter of memory, since it shows for how long the system keeps a particular connection between the vertices in the graph. We show that our model provides a bridge between two well-known models: when the parameter of memory goes to infinity this is a generalized model of random growth,... (More)
We study the large-time dynamics of a Markov process whose states are finite but unbounded graphs. The number of 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: the older an edge is, the lesser is the probability that it is still in the graph. The lifetime of any edge is distributed exponentially. We call its mean value (common for all edges) a parameter of memory, since it shows for how long the system keeps a particular connection between the vertices in the graph. We show that our model provides a bridge between two well-known models: when the parameter of memory goes to infinity this is a generalized model of random growth, and when this parameter is zero, i.e., no memory, our model behaves as a random graph. Thus by introducing a general class of dynamical graphs we have a unified overview on rather different models and the relations between them. We find all the critical values of the parameters at which our model exhibits phase transitions and describe the properties of the phase diagram. Finally, we compare and discuss the efficiency of the corresponding networks. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Physical Review E
volume
65
issue
6
publisher
American Physical Society
external identifiers
  • wos:000176762900009
  • scopus:41349093091
ISSN
1063-651X
DOI
10.1103/PhysRevE.65.066102
language
English
LU publication?
yes
id
3997587b-7786-4793-b4d7-ff0f267b215b (old id 333226)
date added to LUP
2007-11-19 08:28:26
date last changed
2017-12-10 04:30:29
@article{3997587b-7786-4793-b4d7-ff0f267b215b,
  abstract     = {We study the large-time dynamics of a Markov process whose states are finite but unbounded graphs. The number of 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: the older an edge is, the lesser is the probability that it is still in the graph. The lifetime of any edge is distributed exponentially. We call its mean value (common for all edges) a parameter of memory, since it shows for how long the system keeps a particular connection between the vertices in the graph. We show that our model provides a bridge between two well-known models: when the parameter of memory goes to infinity this is a generalized model of random growth, and when this parameter is zero, i.e., no memory, our model behaves as a random graph. Thus by introducing a general class of dynamical graphs we have a unified overview on rather different models and the relations between them. We find all the critical values of the parameters at which our model exhibits phase transitions and describe the properties of the phase diagram. Finally, we compare and discuss the efficiency of the corresponding networks.},
  author       = {Turova, Tatyana},
  issn         = {1063-651X},
  language     = {eng},
  number       = {6},
  publisher    = {American Physical Society},
  series       = {Physical Review E},
  title        = {Dynamical random graphs with memory},
  url          = {http://dx.doi.org/10.1103/PhysRevE.65.066102},
  volume       = {65},
  year         = {2002},
}