基于分形特征的复杂网络社区发现方法

摘要

基于分形特征的复杂网络社区发现方法，基于分形特征的复杂网络社区发现方法，包括离线的静态复杂网络的社区发现的处理和在线动态复杂网络的社区发现的处理两个阶段。本发明充分利用复杂网络的多尺度特征，用重正化过程作为联系不同尺度间的桥梁，从而达到将之前的社区结构信息为新的社区结构发现所用的目的，实现了增量式的社区发现，为研究动态复杂网络的社区结构做了新的尝试，并得到了比较满意的结果。

说明书

技术领域

本发明属于网络社区发现方法技术领域，涉及一种基于分形特征的复杂 网络社区发现方法。

背景技术

现实世界中存在的许多复杂而庞大的系统可以用网络来描述，我们称之 为复杂网络。复杂网络是复杂系统的抽象，复杂系统中的个体是网络中节点， 节点之间的边则是个体之间根据某种规则自然形成或人为构造的某种关系。 现实世界中包含着各种类型的复杂网络，如社会网络、技术网络、生物学网 络、网络中页面之间相互链接而形成的网络、论文合著网络、文献引用网络 等等。这些现实世界中大量的复杂网络是由许多不同类型的节点组合而成， 其中相同的类型节点之间存在的连接比较多，而不同类型节点的连接却相对 较少，复杂网络的这种特性称为社区结构。

研究发现，现实中的复杂网络有三大特征：1.小世界性（Small-world）， 是指虽然复杂网络的规模可能很大，但是其中任意两个结点之间的最短路径 是比较小的。小世界网络同时具有小的特征路径长度（characteristic path  length）和高的聚集系数（clustering coefficient）。2.无标度性（Scale-free）， 是指在复杂网络中结点的度分布服从或者近似服从幂律（power law）分布。 3.自相似性（Self-similarity），是指复杂网络与自身的局部具有近似的相似 性，也就是具有分形（Fractal）特征。为了探索复杂网络的结构特点，进而 了解复杂网络的功能，人们对复杂网络的社区结构进行了广泛的研究，提出 了众多社区发现方法，主要分为四种方法：凝聚方法、分裂方法、优化方法 和模拟方法。在众多方法中这四种方法并不是独立的，一种方法可能会同时 体现多种思想。

分形特征是现实中复杂网络具有的一个特征，根据研究，在具有社区结 构的诸多网络中，最稳定的就是具有分形特征的网络。证实复杂网络的分形 特征会对网络的结构进行调整，所以将复杂网络的分形特征应用于社区发现 具有广阔的前景，是一种新颖的思路。

尽管不少学者目前对复杂网络的分形特征进行了的分析与理论研究。但 是其成果及方法仅仅是对复杂网络的分形特征进行分析和证实，没有提出基 于分形特征的复杂网络社区发现方法。其存在的问题是，复杂网络本质就是 一个复杂的非线性系统，既然分形特征是实际网络中一个重要的性质，那么 其与复杂网络社区结构有什么联系；能不能对复杂网络的社区发现方面的研 究有所帮助等。究其原因，没有重视分形特征不仅能揭示了非线性系统中有 序与无序的统一，而且能未能将确定性与随机性的更好地统一利用等特点， 导致分形的特征用于应用复杂网络社区发现方法仅局限于理论和分析，未能 提出实用的解决复杂网络社区发现方法。

发明内容

本发明的目的在于提供一种基于分形特征的复杂网络社区发现方法，解 决现有复杂网络社区发现方法中存在的及时性问题，满足复杂网络拓扑结构 的动态变化的及时性要求。

本发明的技术方案是，基于分形特征的复杂网络社区发现方法，包括离 线的静态复杂网络的社区发现的处理和在线动态复杂网络的社区发现的处 理两个阶段。

本发明的特点还在于：

第一阶段：离线的静态复杂网络的社区发现的处理，其过程如下：

步骤1、输入复杂网络的拓扑结构G＝(V,E)；复杂网络用无向图G＝(V,E)来 表示，V和E分别为结点和边的集合；

步骤2、初始化；

步骤3、计算相邻结点的距离，重正化距离最小的结点；

步骤4、更新网络；

步骤5、输出结果。

上述步骤2具体为：计算V中每个结点的度，结点n_i的度记为deg_i，表示 网络中连接到结点的边的个数；对E中的每条边设定权值w_ij，若n_i和n_j有一 个度为1，则令其权值为0，其它情况权值为1。令重正化次数k＝0，并令d＝0， d_k＝0，C(d)_k＝0；

上述步骤3具体为：若复杂网络中所有的原始点都已经被重正化过，则 跳至步骤4更新网络，否则继续此步骤；依据式（1）计算所有相邻结点的 距离：

$\left|\right|n_i-n_j\left|\right|=\frac{1}{|{\mathrm{deg}}_i-{\mathrm{deg}}_j|+1}·\min \{{\mathrm{deg}}_i,{\mathrm{deg}}_j\}·w_{\mathrm{ij}},---\left(1\right)$

其中，deg_i，deg_j分别表示结点n_i，n_j的度，min{x,y}表示取较小的一个值。 w_ij表示给边(n_i,n_j)的权值。取所有边中距离的最小值d，将所有距离为d的边 的端点进行重正化。在这里重正化采用的是最多最先处理的原则，即先处理 拥有最短距离边数最多的点，先将此点的相邻最短的边所涉及的点进行重正 化，即将其合并为一个点。重复此过程直到距离为d的边都被处理过。计算 距离：

d_k＝d_k-1+d    （2）

和关联函数C(d)_k：

${C\left(d\right)}_k=\frac{1}{N^2}{\Sigma }_{i,j=1}^{N}H(d-||n_i-n_j|\left|\right)---\left(3\right)$

其中，N为网络中结点的个数，n_i，n_j为网络中的结点。H(y)为阶跃函 数（step function），即

$H(y)\left(\begin{array}{cc}1& y\ge 0\\ 0& y<0\end{array}\right)---\left(4\right)$

令k＝k+1。

上述步骤4具体为：经过步骤2的重正化后，每条边的权值w_ij则按下面 的策略来计算：首先令所有的权值都为1；如果此时n_i和n_j经过上一步重正 化前有s个边相连，则w_ij＝w_ij/s；若n_i和n_j有一个的度为1，且其所代表的点 有m个，即它由m个点重正化而来，则w_ij＝w_ij*m。

上述步骤5为：画图估计复杂网络的分形维数并给出其关联维数的值；

网络的关联维数定义如下：

$D_C=\underset{d\to 0}{\lim }\frac{\ln C\left(d\right)}{\ln d}---\left(5\right)$

1）K个不同的社区{D_i}(i＝1…K)，其中对于$\forall i\ne j,D_i\cap D_j=\phi ;$

2）一系列(C(d),d)点对的值及由此估计出的复杂网络分形维数D_c。

第二阶段：在线动态复杂网络的社区发现的处理：

动态复杂网络的社区发现是指在静态网络基础上，计算随着时间变化的 新增长（演化）的网络；实现过程描述如下：

步骤1、输入复杂网络，用无向图G＝(V,E)来表示，V和E分别为结点和 边的集合；

步骤2、更新网络拓扑结构；

步骤3、去除对复杂网络社区结构没有影响的边变化；

步骤4、调整尺度；

步骤5、结果输出。

上述输入复杂网络，包括：

1）t时刻的复杂网络G(t)＝(V(t),E(t))；

2）t时刻复杂网络的社区结构{D_i(t)}(i＝1…K)，其中对于 $\forall i\ne j,D_i\left(t\right)\cap D_j\left(t\right)=\phi ;$

3）每个社区作为一个结点时复杂网络的结点间的最小距离d_m；

4）t时刻到t+1时刻边的变化：ΔE⁺和ΔE^-，ΔE⁺和ΔE^-分别表示新产生的 边和消亡的边。

上述更新网络拓扑结构，把复杂网络从t时刻到t+1时刻边的变化更新到 t时刻的复杂网络G(t)上，从而得到G(t+1)的拓扑结构，用于后面计算距离时 用。

上述去除对复杂网络社区结构没有影响的边变化，即从ΔE⁺中去除两个 端点在同一个社区D_i(t)中的边，从ΔE^-中去除两个端点在两个社区D_i(t)和D_j(t) 中的边，其中i≠j。

上述调整尺度，对于ΔE⁺和ΔE^-中还剩下的元素所涉及的社区 {D_i(p)(t)}(p＝1…q)，对每个社区内部的结点及边用上面的静态网络方法进行 凝聚，符合下面两种情况之一就停止：凝聚过程中各结点的距离第一次不小 于d_m；社区中的所有结点被凝聚成一个结点。

再调整尺度，对上步的结果进行基于重正化的社区发现过程，直到所有 新加的原始点都被重正化过或者得到合适的社区结构。还一种可能的情况就 是，一个社区分裂成的部分与其它社区结合。这里就需要在实际中先考虑分 裂，然后把分裂后的部分与剩余的社区一起考虑合并的情况。对于这种情况 的处理就是先分裂然后再合并。

上述结果输出，包括t+1时刻复杂网络的社区结构和对复杂网络关联维 数的估计值：

（1）t+1时刻复杂网络的社区结构{D_i(t+1)}(i＝1…L)，其中 $\underset{i=1}{\overset{L}{\cup }}{D}_i(t+1)=V(t+1),$对于$\forall i\ne j,D_i(t+1)\cap D_j(t+1)=\phi$其中V(t+1)由V(t)减去消亡的点再 加上新产生的点而形成；

（2）一系列(C(d),d)点对的值以及由此估计出的复杂网络分形维数D_c。

本发明具有如下有益效果：

1、本发明充分利用现实中复杂网络的分形特征为社区发现服务。以重 正化及其逆过程作为改变尺度的工具，对动态网络的社区结构变化进行了研 究，提出了基于尺度变化的增量式动态网络社区发现方法，并在实际网络上 证实了其可行性。本发明的特点就是充分利用复杂网络的多尺度特征，用重 正化过程作为联系不同尺度间的桥梁，从而达到将之前的社区结构信息为新 的社区结构发现所用的目的，实现了增量式的社区发现，为研究动态复杂网 络的社区结构做了新的尝试，并得到了比较满意的结果。

2、本发明采用分形原理，提出动态增量式的社区发现方法，旨在通过 分形特征技术解决复杂网络社区发现方法、揭示复杂网络的拓扑结构变化规 律和功能重组，更好解决万维网、交通网络、科学合作网络、电力网络、人 际关系网络、细胞神经网络及传染病网络等社区发现方法。尤其是为网络信 息安全提供新思路。

附图说明

图1是本发明基于分形特征的复杂网络社区发现方法中用于估计复杂网 络关联维数的双对数坐标图；

图2是本发明基于分形特征的复杂网络社区发现方法中网络重正化的示 意图；

图3是本发明基于分形特征的复杂网络社区发现方法中复杂网络在凝聚 过程中的不同状态图；

图4是本发明基于分形特征的复杂网络社区发现方法中复杂网络演化的 示意图。

具体实施方式

下面结合附图和具体实施方式对本发明进行详细说明。

基于分形特征的复杂网络社区发现方法，包括离线的静态复杂网络的社 区发现的处理和在线的动态复杂网络的社区发现的处理两个阶段：

第一阶段：离线的静态复杂网络的社区发现的处理，如参照图3，步骤 如下：

步骤1、输入复杂网络的拓扑结构G＝(V,E)；复杂网络用无向图G＝(V,E)来 表示，V和E分别为结点和边的集合；

步骤2、初始化。计算V中每个结点的度，结点n_i的度记为deg_i，表示网 络中连接到结点的边的个数；对E中的每条边设定权值w_ij，若n_i和n_j有一个 度为1，则令其权值为0，其它情况权值为1。令重正化次数k＝0，并令d＝0， d_k＝0，C(d)_k＝0；

步骤3、计算相邻结点的距离，重正化距离最小的结点。重正化 （renormalization）是物理学的一个概念，其定义是为了克服量子场论中的 发散困难，使理论计算得以顺利进行的一种理论处理方法。它的实质是在观 测中改变粗视化（coarsening）程度，借此定量地分析物理量的变化以揭示 某种规律。在复杂网络中，就相当于不断地把小于某个距离的点看成一个点， 直到整个复杂网络都成为一个点。若复杂网络中所有的原始点（指没有被重 正化过的点，即没有被合并过的点）都已经被重正化过，则跳至步骤4，否 则继续此步骤。依据式（1）计算所有相邻结点的距离：

$\left|\right|n_i-n_j\left|\right|=\frac{1}{|{\mathrm{deg}}_i-{\mathrm{deg}}_j|+1}·\min \{{\mathrm{deg}}_i,{\mathrm{deg}}_j\}·w_{\mathrm{ij}},---\left(1\right)$

其中，deg_i，deg_j分别表示结点n_i，n_j的度，min{x,y}表示取较小的一个值。 w_ij表示给边(n_i,n_j)的权值。取所有边中距离的最小值d，将所有距离为d的边 的端点进行重正化。在这里重正化采用的是最多最先处理的原则，即先处理 拥有最短距离边数最多的点，先将此点的相邻最短的边所涉及的点进行重正 化，即将其合并为一个点。重复此过程直到距离为d的边都被处理过。计算 距离：

d_k＝d_k-1+d    （2）

和关联函数C(d)_k：

${C\left(d\right)}_k=\frac{1}{N^2}{\Sigma }_{i,j=1}^{N}H(d-||n_i-n_j|\left|\right)---\left(3\right)$

其中，N为网络中结点的个数，n_i，n_j为网络中的结点。H(y)为阶跃函 数（step function），即

$H(y)\left(\begin{array}{cc}1& y\ge 0\\ 0& y<0\end{array}\right)---\left(4\right)$

令k＝k+1；

步骤4、更新网络。经过步骤2的重正化后，网络的结点个数和边的个 数都发生了变化，因此各个结点的度以及各条边的权值都需要重新计算。度 的大小可以根据边的个数计算出来，每条边的权值w_ij则需要按下面的策略来 计算：首先令所有的权值都为1；如果此时n_i和n_j经过上一步重正化前有s个 边相连，则w_ij＝w_ij/s；若n_i和n_j有一个的度为1，且其所代表的点有m个，即 它由m个点重正化而来，则w_ij＝w_ij*m；

步骤5、输出结果。输出划分出的复杂网络的社区结果，画图估计复杂 网络的分形维数并给出其关联维数的值。网络的关联维数定义如下：

$D_C=\underset{d\to 0}{\lim }\frac{\ln C\left(d\right)}{\ln d}---\left(5\right)$

关联维数方便从实验中直接测定，应用广泛，它是在1983年被提出的。 在本发明的社区发现方法中，将使用关联维数作为复杂网络分形特征的参 数，即分形维数。从式（5）可以看到，与计盒维数类似关联维数也可以用 (C(d),d)在双对数体系下的拟合直线斜率来估计。具体来讲整个方法的结果有 下面两个：

1）K个不同的社区{D_i}(i＝1…K)，其中对于$\forall i\ne j,D_i\cap D_j=\phi ;$

2）一系列(C(d),d)点对的值，并由此按照附图1所示的方法估计出的复 杂网络分形维数D_c。

此方法是一个社区发现的凝聚方法，如果从不同的层次高度将其结果展 示的话，会得到不同的社区结构，这也从另一方面说明了复杂网络社区结构 具有层次性，如附图4所示。

第二阶段：在线动态复杂网络的社区发现的处理；动态复杂网络的社区 发现是指在静态网络基础上，计算随着时间变化的新增长（演化）的网络； 实现过程描述如下：

步骤1、输入复杂网络，用无向图G＝(V,E)来表示，V和E分别为结点和 边的集合；共有4个输入：

1）t时刻的复杂网络G(t)＝(V(t),E(t))；

2）t时刻复杂网络的社区结构{D_i(t)}(i＝1…K)，其中对于 $\forall i\ne j,D_i\left(t\right)\cap D_j\left(t\right)=\phi ;$

3）每个社区作为一个结点时复杂网络的结点间的最小距离d_m；

4）t时刻到t+1时刻边的变化：ΔE⁺和ΔE^-（分别表示新产生的边和消亡 的边）。

步骤2、更新网络拓扑结构。把复杂网络从t时刻到t+1时刻边的变化更 新到t时刻的复杂网络G(t)上，从而得到G(t+1)的拓扑结构，用于后面计算距 离时用。

步骤3、去除对复杂网络社区结构没有影响的边变化。即从ΔE⁺中去除 两个端点在同一个社区D_i(t)中的边，从ΔE^-中去除两个端点在两个社区D_i(t)和 D_j(t)中的边，其中i≠j。复杂网络的社区就是与内部连接密度大而与外部连 接密度小的网络子图。所以容易理解的不会对网络社区造成影响的变化有下 面两种：增加社区内结点之间的边和减少社区间结点之间的边。这两种方式 会使社区更加凝聚，所以不会产生社区的变化。

步骤4、调整尺度，深入社区内部进行凝聚。对于ΔE⁺和ΔE^-中还剩下的 元素所涉及的社区{D_i(p)(t)}(p＝1…q)，对每个社区内部的结点及边用上面的 静态网络方法进行凝聚，符合下面两种情况之一就停止：凝聚过程中各结点 的距离第一次不小于d_m；社区中的所有结点被凝聚成一个结点。这里距离的 计算方法还是采用式（1）的计算办法。这一步所涉及的社区只需要考虑其 内部结点间的联系，并不需要考虑社区间的联系，所以对于每个社区的计算 是独立的，可以使用并行的方法提高处理速度。这一步的结果将把复杂网络 凝聚成了由未分裂的原社区，新加入的结点和分裂社区形成的块混合形成的 一个网络，这个网络的最小距离为d_m，其中这三种元素不一定都有，当然经 过此步骤，上面提到的三种元素都被表示成了结点。可能使某个社区发生分 裂的复杂网络演化。一种情况是社区内部的边消亡，会使得社区内部的密度 减小，从而可能会导致该社区产生分裂；第二种情况是产生的新边只有一个 端点是该社区内部的结点，会增加社区内部结点与外面的联系，从而也有可 能导致该社区产生分裂。

步骤5、再次调整尺度，对上步的结果进行基于重正化的社区发现过程， 直到所有新加的原始点都被重正化过或者得到合适的社区结构。可能使两个 或多个社区产生合并的复杂网络演化。这里的社区也可以表示新增的原始 点，因为从不同的尺度看，社区也是某个尺度下的结点。多个社区合并可以 进一步分解为两个社区先合并再与其它社区合并，从而只需要考虑两个社区 合并的情况就可以了。可能使两个社区合并的复杂网络演化的情况就是使得 两个社区点的联系更密，也就是新增了两个社区之间的边。还一种可能的情 况就是，一个社区分裂成的部分与其它社区结合。这里就需要在实际中先考 虑分裂，然后把分裂后的部分与剩余的社区一起考虑合并的情况。对于这种 情况的处理就是先分裂然后再合并。

步骤6、结果输出。输出结果主要有两个一个是t+1时刻复杂网络的社区 结构，另一个是对复杂网络关联维数的估计值：

（1）t+1时刻复杂网络的社区结构{D_i(t+1)}(i＝1…L)，其中 $\underset{i=1}{\overset{L}{\cup }}{D}_i(t+1)=V(t+1),$对于$\forall i\ne j,D_i(t+1)\cap D_j(t+1)=\phi$其中V(t+1)由V(t)减去消亡的点再 加上新产生的点而形成。

（2）一系列(C(d),d)点对的值以及由此估计出的复杂网络分形维数D_c。

本发明可以得到复杂网络t+1时刻的社区结构，结束时可以得到t+1时刻 的最小距离，和t+1时刻的复杂网络拓扑图，如果有了t+1时刻到t+2时刻的 网络的边的变化量ΔE⁺和ΔE^-，就可以继续得到t+2时刻的复杂网络社区结构， 继续下去就是增量式的含义所在，由前一时候的状态与变化量得到后一时刻 的状态。

本发明提供了一种基于分形特征的复杂网络社区发现方法，利用实际复 杂网络的分形特征及多尺度等特征来服务于社区发现，是一新的思路，实施 例子也证实了此方法的有效性和可行性。

实施例中，选用Zachary空手道俱乐部网络，它是美国一所学校中的空 手道俱乐部所有成员之间的一个网络。该网络由34个结点和78条边组成， 结点代表俱乐部中的每个成员，边表示成员在俱乐部之外的社会联系。Wayne  Zachary在20世纪70年代花了两年时间观察和研究该俱乐部，后来由于内 部的原因，俱乐部产生了分裂，变成了两个俱乐部。由于Wayne Zachary对 该俱乐部进行了详细的调查与研究，所以这个网络就成为了研究社区发现问 题使用频率最高的一个网络。使用这个网络对本发明复杂网络社区发现方法 进行验证。其结果如表1所示：

表1Zachary空手道俱乐部网络上的算法精度

无论从准确率、召回率还是从F-值的统计结果来看，本发明都具有理想 的结果，因为对于整个网络来说只有一个结点被划分到了错误的社区中，所 以本发明的精确度还是比较理想的。

第二个实施例是用来验证针对动态网络的基于尺度变化的增量式动态 网络社区发现方法，选取的实例是美国NCAA（National Collegiate Athletic  Association）橄榄球网络，是搜集的美国大学生体育联赛2000赛季的橄榄球 常规赛比赛记录。在该网络中，结点表示各个参赛的大学球队，以大学的名 字表示，共有115所大学；结点之间的边表示校队之间的常规赛，这些校队 之间共有613场比赛。在现实中这些球队被分成11个不同的赛区，每个赛 区由8到12个球队组成，同一个赛区球队之间的比赛比不同赛区球队之间 的比赛频率要高，赛区内的比赛每队平均是7场，而赛区间的比赛每队平均 是4场。但是值得注意的是赛区间的比赛分布是不均匀的，对于属于不同的 赛区的球队，距离近的之间的比赛要比距离远的之间的比赛要多。这些已知 的社区结构使得该网络常用于对社区发现方法的检测。本发明将该网络分为 了两部分，第一部分为其中的76个结点和其间的426条边，这些结点和边 主要构成了11个赛区中的8个赛区，使用静态方法得到这些点的社区结构。 第二部分为网络中剩余的结点和边，将其用边的变化来表示，即ΔE⁺和ΔE^-， 然后结合第一部分的76个结点的划分结果，及最小距离（在实验中为 8.9344）。这样就构成了第3章中增量算法的输入，结果如表2所示：

表2NACC橄榄球网络上的算法精度

从表中可以看出，虽然在本发明的发现方法中有的赛区的球队个数不太 精确，但是大多数的赛区中，球队还是可以很好的识别出来，总体来说本发 明在这个实际数据集上的效果还是比较令人满意的，平均的准确率达到了 89%，召回率也达到了95%。