Dynamical random graphs with memory
(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:
https://lup.lub.lu.se/record/333226
- author
- Turova, Tatyana LU
- organization
- publishing date
- 2002
- 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
- pmid:12188778
- 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
- 2016-04-01 16:06:25
- date last changed
- 2022-03-22 08:26:44
@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}}, doi = {{10.1103/PhysRevE.65.066102}}, volume = {{65}}, year = {{2002}}, }