Degree-preserving Network Growth*

Real-world networks evolve over time via the addition or removal of vertices and edges. In current network evolution models, vertex degree varies or can even grow arbitrarily, yet there are many networks in which it saturates (e.g., social networks) or is fixed (e.g., chemical complexes), thus requiring an entirely different description. We introduce a novel class of models that encapsulates degree preserving dynamics in the simplest form, resulting in structures significantly different from previous ones. We discuss their properties as function of the evolution of the network's matching number and present several generative models based on this framework, from growing uniform degree distribution graphs to growing random regular graphs, which, to our best knowledge, is the first model of this kind. Within this approach, we also introduce configuration-like models that realize given degree sequences, with tunable degree-mixing properties. Moreover, this process can generate scale-free networks with arbitrary exponents, but without involving any degree-based preferential attachment.