Degree-preserving network growth
Degree-preserving network growth
复制标题
DOI：
10.1038/s41567-021-01417-7
复制
发表时间：
2021-12
期刊：
影响因子：
19.6
通讯作者：
Shubha R. Kharel;T. Mezei;Sukhwan Chung;P. Erdős;Z. Toroczkai
中科院分区：
文献类型：
--
作者：
Shubha R. Kharel;T. Mezei;Sukhwan Chung;P. Erdős;Z. Toroczkai
现实世界的网络随着时间的推移通过添加或删除节点和边而发展。在目前的网络演化模型中，每个节点的度都是任意变化或增长的，但有许多网络需要不同的描述。在一些网络中，节点度饱和，例如一个人的活跃联系人的数量，而在一些网络中，它是固定的，例如分子中原子的价态。在这里，我们介绍了一个家庭的网络增长过程，保持节点度，导致结构与以前报道的有很大不同。我们证明了，尽管它是一个NP（非确定性多项式时间）困难的问题，在一般情况下，大多数真实世界的网络的确切结构可以从度保持增长。我们表明，这个过程可以创建无标度网络与任意指数，但是，没有优惠的附件。我们目前的应用，通过网络免疫流行病控制，病毒营销，知识传播和设计具有所需性能的分子异构体。
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.