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

摘要

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

主权项

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