×

Nongrowing preferential attachment random graphs. (English) Zbl 1237.05189

Summary: We consider an edge rewiring process that is widely used to model the dynamics of scale-free weblike networks. This process uses preferential attachment and operates on sparse multigraphs with \(n\) vertices and \(m\) edges. We prove that its mixing time is optimal and develop a framework that simplifies the calculation of graph properties in the steady state. The applicability of this framework is demonstrated by calculating the degree distribution, the number of self-loops, and the threshold for the appearance of the giant component.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
60C05 Combinatorial probability
05C07 Vertex degrees
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)