Dynamical random graphs with memory
Research output: Contribution to journal › Article
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.
Details
Authors  

Organisations  
Research areas and keywords  Subject classification (UKÄ) – MANDATORY

Original language  English 

Journal  Physical Review E 
Volume  65 
Issue number  6 
Publication status  Published  2002 
Publication category  Research 
Peerreviewed  Yes 