2009/12/19 by Balázs Ráth, Rath, Balazs
Computer Science · Mathematics · Physics and Astronomy · #60C05 #Cellular Automata and Applications #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Probability (math.PR) #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.0912.3904
openalex publication_date 2009/12/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We define the edge reconnecting model, a random multigraph evolving in time. At each time step we change one endpoint of a uniformly chosen edge: the new endpoint is chosen by linear preferential attachment. We consider a sequence of edge reconnecting models where the sequence of initial multigraphs is convergent in a sense which is a natural generalization of the notion of convergence of dense graph sequences, defined by Lovasz and Szegedy in arXiv:math/0408173. We investigate how the limit object evolves under the edge reconnecting dynamics if we rescale time properly: we give the complete characterization of the time evolution of the limit object from its initial state up to the stationary state, which is described in the companion paper arXiv:1106.2058. In our proofs we use the theory of exchangeable arrays, queuing and diffusion processes. The number of parallel edges and the degrees evolve on different timescales and because of this the model exhibits subaging.