Degree-preserving network growth
Abstract
Real-world networks evolve over time through the addition or removal of nodes and edges. In current network-evolution models, the degree of each node varies or grows arbitrarily, yet there are many networks for which a different description is required. In some networks, node degree saturates, such as the number of active contacts of a person, and in some it is fixed, such as the valence of an atom in a molecule. Here we introduce a family of network growth processes that preserve node degree, resulting in structures substantially different from those reported previously.
We demonstrate that, despite it being an NP (non-deterministic polynomial time)-hard problem in general, the exact structure of most real-world networks can be generated from degree-preserving growth. We show that this process can create scale-free networks with arbitrary exponents, however, without preferential attachment. We present applications to epidemics control via network immunization, to viral marketing, to knowledge dissemination and to the design of molecular isomers with desired properties.
