Dynamical random graphs with memory
(2002) In Physical Review E 65(6). Abstract
 We study the largetime 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 meanfield 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 wellknown models: when the parameter of memory goes to infinity this is a generalized model of random growth,... (More)
 We study the largetime 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 meanfield 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 wellknown 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
 1063651X
 DOI
 10.1103/PhysRevE.65.066102
 language
 English
 LU publication?
 yes
 id
 3997587b77864793b4d7ff0f267b215b (old id 333226)
 date added to LUP
 20160401 16:06:25
 date last changed
 20220322 08:26:44
@article{3997587b77864793b4d7ff0f267b215b, abstract = {{We study the largetime 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 meanfield 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 wellknown 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 = {{1063651X}}, 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}}, }