改进的随机分块模型

李慧驰

【摘 要】社团结构揭示了网络内部的结构，不断优化发现社团的算法尤为重要.而随机分块模型是用于测试算法表现的基本工具，其改进与更新对于适应各种新算法的测试具有重要意义.笔者主要介绍一种对度进行改进的随机分块模型，浅析其性质，对比模糊程度不同的网络，以便于更好的将其运用于算法的测试。

【关键词】社团结构；随机分块模型；模糊程度

0.引言

在复杂网络中，随机分块模型既可以用来发现网络社团结构，还可用于产生合成网络，以此作为测试社团发现等算法的表现.然而，传统的分块模型忽略了节点度的变化性，与真实网络中度的分布特征不太相符.因此，在真实网络的社团发现过程中，传统模型的合成网络对于测试算法准确性并不十分适用.Brian Karrer和M.E.J.Newman对传统的随机分块模型做了改进，使得改进后的模型生成的网络度的分布更为宽泛，这样就更加接近于真实网络的特性[1]。

1.模型介绍

本文所探讨的随机分块模型为对度进行改进的模型，其相比与传统的模型，度的变化范围更为宽泛，更接近真实网络的特性.在模型的理论分析过程中，我们允许节点自连边以及多连边，这主要体现在生成模型的连边概率中，对网络的产生没有影响[2]。

该模型中网络节点的度服从普瓦松分布，社团大小服从均匀分布.网络的生成过程主要分为两步：首先，要确定网络的群分配，即社团结；其次，要确定网络中每两条边之间连边的概率.社团结构的划分是预先设置的，而群gi与群gj内节点连边的概率如下式所示：

Pgigj=θiθjωgi，gj （1）

在上式中，gi表示节点i所属的社团，参数θi和ωrs的最大似然值分别如下：

= rs=mrs （2）

2.合成网络

在运用随机分块模型生成网络时，涉及到参数的选择.对于网络的群分配参数g和节点的期望度值，我们可以根据实验需要进行预设值，而对于参数ωrs的选择，则相对复杂.理论上来说，任何满足sωrs=kr的非负ωrs值都可以.然而，考虑到我们要用于实验的网络并非具有同样的社团结构，而是千变万化的.为了便于更便捷的生成社团结构不同的网络，我们引入参数λ，来调节下面线性表达式的系数：

ω=λωplanted+（1-λ）ωrandom （3）

这里，ωrsandom=krks/2m对应于随机图中ωrs的期望值，而ωrsplanted对应于构造社团结构.例如，我们想要将网络划分为4个社团，那么就有：

ω= （4）

2.1合成网络特性分析

运用MALAB软件，编写以上随机分块模型的生成程序，并对相应的网络特性进行分析.以500个节点的网络为例，设置其社团数目为5个，参数λ设为0.8。

实验结果表明，网络中节点度大致服从普瓦松分布，并且该生成网络节点的度主要集中在0-50之间，度大于50的节点非常少.对生成网络中节点度的分布有大致了解，有助于我们对网络特性的掌握，在连边预测以及社团分析时，能帮助我们分析实验结果。

2.2合成网络的对比分析

我们运用该模型，分别生成社团结构模糊程度不同的网络，预先设置社团数为2，随着参数λ 的不断增大，网络的社团结构越来越清晰，当λ=0.5时，从表达式（3）可知，随机图与构造社团结构各占一半的权重，此时生成网络的社团结构比较模糊，两个社团的分界并不明显.而随着λ 增大到0.9时，网络的社团结构已经非常清晰。

3.小结

笔者通过详细介绍对度进行改进后的随机分块模型，了解其原理，进而分析其生成网络的机制原理.同时，还提供了在运用模型生成网络时，参数的选择方式.最后，通过实验生成网络模型，分析其节点度的特性，并对比分析不同参数值对应的网络社团结构，以便于帮助剖析网络的特征，为其应用于算法测试[3]奠定基础。

【参考文献】

[1]汪小帆.复杂网络理论及其应用[M].北京：清华大学出版社，2006.

[2]胡守信.MATLAB基础及其应用教程[M].北京：科学出版社，2006.

[3]Karrer，B.and M.E.J.Newman.Stochastic block models and community structure in networks.Phys.Rev.E，83（1）：016107（2011）.