smax图算法及其相关标度测度的改进

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (9): 43-46.

smax图算法及其相关标度测度的改进

周晖杰1，史定华2，毛小燕3

1.宁波大学科学技术学院，浙江宁波 315212
2.上海大学数学系，上海 200444
3.宁波大学数学系，浙江宁波 315211

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2012-03-21 发布日期:2012-04-11

Improved algorithm of smax graph and scale metric of S（g） for complex networks

ZHOU Huijie1, SHI Dinghua2, MAO Xiaoyan3

1.College of Science and Technology, Ningbo University, Ningbo, Zhejiang 315212, China
2.Department of Mathematics, Shanghai University, Shanghai 200444, China
3.Department of Mathematics, Ningbo University, Ningbo, Zhejiang 315211, China

Received:1900-01-01 Revised:1900-01-01 Online:2012-03-21 Published:2012-04-11

摘要/Abstract

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

关键词: 基于边算法, 基于点算法, 无标度测度, 网络稠密度

Abstract: 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（N2） for the former, and it spends massive time or causes insufficient space. The calculation error can’t be allowed to ignore for the latter, and the algorithm can’t be used to analyze the identical degree 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 Snew（g） is more stable.

Key words: link-based algorithm, node-based algorithm, scale-free metric, network density

周晖杰1，史定华2，毛小燕3. smax图算法及其相关标度测度的改进[J]. 计算机工程与应用, 2012, 48(9): 43-46.

ZHOU Huijie1, SHI Dinghua2, MAO Xiaoyan3. Improved algorithm of smax graph and scale metric of S（g） for complex networks[J]. Computer Engineering and Applications, 2012, 48(9): 43-46.