基于三角簇多标签传播的复杂网络社区结构挖掘方法

摘要

一种基于三角簇多标签传播的复杂网络社区挖掘方法，包括以下步骤：搜索网络中互不相交的三角簇；为不同三角簇中的节点设置互不相同的标签作为标签传播的起始状态；按照多标签更新规则，对于网络中的所有节点，同步进行标签的传播更新；将更新后得到的标签数组与之前更新得到的标签数组进行比较；如果标签仍在传播，则继续进行更新；如果标签产生振荡，则进行振荡消除处理后再继续进行更新；如果标签不再改变，则停止更新，得到网络中的具有重叠的社区结构。本发明的时间复杂度很低，适用于大规模的复杂网络。此外，本发明可以很好地检测出网络社区结构的重叠部分，并且具有良好的鲁棒性，检测的准确度很高。

说明书

技术领域

本发明涉及的是一种复杂网络领域的方法，具体是一种基于三角簇多标签传 播的复杂网络社区结构挖掘方法。

背景技术

复杂网络是现实世界中复杂系统的一种抽象表现形式，复杂网络中的节点代 表复杂系统中的个体，节点之间的连接则代表系统中个体之间按照某种规则自然 形成或人为构造的一种关系。目前，复杂网络已经广泛应用于表征电力网络、通 信网络、互联网、社交网络等各种复杂系统。

社区结构是复杂网络的一个重要的拓扑特性，整个复杂网络是由若干个社区 结构组成，每个社区结构内部的节点连接非常紧密，而社区结构之间的连接则相 对稀疏。复杂网络的社区结构对应于现实中拥有共同特点的功能单元或组织团体， 例如在互联网中社区结构就是讨论共同话题的一些网站，而在社交网络中的社区 结构就是拥有共同兴趣爱好的人组成的一个团体。因此，通过挖掘复杂网络中的 社区结构来分析网络的特性和功能具有十分重要的现实意义。

复杂网络的社区结构挖掘需要满足两个关键的性质：

第一，复杂度低。复杂网络的规模往往非常庞大，可以包含几千甚至上万个 节点，在这种规模的网络下，如果方法的复杂度较高，那么进行社区结构挖掘的 时间开销将会非常大；

第二，有效的重叠结构检测机制。实际的复杂网络中，社区结构普遍存在重 叠现象，即复杂网络中的一些节点可以同时属于多个社区结构，这就要求社区结 构挖掘方法能够检测出复杂网络中社区结构的重叠部分。

经文献检索发现，M.E.J.Newman和M.Girvan在文章“Community structure in  social and biological networks[J]”（《在社交和生物网络中的社区结构》）(Proc. Natl.Acad.Sci.USA99,7821-7826(2001))（美国科学院院刊）中提出了一种基于 最短路径的社区挖掘方法。该方法首先通过计算网络中任意两点之间的最短路径， 得到整个网络的最短路径表；然后利用该表统计每条边被最短路径通过的次数作 为该边的权值，并移除网络中权值最大的边，之后重新计算整个网络中各条边的 权值；重复以上步骤，直到整个网络被划分为合理的社区结构。该方案的检测精 度不高，方法复杂度较高，并且无法检测具有重叠的社区结构。

再经检索发现，Filippo Radicchi和Claudio Castellano等人在文章“Defining  and identifying communities in networks[J]”（《定义并识别网络中的社区结构》） (Proc.Natl.Acad.Sci.USA101,2658-2663(2004))（美国科学院院刊）中提出了一 种基于局部网络拓扑结构的社区挖掘方案。其方法为：首先分析复杂网络中社区 结构的局部拓扑特点，并将网络中的三角形结构作为网络社区最基本的结构，统 计网络中每条边所从属的三角形结构的数量作为该边的权值；然后，移除网络中 权值最大的边，重新计算整个网络中各条边的权值；重复以上步骤，直到整个网 络被划分为合理的社区结构。该方案考虑到了网络拓扑结构的局部特点，检测精 度有一定的提升，但是仍然无法解决复杂度高和社区结构重叠部分的检测这两个 问题。

再经检索发现，Gergely Palla和Imre Derenyi等人在文章“Uncovering the  overlapping community structure of complex networks in nature and society[J]”（《挖 掘自然和社会网络中具有重叠的社区结构》）(Nature435(7043),814-818(2005)) （自然）中提出了一个基于完全子图的社区结构挖掘方法。对于复杂网络中的每 个节点，首先计算包含该节点的所有完全子图，构建出这些完全子图的重叠矩阵； 然后根据连通性对重叠矩阵进行过滤，从而得到具有重叠的社区结构。该方法虽 然能够挖掘出具有重叠的社区结构，但是由于复杂度太高，并不具有实际的应用 价值。

最后经检索发现，U.N.Raghavan和R.Albert等人在文章“Near linear time  algorithm to detect community structures in large-scale networks[J]”（应用于大规模 网络中社区结构挖掘的一种接近线性时间复杂度的方法）(Phys.Rev.E76, 036106(2007))（物理评论）中提出了一种应用于社区结构挖掘的标签传播方法。 该方案初始化时首先给复杂网络中的每个节点分配一个独立的标签；之后在每次 迭代时都将每个节点的标签更新为其邻居节点中占有比例最大的标签，一直到网 络中所有节点的标签都不再发生改变时停止迭代，此时拥有相同标签的节点就属 于同一个社区结构。由此，就可以划分出复杂网络的社区结构。该方法复杂度很 低，具有接近线性的时间复杂度，可以适用于大规模的复杂网络。但是该方法的 鲁棒性很差，检测精度不高，并且无法检测具有重叠的社区结构。

发明内容

本发明的目的在于针对上述现有技术的不足，提出一个基于三角簇多标签传 播的复杂网络社区结构挖掘方法。其主要思想是首先寻找社区结构的核心部分作 为标签传播的起始状态，之后在标签的更新中采用多标签更新规则，保证社区结 构重叠部分的检测效果。

本发明是通过如下技术方案实现的：

一种基于三角簇多标签传播的复杂网络社区挖掘方法，其特点在于：该方法 包括以下步骤：搜索网络中互不相交的三角簇；为不同三角簇中的节点设置互不 相同的标签作为标签传播的起始状态；按照多标签更新规则，对于网络中的所有 节点，同步进行标签的传播更新；将更新后得到的标签数组与之前更新得到的标 签数组进行比较；如果标签仍在传播，则继续进行更新；如果标签产生振荡，则 进行振荡消除处理后再继续进行更新；如果标签不再改变，则停止更新，得到网 络中的具有重叠的社区结构。

该方法的具体步骤如下：

①为待测的复杂网络G的每个节点赋予一个空标签；

②按下列公式计算每条边e_ij的三角簇系数TC(e_ij)：

TC(e_ij)＝|N(v_i)∩N(v_j)|

其中：N(v_i)是节点v_i的邻居节点的集合，∩是求交集的运算符，|·|是求集合 基数的运算符，i为1、2、3、……，N；

③搜索出三角簇系数最大的边；

④将该边的三角簇中的所有节点赋予一个不同于网络中其他标签的基数为1 的标签；之后将这些节点从网络中删除，得到新的网络G’，

⑤判断是否存在三角簇系数大于0的边，存在，则返回步骤②，否则将此时 网络中所有节点的标签保存为一个标签数组L⁽⁰⁾，作为标签传播的初始状态，进 入步骤⑥；

⑥利用下式同步进行标签的传播更新：

$L_i^{\left(t\right)}=\arg \underset{l}{\max }\underset{v_j\in N\left(v_i\right)}{\Sigma }\delta (L_j^{(t-1)},l)$

$\delta (L_j^{(t-1)},l)=\left(\begin{array}{cc}1,& l\in L_j^{(t-1)}\\ 0,& l\notin L_j^{(t-1)}\end{array}\right)$

其中：是节点v_i进行第t次更新后的标签，t为1以上的正整数，N(v_i)是节 点v_i的邻居节点的集合，是节点v_i的邻居节点v_j在第t-1次更新后的标签， 是求元素l的集合的运算符，所求得的l使得max后所定义的函数取得 最大值。在第t次更新时，利用第t-1次更新得到的标签数组L^(t-1)，对于复杂网 络G中的所有节点按照多标签更新的规则，同步进行标签的传播更新，并保存 至新的标签数组L^(t)；

⑦比较标签数组：将第t次更新得到的标签数组L^(t)与之前t-1次更新得到的 标签数组L⁽¹⁾,L⁽²⁾,…,L^(t-1)进行比较，

当t次的标签数组均不相同，则返回步骤⑥；

当L⁽¹⁾,L⁽²⁾,…,L^(t-2)中存在和L^(t)相同的标签数组，则进入表明更新出现了 振荡，则进行步骤⑧；

当标签数组L^(t-1)和L^(t)相同，则进入步骤⑨

⑧振荡消除处理：假定标签数组L⁽¹⁾,L⁽²⁾,…,L^(t-2)中存在L^(k)和L^(t)相同， 则在标签数组L^(k+1)，…,L^(t)中搜索出所有从第k+1次更新至第t次更新标签发生 过改变的节点，在L^(t)中将这些节点的标签分别替换成不同于网络中其他标签的 基数为1的标签；然后返回步骤⑥；

⑨得到网络的具有重叠的社区结构，网络中拥有相同标签元素的节点属于同 一个网络社区结构，标签基数大于1的节点即为网络社区结构的重叠部分。

对本发明的技术解决方案作如下说明：

1.计算标签传播的初始状态：

对于待测的复杂网络G＝(V,E)，其中V＝{v_i|i＝1,2,...,N}是复杂网络G的 节点集合，v_i表示第i个节点，N为复杂网络中节点的数量， 是复杂网络G的边集合，e_ij＝(v_i,v_j)表示网络中 连接节点v_i和v_j的边，为网络G中的每个节点v_i(i＝1,2,...,N)赋予一个空标签。 首先，计算每条边e_ij(i,j＝1,2,...,N)的三角簇系数；然后，搜索出三角簇系数最 大的边，将该边的三角簇中的所有节点重新设置一个不同于网络中其他标签的基 数为1的标签；之后将这些节点从网络中删除，得到新的网络G'＝(V',E′)；

重复上述过程，直到网络中不存在三角簇系数大于0的边，将此时网络中所 有节点的标签保存为一个标签数组作为标签传播的初 始状态，其中表示节点vi在标签传播初始状态时的标签；

2.标签的传播更新：

在第t次更新时，利用第t-1次更新得到的标签数组L^(t-1)，对于复杂网络 G＝(V,E)中的所有节点按照多标签更新的规则，同步进行标签的传播更新，并 保存至新的标签数组$L^{\left(t\right)}=[L_1^t,L_2^t,...,L_i^t,...,L_N^t],$其中表示节点v_i在第t 次更新后的标签；

3、标签数组比较：

将第t次更新得到的标签数组L^(t)与之前t-1次更新得到的标签数组L⁽¹⁾, L⁽²⁾,…,L^(t-1)进行比较，

当t次的标签数组均不相同，则继续按照步骤2进行标签的传播更新；

当L⁽¹⁾,L⁽²⁾,…,L^(t-2)中存在和L^(t)相同的标签数组，则表明更新出现了振荡， 须进行振荡消除处理，之后再继续按照步骤2进行标签的传播更新；

当标签数组L^(t-1)和L^(t)相同，则表明网络G＝(V,E)中所有节点的标签都不 再发生改变，此时终止标签的传播更新，网络中拥有相同标签元素的节点即属于 同一个网络社区结构，标签基数大于1的节点即为网络社区结构的重叠部分。

所述的计算标签传播的初始状态。对于待测的复杂网络G＝(V,E)，其中 V＝{v_i|i＝1,2,...，N是复杂网络G的节点集合，vi表示第i个节点，N为复杂网 络中节点的数量，E＝{e_ij＝(v_i,v_j)|i,j＝1,2,...,N}是复杂网络G的边集合， e_ij＝(v_i,v_j)表示网络中连接节点v_i和v_j的边，为网络G中的每个节点 v_i(i＝1,2,...N，赋予一个空标签。首先，计算每条边e_ij(i,j＝1,2,...,N)的三角簇系 数；然后，搜索出三角簇系数最大的边，将该边的三角簇中的所有节点重新设置 一个不同于网络中其他标签的基数为1的标签；之后将这些节点从网络中删除， 得到新的网络G'＝(V',E')。重复上述过程，直到网络中不存在三角簇系数大于0 的边。将此时网络中所有节点的标签保存为一个标签数组 作为标签传播的初始状态，其中表示节点v_i在标签传播初始状态时的标签。具体为：

所述的边e_ij的三角簇，是指网络中包含边e_ij的所有三角形组成的拓扑结构。

所述的边e_ij的三角簇系数，是指网络中包含边e_ij的所有三角形的数量，其 计算公式如下：

TC(e_ij)＝|N(v_i)∩N(v_j)|

其中，TC(e_ij)是边e_ij的三角簇系数，N(v_i)是节点v_i的邻居节点的集合，∩是 求交集的运算符，|·|是求集合基数的运算符。

所述的节点v_i的邻居节点，是指网络中和节点v_i之间有连接边的节点。

所述的集合的基数，是指集合中元素的个数。

所述的节点v_i的标签，是一个集合L_i＝{l_ik|k＝1,2，...,K}，其元素l_ik用来 表征节点v_i所属的社区结构的编号，K为集合的基数。如果该标签的基数为1， 则表明节点v_i只属于一个社区结构；如果该标签的基数大于1，则节点v_i同时属 于多个社区结构。

所述的空标签，是指集合为空集的标签，即基数为0的标签。节点拥有的标 签为空标签，则说明该节点不属于任何社区结构。

所述的标签数组，是一个1×N的数组，用于保存网络中所有节点的标签。其 中，N为网络中节点的数量，表示在标签传播初 始状态时所有节点所拥有的标签，为标签传播初始状态时节点v_i所拥有的标 签；表示第t次更新后所有节点所拥有的标签， 为第t次更新后节点v_i所拥有的标签。

所述的标签的传播更新。在第t次更新时，利用第t-1次更新得到的标签数 组L^(t-1)，对于复杂网络G＝(V,E)中的所有节点按照多标签更新的规则，同步 进行标签的传播更新，并保存至新的标签数组其中 表示节点v_i在第t次更新后的标签。具体为：

所述的多标签更新规则为：

$L_i^{\left(t\right)}=\arg \underset{l}{\max }\underset{v_j\in N\left(v_i\right)}{\Sigma }\delta (L_j^{(t-1)},l)$

$\delta (L_j^{(t-1)},l)=\left(\begin{array}{cc}1,& l\in L_j^{(t-1)}\\ 0,& l\notin L_j^{(t-1)}\end{array}\right)$

其中，是节点v_i进行第t次更新后的标签，t为1以上的正整数，N(v_i)是节 点v_i的邻居节点的集合，是节点v_i的邻居节点v_j在第t-1次更新后的标签， 是求元素l的集合的运算符，所求得的l使得max后所定义的函数取得 最大值。

所述的同步进行标签的传播更新，是指第t次更新任意节点v_i的标签只 能由之前t-1次更新得到的标签数组L⁽¹⁾,L⁽²⁾,…,L^(t-1)计算得到，而与第t次更 新已得到的其他任何节点v_j(j≠i)的标签无关。

所述的标签数组比较。将第t次更新得到的标签数组L^(t)与之前t-1次更新得 到的标签数组L⁽¹⁾,L⁽²⁾，…,L^(t-1)进行比较。如果t次的标签数组均不相同，则继 续按照步骤2进行标签的传播更新；如果L⁽¹⁾,L⁽²⁾，…,L^(t-2)中存在和L^(t)相同的 标签数组，则表明更新出现了振荡，须进行振荡消除处理，之后再继续按照步骤 2进行标签的传播更新；如果标签数组L^(t-1)和L^(t)相同，则表明网络G＝(V,E) 中所有节点的标签都不再发生改变，此时终止标签的传播更新，网络中拥有相同 标签元素的节点即属于同一个网络社区结构，标签基数大于1的节点即为网络社 区结构的重叠部分。具体为：

所述的振荡消除，其步骤为：假定标签数组L⁽¹⁾,L⁽²⁾，…,L^(t-2)中存在L^(k)和 L^(t)相同，则在标签数组L^(k+1)，…,L^(t)中搜索出所有从第k+1次更新至第t次更 新标签发生过改变的节点，在L^(t)中将这些节点的标签分别替换成不同于网络中 其他标签的基数为1的标签。

本发明从三个方面提高了标签传播的性能与效果。首先，复杂网络社区结构 的核心结构为三角簇。本发明从网络中划分出不相交的三角簇，并且分配不同的 标签作为标签传播的起始状态，充分利用了复杂网络的拓扑特性，初步构建了社 区结构的基本形状，相比为网络中所有节点分配互不相同的标签作为起始状态的 方法有了很大的优化。其次，本发明引入了多标签更新规则，使得每个节点的标 签传播更新充分利用了邻居节点的标签信息，使得节点的局部信息不会损失，与 随机选择最优标签的更新规则相比，多标签更新规则大大提高了标签传播的鲁棒 性和准确度。最后，采用振荡消除处理对振荡节点的标签重新赋值，较好地解决 了同步更新方式下的振荡问题，彻底消除了异步更新方式中由于节点的更新顺序 而引入的随机性缺陷，并且可以通过并行计算，提高计算效率。

附图说明

图1为本发明的方法流程图。

图2为本方法在空手道俱乐部网络下的标签传播的初始状态示意图。

图3为本方法在空手道俱乐部网络下得到的具有重叠的社区结构示意图。

具体实施方式

下面对本发明的实施例作详细说明，本实施例在以本发明技术方案为前提下 进行实施，给出了详细的实施方式和具体的操作过程，但本发明的保护范围不限 于下述的实施例。

本实施例采用社会网络中的经典数据集Zachary空手道俱乐部网络，该网络 包含34个节点和78条边。具体包括步骤如下：

①为待测的空手道俱乐部网络的每个节点赋予一个空标签；

②按下列公式计算每条边ej的三角簇系数TC(e_ij)：

TC(e_ij)＝|N(v_i)∩N(v_j)|

其中：N(v_i)是节点v_i的邻居节点的集合，∩是求交集的运算符，|·|是求集合 基数的运算符，i为1、2、3、……，N；

③搜索出三角簇系数最大的边；

④将该边的三角簇中的所有节点赋予一个不同于网络中其他标签的基数为1 的标签；之后将这些节点从网络中删除，得到新的网络G’，

⑤判断是否存在三角簇系数大于0的边，存在，则返回步骤②，否则将此时 网络中所有节点的标签保存为一个标签数组L⁽⁰⁾，作为标签传播的初始状态，进 入步骤⑥；

由步骤⑤得到的标签传播初始状态的标签数组L⁽⁰⁾共包含3种不同的非空标 签l₁、l₂和l₃，对应于空手道俱乐部网络中存在的3个互不相交的三角簇，如图 2所示，其中每个标签用一个圆圈表示，不同圆圈内的节点拥有不同的非空标签， 空白的节点表示拥有空标签的节点。

⑥利用下式同步进行标签的传播更新：

$L_i^{\left(t\right)}=\arg \underset{l}{\max }\underset{v_j\in N\left(v_i\right)}{\Sigma }\delta (L_j^{(t-1)},l)$

$\delta (L_j^{(t-1)},l)=\left(\begin{array}{cc}1,& l\in L_j^{(t-1)}\\ 0,& l\notin L_j^{(t-1)}\end{array}\right)$

其中：是节点v_i进行第t次更新后的标签，t为1以上的正整数，N(v_i)是节 点v_i的邻居节点的集合，是节点v_i的邻居节点v_j在第t-1次更新后的标签， 是求元素l的集合的运算符，所求得的l使得max后所定义的函数取得 最大值，在第t次更新时，利用第t-1次更新得到的标签数组L^(t-1)，对于复杂网 络G中的所有节点按照多标签更新的规则，同步进行标签的传播更新，并保存 至新的标签数组L^(t)；

⑦比较标签数组：将第t次更新得到的标签数组L^(t)与之前t-1次更新得到的 标签数组L⁽¹⁾,L⁽²⁾,…,L^(t-1)进行比较，

当t次的标签数组均不相同，则返回步骤⑥；

当L⁽¹⁾,L⁽²⁾,…,L^(t-2)中存在和L^(t)相同的标签数组，则进入表明更新出现了 振荡，则进行步骤⑧；

当标签数组L^(t-1)和L^(t)相同，则进入步骤⑨

⑧振荡消除处理：假定标签数组L⁽¹⁾,L⁽²⁾,…,L^(t-2)中存在L^(k)和L^(t)相同， 则在标签数组L^(k+1)，…,L^(t)中搜索出所有从第k+1次更新至第t次更新标签发生 过改变的节点，在L^(t)中将这些节点的标签分别替换成不同于网络中其他标签的 基数为1的标签；然后返回步骤⑥；

⑨得到网络的具有重叠的社区结构，网络中拥有相同标签元素的节点属于同 一个网络社区结构，标签基数大于1的节点即为网络社区结构的重叠部分。

利用本方法，在第2次更新后得到的标签数组L⁽²⁾和第1次更新后得到的标签 数组L⁽¹⁾相同，所以终止标签的传播更新，得到空手道俱乐部网络的具有重叠的 社区结构，如图3所示。可以看出，空手道俱乐部网络中共存在3个社区结构C₁、 C₂和C₃，分别用一个圆圈表示，圆圈内的节点为该社区结构的成员节点；节点5、 节点10和节点11为社区结构的重叠部分，用黑色的节点表示；社区结构C₁和C₂共同拥有节点5和节点11，社区C₂和C₃共同拥有节点10。

以上实验使用典型网络数据集，对本发明的方法流程进行了详细的说明。该 实验结果与数据集的背景知识基本一致，被划分进入正确社区结构的节点比例达 到了95.59%。此外，模块度是一个用于衡量社区结构优劣的非常重要的指标参数， 经计算本方法在空手道俱乐部网络下得到的社区结构的模块度为0.3912，非常接 近于理论上的最大值0.4020，这也验证了本方法的准确性和有效性。