On the Fractality of Complex Networks: Covering Problem, Algorithms and Ahlfors Regularity.
On the Fractality of Complex Networks: Covering Problem, Algorithms and Ahlfors Regularity.
复制标题
复杂网络的分形：涵盖问题、算法和 Ahlfors 正则
DOI：
10.1038/srep41385
复制
发表时间：
2017-01-27
影响因子：
4.6
通讯作者：
Zhao L
中科院分区：
文献类型：
--
作者：
Wang L;Wang Q;Xi L;Chen J;Wang S;Bao L;Yu Z;Zhao L
本文从最小盒覆盖、最小球覆盖和球的平均体积三个维度重新审视复杂网络的分形性。前两个维度通过最小盒子覆盖问题和最小球覆盖问题计算。对于最小球覆盖问题，我们证明了它的NP-完全性，并给出了几种求解其可行解的启发式算法，并对这些算法的性能进行了比较。对于第三维，我们引入了随机球体积算法。引入网络的Ahlfors正则性的概念，证明了如果网络是Ahlfors正则的，则网络的上述三个维是相同的。我们还提供了一类满足Ahlfors正则性的网络。
In this paper, we revisit the fractality of complex network by investigating three dimensions with respect to minimum box-covering, minimum ball-covering and average volume of balls. The first two dimensions are calculated through the minimum box-covering problem and minimum ball-covering problem. For minimum ball-covering problem, we prove its NP-completeness and propose several heuristic algorithms on its feasible solution, and we also compare the performance of these algorithms. For the third dimension, we introduce the random ball-volume algorithm. We introduce the notion of Ahlfors regularity of networks and prove that above three dimensions are the same if networks are Ahlfors regular. We also provide a class of networks satisfying Ahlfors regularity.