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

关键词：复杂网络；零模型；随机置乱无对应英文无体现算法；成功置乱次数；稳定性

中图分类号： TP393.01 文献标志码：A

英文摘要

英文关键词

Key words：complex network； null model； random scrambling algorithm； successful scrambling times； stability

0 引言

在生成零模型的置乱过程中，置乱次数过少可能导致零模型随机化不充分，进而影响零模型质量，而对于规模较庞大的网络而言，置乱次数过多又会在零模型特征已稳定后消耗大量的时间进行无意义的置乱。究竟要进行多少次的随机置乱才“足够好”、随机置乱的次数对网络拓扑性质以及进一步对零模型的使用的影响等问题，尚未有人作过量化的研究。文献[7]指出对一个L条边的实际网络，需要置乱4L次则零模型基本保持稳定，但文中仅是针对1阶零模型而言，对于其他阶次零模型则不适用，且并未对该结论进行相应的评估与证明。本文将针对基于随机置乱方法生成零模型需要的执行次数进行研究，考察不同阶次的零模型生成过程中网络特性变化情况，最终将约定一个置乱次数范围，供研究者们在生成零模型的过程中进行参考。

1 随机置乱的零模型构建方法

根据随机置乱时约束条件的不同，零模型通常可分为以下不同的阶次的随机化网络[8-10]： 1）0阶零模型：与原网络有相同节点数和边数，即相同的平均度〈k〉。

2）1阶零模型：与原网络有相同节点数和度分布ρ（k）。

3）2阶零模型：与原网络有相同节点数和联合度分布ρ（k， k′）。

1）d=0，即0阶零模型的随机置乱算法。每次随机选择原网络中的一条边em， n，再随机选择两个节点p、q，若这两个节点不相连，则删除em， n，增加ep， q。

2）d=1，即1阶零模型随机置乱算法。每次随机选择原网络中的两条边，记为em， n和ep， q若vm、 vn、vp、vq这4个节点之间仅存在这两条边，则删除em， n和ep， q，并创建新边em， q和ep， n.。

3）d=2，即2阶零模型的随机置乱算法。在1阶零模型的基础上要求节点vn、vq（或vm、vp）具有相同的度值。

上述算法也可以推广到有向网络，如保持每个节点的入度和出度不变进行随机置乱而生成有向网络的1阶零模型。

2 网络特性评估指标

在复杂网络的研究中，通常使用以下指标衡量某个网络的拓扑特性。

2.1 平均路径长度

一个网络中从节点i出发到节点j之间经过的最短距离dij定义为从i到j经过的所有可达路径中节点数和边数最少的路径中的边数。对于一个含N个节点的网络，每一对节点之间最短路径的平均值则称为该网络的平均路径长度（Average path length）l，计算方法为：

一个网络的平均路径长度（Average path length）l定义为网络中任意两节点之间距离的平均值。

其中N为网络节点个数。

2.2 同配系数

同配系数即Pearson相关系数（assortativity coefficient）：衡量度值相近的节点之间互相连接的倾向性。度高的节点倾向于与度高的节点相互连接或度低的节点倾向于与度低的节点相互连接的现象称为同配，度高的节点倾向于与度低的相互连接称为异配。同配系数定义为：

3 成功置乱次数

将本文提出的成功置乱次数应用至算法中，以1阶随机置乱算法为例，设计如下的伪代码。其中：布尔型变量succ为成功置乱标记符号；attempt_times为尝试置乱次数；succ_times为成功置乱次数；succ_prob为成功置乱概率。为节省时间，对所有数据集仅计算100个成功概率值。

4 稳定次数的确定

从第3章中可以看到在应用零模型时应采用成功置乱次数。为了进一步验证设定其作为置乱次数能够在不同阶次、数据集的情况下仍旧保证在一定的次数内使零模型趋于稳定，并最终得出不同阶次稳定次数的可设定范围，本文针对不同规模数据集做了如下的实验。 选用4个不同规模的公共数据集football、 petsterfamilylinkshamster、p2pGnutella08、Wikipedia vote network进行零模型质量的研究，其中football为无向网络，其余数据集为有向网络，数据规模见表1。

本文选用第2章中各网络拓扑指标对以上各网络的0阶到2阶零模型质量进行评估，因篇幅限制，此处仅给出petsterfamilylinkshamster网络2阶随机置乱各网络拓扑指标的变化图，其中计算Q值时采用经典的基于贪婪算法思想的社团结构检测算法――缩略语CNM算法由Clauset、Newman和Moore提出。算法名称为这几个人的名字缩写。CNM（Clauset，Newman，Moore）算法，算法采用堆数据结构计算和更新模块度。实验结果如图3所示。，横坐标为成功置乱次数，纵坐标依次为平均路径长度、聚类系数、成功置乱概率、社团Q值以及同配系数（包括r（out，in）， r（in，out），r（out，out），r（in，in））。

为方便以后学者们对于零模型的应用，避免无规则地人为设定置乱次数，有必要确定一个明确的置乱次数。通过对表2的总结，将不同阶次置乱次数规定如表3，当对实际网络成功置乱表中相应次数时（可在第3章的伪代码中将N设为表中的值），得到的零模型便是稳定的。

5 结语

本文仅针对0到2阶零模型置乱次数作了研究，对于更高阶次零模型的特征分析与质量评估以及网络内部结构和置乱次数之间的关系是下一步研究的方向。

参考文献：

[9]MAHADEVAN P， HUBBLE C， KRIOUKOV D， et al.Orbis： rescaling degree correlations to generate annotated Internet topologies [J]. ACM SIGCOMM Computer Communication Review， 2007， 37（4）：325-336.