发帖
雷达卡
摘要翻译：
计算分形网络维数的最小盒数复盖问题是一个NP难问题。同时，随机球覆盖计算维数的时间复杂度很低。本文严格给出了随机球覆盖算法相对误差的上界。我们还提出了计算网络维数的两次随机球覆盖算法。对于现实中的许多分形网络，当网络直径足够大时，该方法的相对误差上界将趋于0。从这个角度出发，在给定适当的误差范围内，维数计算就不是一个NP难问题，而是一个P问题。
---
英文标题：
《Upper Bound of Relative Error of Random Ball Coverage for Calculating
Fractal Network Dimension》
---
作者：
Yanqing Hu, Zengru Di
---
最新提交年份：
2007
---
分类信息：
一级分类：Physics 物理学
二级分类：Statistical Mechanics 统计力学
分类描述：Phase transitions, thermodynamics, field theory, non-equilibrium phenomena, renormalization group and scaling, integrable models, turbulence
相变，热力学，场论，非平衡现象，重整化群和标度，可积模型，湍流
--
---
英文摘要：
Least box number coverage problem for calculating dimension of fractal networks is a NP-hard problem. Meanwhile, the time complexity of random ball coverage for calculating dimension is very low. In this paper we strictly present the upper bound of relative error for random ball coverage algorithm. We also propose twice-random ball coverage algorithm for calculating network dimension. For many real-world fractal networks, when the network diameter is sufficient large, the relative error upper bound of this method will tend to 0. In this point of view, given a proper acceptable error range, the dimension calculation is not a NP-hard problem, but P problem instead.
---
PDF链接：
https://arxiv.org/pdf/710.5228
京公网安备 11010802022788号
