复杂网络分形维数的计算方法研究

摘要

检测复杂网络中的分形特性和自相似性广泛采用盒覆盖法计算其分形维数的办法，而其中问题的关键是如何用最少盒子来覆盖整个网络，或者如何得到一个最优的解决方案。在独立盒子以及没有考虑网络自身结构的情况下，由盒覆盖法得到的结果往往具有很大的随机性或者较大的误差。本文主要从两个方面对该问题进行了研究，即重叠盒子和由外到内的层次，以尽可能的得到更少的盒子数量，从而使得分形维数更加精确。
　　其一，本文采用重叠盒子来覆盖整个网络，将该方法称为重叠盒覆盖法。在这此情况下，为了验证其有效性，本文提出一个重叠盒覆盖算法(OBCA)，并将其应用到三个确定性网络以及四个实际分形网络中。对于前者，OBCA得到了最优盒子数量或者更精确的分形维数;对于后者，OBCA最终得到的盒子数量更少且更确定，其中冗余盒子的比重最多高达33.3％。实验结果表明，重叠盒覆盖法是有效的，并且重叠盒子要优于独立盒子的情况，使得随机性有所降低，误差更小。
　　其二，本文检验由外到内的层次节点执行序列是否有助于盒覆盖法获得更少的盒子数量。首先，定义两种由外到内的层次，即距离层次和度层次。然后，在这两种层次节点序列下，将OBCA与CBB（紧密盒燃烧）算法应用到上述三个确定性网络和四个实际分形网络中。对于前者，在距离层次任意随机序列下，两个算法都得到最优的盒子数量。对于后者，在这两种层次下，CBB算法都能够生成更少的盒子，而OBCA得到的盒子数量在整体上都没有太大变化。实验结果表明，这两种由外到内的层次都起到有效的作用，都有利于盒覆盖法得到更少的盒子数量，尤其是CBB算法。
　　最后，本文得出结论，认为重叠盒子以及由外到内的层次是决定复杂网络分形维数更加精确的两个影响因素。