计算机应用 ›› 2015, Vol. 35 ›› Issue (6): 1560-1563.DOI: 10.11772/j.issn.1001-9081.2015.06.1560

• 先进计算 • 上一篇    下一篇

复杂网络零模型的量化评估

李欢, 卢罡, 郭俊霞   

  1. 北京化工大学 信息科学与技术学院, 北京 100029
  • 收稿日期:2015-01-06 修回日期:2015-03-20 发布日期:2015-06-12
  • 通讯作者: 卢罡(1981-),男,吉林吉林人,讲师,博士,主要研究方向:复杂网络、社会计算;sizheng@126.com
  • 作者简介:李欢(1989-),女,河北张家口人,硕士研究生,主要研究方向:复杂网络、社会计算;郭俊霞(1980-),女,山西朔州人,讲师,博士,主要研究方向:网络信息定向抽取、网络用户行为分析。
  • 基金资助:

    北京高等学校青年英才计划项目(YETP0506)。

Quantitative evaluation for null models of complex networks

LI Huan, LU Gang, GUO Junxia   

  1. College of Information Science and Technology, Beijing University of Chemical Technology, Beijing 100029, China
  • Received:2015-01-06 Revised:2015-03-20 Published:2015-06-12

摘要:

针对随机置乱算法生成复杂网络的零模型时,因不同阶次零模型成功置乱概率的差异导致难以准确判断零模型何时能够趋于稳定的问题,定义了"成功置乱次数"的概念,并提出使用"成功置乱次数"替代传统的"尝试置乱次数"进行算法设定。提出的成功置乱次数指标仅在随机选择的边满足相应阶次零模型的置乱条件从而被成功置乱后进行累加。各阶次零模型生成实验表明,使用该算法设定方式后各网络拓扑指标均能在较小的成功置乱次数范围内趋于稳定。进一步的量化分析表明,按阶次分别设定成功置乱次数为网络边数的2倍、1倍、1倍即可得到质量较好的0阶、1阶、2阶零模型。

关键词: 复杂网络, 零模型, 随机置乱算法, 成功置乱次数, 稳定性

Abstract:

The null models of complex networks generated by random scrambling algorithm often can't tell when null models can be stable because of the difference of successful scrambling probabilities of different order null models. Focusing on the issue, the concept of "successful scrambling times" was defined and used to replace the usual "try scrambling times" to set the algorithm. The index of the proposed successful scrambling times could be added only when the randomly selected edges could meet the scrambling conditions of corresponding null models, and thus be successfully scrambled. The generation experiments of null models of every order show that every index can be stable in a small scale of successful scrambling times. Further quantitative analyses show that, according to the corresponding orders, 0-order, 1-order and 2-order null models with good quality can be got by setting successfully scrambling times to be 2 times, 1 times and 1 times of actual networks' edge number respectively.

Key words: complex network, null model, random scrambling algorithm, successful scrambling times, stability

中图分类号: