Wu Zhi-Xi, Holme Petter
Institute of Computational Physics and Complex Systems, Lanzhou University, Lanzhou, Gansu 730000, China.
Phys Rev E Stat Nonlin Soft Matter Phys. 2011 Aug;84(2 Pt 2):026106. doi: 10.1103/PhysRevE.84.026106. Epub 2011 Aug 5.
In a recent work [Proc. Natl. Acad. Sci. USA 108, 3838 (2011)], Schneider et al. proposed a new measure for network robustness and investigated optimal networks with respect to this quantity. For networks with a power-law degree distribution, the optimized networks have an onion structure-high-degree vertices forming a core with radially decreasing degrees and an over-representation of edges within the same radial layer. In this paper we relate the onion structure to graphs with good expander properties (another characterization of robust network) and argue that networks of skewed degree distributions with large spectral gaps (and thus good expander properties) are typically onion structured. Furthermore, we propose a generative algorithm producing synthetic scale-free networks with onion structure, circumventing the optimization procedure of Schneider et al. We validate the robustness of our generated networks against malicious attacks and random removals.
在最近的一项研究工作中[[[《美国国家科学院院刊》108, 3838 (2011)]中，施耐德等人提出了一种衡量网络鲁棒性的新方法，并针对这一指标研究了最优网络。对于具有幂律度分布的网络，优化后的网络具有洋葱结构——高度顶点形成一个核心，度数沿径向递减，且同一径向层内的边过度集中。在本文中，我们将洋葱结构与具有良好扩展器特性的图（鲁棒网络的另一种特征）联系起来，并指出具有大谱隙（因而具有良好扩展器特性）的偏态度分布网络通常具有洋葱结构。此外，我们提出了一种生成算法，用于生成具有洋葱结构的合成无标度网络，绕过了施耐德等人的优化过程。我们验证了我们生成的网络针对恶意攻击和随机移除的鲁棒性。
