s_(max)图算法及其相关标度测度的改进

Improved algorithm of s_(max) graph and scale metric of S(g) for complex networks

在给定相同度序列的条件下,讨论了计算smax的二种算法所存在的不同缺陷:基于边算法的时间和空间复杂度都为O(N2),对较大的N会导致计算机存储空间不够;基于点算法是smax的一个近似值,通过实例说明其近似计算的误差不容忽视,而且该算法只能用来计算度序列中的最小度m=1的情况,对度序列中最小度m>1的情况,用该算法来计算smax就会失效。基于上述算法的缺陷,提出了一个改进算法,它具有smax值精度的优越性和对m>1情况的有效性。采用改进的算法求得smax值,通过对不同模型的模拟和分析,发现与smax值相关的标度测度S(g)关于网络规模、网络稠密度具有较大波动性,这会导致对网络无标度程度的误判,为消除网络规模、网络稠密度对测度的影响,对该测度做了改进,实验结果显示新的测度Sne(wg)更稳定。

This paper discusses different flaws of the link-based algorithm and the node-based algorithm to calculate Smax value for graph having an identical degree sequence. The time and space complexity are O（N^2） for the former, and it spends massive time or causes insuf- ficient space. The calculation error can＇ t be allowed to ignore for the latter, and the algorithm can＇ t be used to analyze the identical de- gree sequence with minimal degree m〉1. Based on these defects, this paper presents an improved algorithm, which has its superiority and validity. In addition, this paper studies the scale metric S（g） for different models. Through the simulation and statistical analysis, the scale metric S（g） has large fluctuation about network size and density. In order to eliminate the influence of network size and density, this paper puts forward a new scale metric, and experimental result shows that the new scale metric Smax（g） is more stable.