2. 成都信息工程大学 管理学院, 四川 成都 610103;
3. 西南交通大学 信息科学与技术学院, 四川 成都 611756;
4. 北京大学 计算机科学技术研究所, 北京 100871;
5. 哈尔滨工业大学 计算机科学与技术学院, 黑龙江 哈尔滨 150006;
6. Department of Computer Science, Rensselaer Polytechnic Institute, New York, USA
2. School of Management, Chengdu University of Information Technology, Chengdu 610103, China;
3. School of Information Science and Technology, Southwest Jiaotong University, Chengdu 611756, China;
4. Institute of Computer Science and Technology, Peking University, Beijing 100871, China;
5. Department of Computer Science and Technology, Harbin Institute of Technology, Harbin 150006, China;
6. Department of Computer Science, Rensselaer Polytechnic Institute, New York, USA
随着互联网、物联网技术的快速发展,事物之间的联系更加紧密,错综复杂的联系形成了多样、多变、规模庞大的网络,例如人际交往形成的复杂社交网络、蛋白质交互网络、基于地理空间的交通网络、城市路线网络等.上述网络因其结构复杂、网络进化、连接和节点的多样性、多重复杂性融合,被称为复杂网络[1].复杂网络在规模与复杂度上的快速增长,演变成网络大数据[2].在现实网络中,社区重叠是复杂网络大数据中另一重要特征,即,不同社区之间具有重叠的节点.重叠社区的检测对于网络结构分析、社区划分等具有重要研究价值和科学意义.值得注意的是,国家重点基础研究发展计划(973) 和重大科学研究计划将社交网络结构分析的基础研究作为重要支持方向.
复杂网络大数据中,社区发现算法的研究涉及社会学、生物学、计算机等交叉学科,具有广阔的应用前景.例如在生物学方面,社区检测可以从蛋白质、新陈代谢网络中提取信息,帮助了解生命的奥秘.本文的主要研究动机包括:
1) 早期社区发现研究工作很少考虑重叠节点,建立在节点只属于某一社区的假设之上.然而,在网络大数据中,社区之间重叠是其重要结构特征,考虑网络节点的重叠性可以极大地提高算法的准确性;
2) 传统的非重叠社区发现算法已经不能满足对现实网络分析的要求.现有的重叠社区检测算法时间复杂性较高,应用于大规模复杂网络数据时,其劣势相当明显.当网络节点规模上万,节点连接关系更加复杂的情况下,甚至无法对社区进行划分;
3) 现有重叠社区检测算法很难兼顾算法的准确性和实效性.
针对上述不足,本文的主要贡献包括:基于模块度思想和图论知识,应用新的网络模块度更新方法和社区合并方法,采用平衡二叉树对其进行优化,其节点间模块度增量更新算法时间复杂度仅为O(log2(n)),整体算法时间复杂度为O(nlog2(n)),其中,n表示节点的个数;在非重叠网络社区检测算法得到的社区划分基础上,提出了一种新的重叠社区检测算法,降低了每个节点识别的时间代价,算法的复杂度仅为O(n);为该类问题提供一种新的思路,即,将重叠节点的检测作为了一个分类问题进行研究;将所提算法与经典的社区识别算法COPRA算法(clustering overlap propagation algorithm)[3]、SLPA算法(speaker-listener label propagation algorithm)[4]和CONGA算法(cluster-overlap newman girvan algorithm)[5]进行了对比实验,从多角度验证所提方法的性能优势.
1 相关工作复杂网络大数据中,社区发现算法是根据网络的拓扑结构以及节点属性的相似性,将网络进行模块划分的方法,通常情况下,找到这类划分方法精确解是一个NP难问题.按照是否考虑重叠节点划分将社区发现算法分为两类:未考虑重叠节点和考虑重叠节点社区发现算法,主要工作如下.
(1) 未考虑重叠节点的社区发现算法
基于模块度最优思想的凝聚类算法成为目前网络社区挖掘方法的主流,经典算法包括Fast-Newman算法[6]和CNM算法[7]等.Fast-Newman算法基于最大化模块度的贪婪思想,归并能够产生最大模块度增量的两个社区,直到任意两个社区所产生的模块度增量均小于0时终止.Clauset等人[8]提出了CNM算法,对Fast-Newman算法中节点归并操作进行优化,同时采用大根堆等数据结构对算法进行改进.Zhang等人[9]重新设计模块度的求解方法,改进了Fast-Newman算法的更新策略,较好地提高了社区识别的效率.Blondel等人[10]对模块度增量的求解方法进行改进,设计新的模块度增量计算公式,迭代合并社区,取得了良好的社区识别效果. Oliveira等人[11]利用改进的Kuramoto耦合振子同步模型,从动力学因素分析网络,实现了复杂网络中的社区发现.基于硬聚类算法思想,Chen等人[12]提出了一种在初步划分下的重叠社区检测算法,对节点隶属度计算进行改进,优点在于最大化重叠社区划分的模块度,但计算过程复杂度较高,不适用于复杂网络大数据.基于标签传播的社区识别经典算法是未考虑重叠社区检测的硬聚类算法RAK[13],算法通过赋予每个节点一个社区标签,不断在邻接节点间进行传播,最终收敛到一个较好的解.除了上述算法,还有一些社区划分效果较好的算法,如LFM算法[14],通过设定适应度函数,每次以一个节点作为开始,不断扩充自身的社区,使得适应度函数值达到局部最大值,能够较好地检测复杂网络的社区结构.但是由于其适应度函数的选取将会影响社区的大小,使得算法不稳定.Staudt等人[15]基于内存共享的思想提出了并行标签传播算法,对大规模网络数据取得较好的识别效果.
(2) 重叠社区检测算法
Gregory等人对G-N算法进行改进,提出了CONGA算法[5],通过对节点自身进行分裂,在两个分裂节点间添加虚边,所提方案能够较准确地检测重叠社区,但是由于该算法的时间复杂度较高,实际应用价值不高.近年来,研究人员针对RAK改进设计了多种能够检测重叠社区的方法,其中代表性算法包括COPRA[3]及算法SLPA[4]. COPRA算法通过设置参数来确定概率接受准则,进而通过每次传播的标签概率是否满足相应概率接受准则来确定是否接受该标签,当所有标签都无法满足概率接受准则的时候,就随机选取概率最大的标签之一,使得算法能够检测重叠社区.但是由于随机选取标签的原因,将会导致算法收敛性能较差,社区划分的结果不够稳定. SLPA算法增强了标签传播的收敛性能,但是由于要设置不同的概率准则以及参数才能选取相应的标签,导致算法在实际应用过程中需要对不同的网络进行参数调节,适用范围较窄.
为了克服传统社区发现算法复杂度较高等不足,本文提出了一种新的考虑重叠社区检测的大规模复杂网络社区划分方法,在极大地降低算法运行时间复杂度的同时,保证重叠社区检测的准确性.
2 基本概念本节对算法中使用的基本概念进行描述.
定义 1(复杂网络). CN=(V,E),
1) 结构复杂:节点数目巨大,网络结构呈现多种不同特征;
2) 网络进化:节点或连接的产生与消失;
3) 连接多样性:节点之间的连接权重存在差异,且有可能存在方向性;
4) 动力学复杂性:节点集可能属于非线性动力学系统,例如节点状态随时间发生复杂变化;
5) 节点多样性:复杂网络中的节点可以代表任何事物;
6) 多重复杂性融合:上述多重复杂性相互影响,导致更为难以预料的结果.
定义 2(复杂网络大社区). 大社区是复杂网络中节点的集合,社区内部节点连接紧密,社区之间节点连接较为稀疏.随着复杂网络规模增大,社区也不断增大(velocity),社区内节点数目不断增多(volume),社区内部和社区之间的关系变得非常复杂,具备网络大数据的复杂性,即,数据类型的复杂性、数据结构的复杂性和数据内在模式的复杂性,复杂关系中隐藏着有价值的社会关系网交互信息(value).大的社区不断吞并小社区,小社区不断消亡,社区变得更加广阔(variety),此类社区结构称为复杂网络大社区.
定义 3(重叠社区). 重叠社区是网络中节点的集合,社区内节点同时隶属于多个不同的社区,社区内部节点间的联系较为紧密,而属于不同社区的节点之间的联系较为稀疏,此类社区称为重叠社区.
如图 1所示,节点5同时属于社区1和社区2,节点8同时属于社区2和社区3,图中的3个社区被称为重叠社区.
传统的重叠社区检测算法无法高效地对复杂网络中重叠节点进行检测,主要困难在于:传统算法时间性能较差,无法应对节点数目众多以及边信息复杂的网络,当节点规模较大时,往往导致算法无法正常运行.
定义 4(节点度). 已知一个节点数为n、边数为m的复杂网络CN(V,E)中,V表示节点集合,E表示边的集合.如果节点u与节点v中间有边相连,则euv=1;否则,euv=0.节点u的度ku表示为
注意:下文出现的参数n和m均表示网络中节点和边的数量.
定义 5(节点隶属度). 对于重叠网络中节点u和社区c,节点隶属度表征节点对社区的隶属程度,定义为
$B(u,c)=\frac{k_{u}^{c}}{{{k}_{u}}}$ | (1) |
其中,
从图 1可以看出,节点8对社区2和社区3的隶属度分别为0.33和0.67.
定义 6(模块度). 网络的模块度Q定义为[6]
$Q=\sum\limits_{i=1}^{k}{({{e}_{ii}}-a_{i}^{2})}$ | (2) |
$Q=\frac{1}{2m}\sum\limits_{c\in C}{\sum\limits_{u,v\in V}{{{\delta }_{cu}}}}{{\delta }_{cv}}\left( {{A}_{uv}}-\frac{{{k}_{u}}{{k}_{v}}}{2m} \right)$ | (3) |
公式(2) 和公式(3) 等价.公式(2) 中:eii表示在一个社区i内部,连接两个顶点的边数占网络总边数的比例;ai表示与社区i中节点相连,但另一个节点不属于社区i的边数占网络总边数的比例;k表示社区数目.在公式(3) 中,A表示网络的邻接矩阵,ku和kv分别表示节点u和v的度,C表示所有社区构成的集合,m表示网络的总边数.如果节点u在社区c中,则δcu=1;否则,δcu=0.
模块度表征了网络中节点社区划分的精确程度.当一个网络在某种模块划分下的模块度Q达到最大值时,表明网络社区划分达到了最佳.然而,求解在所有网络社区划分状况下的模块度Q是一个NP难题,因此,Newman提出了模块度增量的概念,其意义是:当社区i和社区j进行合并时,将产生的模块度增量定义为[7]
$\Delta Q=2\left( {{e}_{ij}}-{{a}_{i}}\times {{a}_{j}} \right)$ | (4) |
其中,ai=ki/2m,ki表示社区合并后的节点度数,m为网络中边的数量.
3 复杂网络大数据中重叠社区检测算法本文提出的面向复杂网络的重叠社区检测算法(detecting overlapping communities in complex networks,简称DOC)包含两个主要部分.
(1) 基于模块度理论和图论知识,在Fast-Newman算法的基础上设计新的网络模块度更新方法和社区合并方法.为了提高网络大数据挖掘效率,设计平衡二叉树索引模块度增量,得到无重叠的社区;
(2) 根据节点隶属度定义对网络中节点进行分类,对不同隶属度下的节点进行讨论,从而获得重叠节点部分.DOC算法的工作原理如图 2所示.
如图 2所示:DOC算法首先基于大规模复杂网络提取网络信息,形成由节点和边构成的网络;然后,基于Fast-Newman算法,利用新的节点归并方法以及新的数据结构对其进行优化,这一步未考虑重叠节点的情况;再者,利用重叠社区检测算法得到新的社区划分结果;最后,对社区划分的结果可视化输出.
3.1 理论基础本节将通过概率论以及图计算理论介绍重叠社区检测算法的基本思想.利用模块度进行社区划分的基本思路为:如果一个网络的子图中节点之间的连接强度远大于网络随机划分下子图中节点之间连接的强度,那么可以认为该子图可以作为网络的一个社区.通过概率量化节点间的连接强度的过程如下.
对于随机无向图,图中任意两个节点之间具有连接边的概率Pij是
${{P}_{ij}}=\frac{{{k}_{i}}\times {{k}_{j}}}{{{(2m)}^{2}}}$ | (5) |
其中,ki表示节点i的度数,kj表示节点j的度数,m表示图中的边的数量.
对于网络图CN(E,V),对于其中任意一个社区,能够计算出实际社区内部节点连接强度相对于随机划分下社区内部节点间的连接强度的差值,节点间的连接强度反映到概率上的表达形式如下:
${{Q}_{c}}=\sum\limits_{i,j\in c}{\left[ \frac{{{A}_{ij}}}{2m}-{{P}_{ij}} \right]}$ | (6) |
其中,Aij表示在节点i和j之间的邻接关系,如果i和j之间有边连接,则Aij=1;反之,Aij=0.
根据公式(6) ,可以得到基于整个网络的模块度[8]:
$Q=\frac{1}{2m}\sum\limits_{c\in C}{\sum\limits_{u,v\in V}{\left( {{A}_{uv}}-\frac{{{k}_{u}}{{k}_{v}}}{2m} \right)}}$ | (7) |
其中,A表示网络邻接矩阵,ku和kv表示节点u和v的度,C表示所有社区构成的集合,m表示网络边数量.
上述方法仅针对未考虑重叠节点的社区划分,其含义是:对于每一种社区划分方式,模块度越大,越能够证明社区划分方式的合理性.然而,当允许一个节点同时属于多个社区的时候,上述模块度将不再适用.因此,此处引入节点的模糊隶属函数.模糊隶属函数值表示每个特征向量同时属于多个聚类的“某种程度”,区间[0,1]中的隶属度函数相应量化这个程度.可以得到以下基于重叠社区检测的模块度表达式:
$Q=\frac{1}{2m}\sum\limits_{c\in C}{\sum\limits_{u,v\in V}{{{\delta }_{cu}}{{\delta }_{cv}}\left( {{A}_{uv}}-\frac{{{k}_{u}}{{k}_{v}}}{2m} \right)}}$ | (8) |
注意,公式(8) 相对于公式(7) 新增的两个隶属度因子δcv和δcu分别表示节点v和节点u相对于社区c的隶属程度.Nicosia等人[16]通过大量实验对比不同的模糊隶属函数,认为模糊隶属函数使用公式(9) 最为合适.
${{\delta }_{cv}}=\frac{1}{1+\exp (-120\times B(v,c)+60)}$ | (9) |
其中,B(v,c)表示节点v隶属于社区c的隶属度.
基于上述理论基础,可以得到以下推论.
推论 1. 针对某一社区,将其他社区的某一节点u加入该社区后,所产生的重叠社区模块度增量为[8]
$\text{ }\!\!\Delta\!\!\text{ }{{Q}_{ov}}=\sum\limits_{v\in C}{\left[ \frac{{{A}_{uv}}}{2m}-\frac{{{k}_{u}}\times {{k}_{v}}}{4{{m}^{2}}} \right]}$ | (10) |
推论 2. 对于有效重叠社区划分方法,应当满足重叠社区模块度不小于未考虑社区重叠的模块度,即满足:
$\sum\limits_{c\in C}{\sum\limits_{u,v\in V}{{{\delta }_{cu}}{{\delta }_{cv}}\left( {{A}_{uv}}-\frac{{{k}_{u}}{{k}_{v}}}{2m} \right)}}\ge \sum\limits_{c\in C}{\sum\limits_{u,v\in V}{\left( {{A}_{uv}}-\frac{{{k}_{u}}{{k}_{v}}}{2m} \right)}}$ | (11) |
根据推论2,引出本文算法的基本思路:首先,通过传统的未考虑重叠社区的算法获取基本的网络划分;然后,通过最优化重叠社区模块度获得重叠社区节点部分.
3.2 基于模块度的社区划分方法本节将介绍DOC算法的第1个步骤,不考虑社区重叠部分的社区划分方法,通过设计新的节点和边的更新方法,针对复杂网络大数据,利用平衡二叉树数据结构进行优化,通过建立平衡二叉树,对模块度增量建立索引,使得每次算法寻找最大模块度增量的复杂度大为降低,时间复杂度为O(nlog2(n)).下面首先对节点和边的更新算法进行介绍.
Fast-Newman算法在网络中节点i和节点j进行归并后,需要计算当前情况下两两节点归并所产生的模块度增量△Qij.本文针对这一过程进行改进:已知归并的两个社区为i和j,其归并后的新社区编号为k,此时,对于网络任意两个社区p和q,当计算社区p和q归并的模块度增量时,其归并的模块度增量有以下3种情况(节点更新规则).
1) 当社区p和社区i,j均有连接或均无连接时,合并社区p和社区k产生的模块度增量为△Qpk=△Qpi+△Qpj.
证明:
∵由模块度定义可知,模块度增量与合并社区始末的网络社区划分情况有关;
考虑3个社区,即i,j,p合并所产生的模块度增量为△Qijp,则在社区i,j合并为社区k后,社区k和社区p合并所产生的模块度增量公式:△Qpk=Q末-Q始=(△Qijp+Q0)-(△Qij+Q0);
∴△Qpk=△Qijp-△Qij.
∵△Qijp=△Qij+△Qpj+△Qpi;
∴△Qpk=△Qpi+△Qpj.
2) 当社区p仅与社区i有连接时,合并社区p和k产生的模块度增量公式为△Qpk=△Qpi-2apaj.
证明:
∵△Qpk=△Qijp-△Qij=(△Qij+△Qpj+△Qpi)-△Qij且△Qpj=2(epj-apaj)=-2apaj;
∴△Qpk=△Qpj+△Qpi=△Qpi-2apaj.
3) 当社区p仅与社区j有连接时,合并社区p和i产生的模块度增量公式为△Qpk=△Qpj-2apai.
DOC算法利用新的节点和边更新算法以及平衡二叉树,使得每次更新边和节点时不需要计算全部模块度增量.在社区识别时,首先需要对参数初始化,如算法1所示,主要步骤:(1) 计算网络中各节点的度,保存在节点度数向量k中(第1行~第4行);(2) 计算各个节点合并产生的模块度增量,保存在矩阵△Q中(第5行~第9行);(3) 初始化平衡二叉树森林T(见算法2) ,使得每棵平衡二叉树Ti存储了△Qi(第10行),并输出各参数(第11行).
算法 1. 参数初始化.
输入:复杂网络的邻接矩阵A;
输出:各节点度数向量k,△Q矩阵以及初始化平衡二叉树T.
1. k i=0;
2. for i:=1 to n
3. for j:=1 to n
4. ki=ki+Aij;
5. for i:=1 to n
6. for j:=1 to n
7. if (Aij≠0) then
8. continue;
9. △Qij=1/2m-kikj/(2m)2;
10. T=InitialBTree();
11. Outputk,△Q矩阵,T;
算法 2. 建立和更新平衡二叉树森林.
输入:初始△Q矩阵;
输出:存有每行△Q的平衡二叉树森林.
1. for i:=1 to n
2. for j:=1 to log2(n)
3. InsertNode(△Qij);
4. AdjustAVL(Ti);
5. DeleteTree(Tj);
6. for u:=1 to n
7. P=Search(Tu,A(u,j));
8. DeleteNode(P);
算法2的主要步骤如下:
(1) 平衡二叉树森林的建立算法:将△Q矩阵的每一行均插入相应的平衡二叉树中,对平衡二叉树进行平衡调整(第1行~第4行);
(2) 平衡二叉树森林的更新算法:依据△Q矩阵更新平衡二叉树森林.具体操作为:删除第j棵平衡二叉树(第5行),根据节点更新规则更新第i棵平衡二叉树.针对任意平衡二叉树u,根据△Q矩阵中△Qui以及△Quj,依据更新规则更新、删除平衡二叉树中相应值(第6行~第8行).
初始化主要参数之后则进入第2个步骤,非重叠社区的检测,算法如下所示.
算法 3. 非重叠社区检测.
输入:邻接矩阵A,△Q矩阵,n棵平衡二叉树构成的森林F,节点度数向量k;
输出:非重叠社区存储向量集合C.
1. for i:=1 to n
2. Ci=i;
3. while max{DQ}>0 do
4. Merge(Ci,Cj);
5. ki=ki+kj;
6. Update(A);
7. Update(F);
8. Update(△Q);
9. OutputC;
算法3首先将各个节点作为单独社区,即,赋予各个社区相应节点编号(第1行、第2行);从△Q矩阵中查找最大的模块度增量所需合并的两个社区i和j的编号,将对应的两个社区合并(第3行、第4行);更新节点度数向量和邻接矩阵(第5行、第6行),依据△Q矩阵利用新的规则(第3.2节第3段开始讨论的3种情况)更新平衡二叉树(第7行),更新模块度增量矩阵(第8行);重复进行上述步骤,直到最大模块度增量为负数;输出划分后的社区(第9行).
3.3 重叠社区检测算法本节将介绍DOC算法的第2步,即重叠社区检测算法,基于第3.2节初步未考虑重叠社区的社区检测算法的聚类结果,对网络中各个节点进行隶属度讨论,从而获得网络的重叠社区划分.
根据第3.1节中介绍的重叠社区模块度公式(8) ,可以得到结论:当节点对某社区隶属度大于0.55时,其节点相应模糊隶属度函数公式(9) 的值大于0.997 5,接近于1;当节点对某社区的隶属度小于0.4时,其模糊隶属度函数公式(9) 的值小于10-6,接近于0.基于最优化重叠社区模块度的思想,可以通过对节点的隶属度分成3类讨论,最终确定各节点的社区.算法4通过计算节点对社区的隶属度,进而实现重叠节点检测,如下所示.
算法 4. 重叠社区检测.
输入:非重叠社区向量集合C,社区数p;
输出:重叠社区向量集合C′.
1. for i:=1 to p //p表示算法3划分后的社区数量
2. for each v∈Ci //遍历社区Ci中每一个节点
3. for k:=1 to p
4. if k==i then
5. continue;
6. for eachu∈Ck
7. B(v,Ck)=B(v,Ck)+Avu/kv; //计算节点v相对社区Ck的隶属度
8. ifB(v,Ck)>0.55then //对应节点对社区隶属情况1
9. ifvCkthen
10. add this node toCk;
11. else
12. ifB(v,Ck)>=0.4then //对应节点对社区隶属情况2
13. if △Qov>0then
14. add this node toCk;
15. else ifv∈Ckthen
16. separate this node fromCk;
17. else
18 ifv∈Ck THEN //对应节点对社区隶属情况3
19. separate this node fromCk;
20. OutputC′;
算法4中,节点对某社区的隶属进行的讨论分成3种情况.
(1) 当节点对某社区的隶属度大于0.55时:若该社区为原始划分社区,则不必进行操作;若该社区不为原始划分社区,则将该节点加入相应社区;
(2) 当节点对某社区的隶属度介于[0.4,0.55]时,计算节点加入相应社区是否使重叠社区的模块度增加:若增加,则将该节点加入该社区;反之,该社区将不能拥有这一节点作为其社区元素.其中,应用公式(10) 计算该节点加入相应社区所产生的模块度增量;
(3) 当节点对某社区的隶属度小于0.4时,该节点不能作为该社区的元素.
3.4 算法时间复杂度分析为了说明DOC算法具有较好的时间性能,可用于处理网络大数据,本节将分析DOC算法的时间复杂性.首先获取非重叠社区算法:初始化△Q矩阵时间复杂度为O(m);初始化△Q平衡二叉树时间复杂度约为O(nlog(n)),更新平衡二叉树复杂性是O(log(n));选取最大模块度增量进行社区合并的算法时间复杂度为O(nlog2(n)).综合上述步骤,获取非重叠社区算法时间复杂度为O(nlog2(n)).值得注意的是:大多数社区发现算法并未考虑参数初始化过程时间复杂性(本文算法1的第2步~第9步参数初始化的复杂性是O(n2)),为了保证算法可比性,本文忽略参数初始化的时间复杂度.其次检测重叠社区算法:算法对每个节点对不同社区的隶属度进行讨论,通过分析可以得到算法4的时间复杂度为O(n×p2),因为社区的数目p为常数,所以重叠社区检测算法复杂度可粗略估计为O(n).综上,DOC算法的总时间复杂度为O(nlog2(n)+n),近似为O(nlog2(n)).
4 实验分析 4.1 数据集描述为了验证本文所提的重叠社区检测算法社区划分的准确性和时间性能,实验采用不同的复杂网络大数据集进行实验:(1) 使用LFR基准程序生成的人工模拟的大规模复杂网络数据集[17];(2) 从SNAP网站上获取的3个真实社交网络.LFR基准程序是由Lancichinetti等人提出生成人工模拟网络的程序,该程序在生成基准网络的同时生成含有类标的社区结果.本文算法生成网络参数设置见表 1,其中,社区混合参数μ取值范围为(0,1],表征了社区结构的明显程度,参数值越大,说明社区结构越不明显.
本文实验通过LFR基准程序生成了2个基准网络,分别为:
(1) 节点数目为1 000~10 000的10个大规模网络图,其社区混合参数μ=0.3,其社区重叠节点个数为10~100个,节点可归属社区个数为2;
(2) 节点数量为5 000、节点可归属社区个数为2~8个不等的网络.
本文所有算法利用面相对象Java语言编程实现,硬件平台为2.5GHz Intel Core i5的CPU,内存为16GB,运行在Apple的OS X操作系统上.使用的对比算法包括:
(1) 基于标签传播思想的COPRA算法[3]和SLPA算法[4];
(2) 基于分裂思想的CONGA算法[5],对比CONGA各种划分选取最好准确度作为最终结果.
4.2 社区检测准确性分析本节从4个指标对比分析复杂网络大数据社区检测算法的准确性,具体内容如下.
(1) 标准化互信息指标NMI(normalized mutual information)[18].
这一指标对于人工模拟的网络,即已知标准划分情况的网络能够非常好地判断算法的重叠社区检测准确度,其表达式如公式(12) 所示.
$I(A,B)=\frac{-2\sum\nolimits_{i=1}^{{{C}_{A}}}{\sum\nolimits_{j=1}^{{{C}_{B}}}{{{N}_{ij}}\log \left( \frac{{{N}_{ij}}\times N}{{{N}_{i\bullet }}\times {{N}_{\bullet j}}} \right)}}}{\sum\nolimits_{i=1}^{{{C}_{A}}}{{{N}_{i\bullet }}\log \left( \frac{{{N}_{i\bullet }}}{N} \right)+\sum\nolimits_{j=1}^{C{{}_{B}}}{{{N}_{\bullet j}}\log \left( \frac{{{N}_{\bullet j}}}{N} \right)}}}$ | (12) |
其中,CA表示标准社区划分结果,CB为算法所得到的社区划分结果,矩阵N的行对应标准的社区检测结果,矩阵N的列对应算法得到的社区检测结果,第i行的总和记作Ni•,第j列的总和记作N•j.对公式进行分析可知:
· 当算法得到的社区划分结果和标准社区划分结果一致时,NMI指标的值等于1;
· 当算法得到的社区结果完全和标准社区划分相反时,例如划分得到了所有节点在一个社区之中,此时,NMI指标的值将等于0.
图 3的实验分别基于表 2的LFR基准网络B中的B1,B2数据集进行,其中,数据集B1的社区混合参数值为0.1,数据集B2的社区混合参数值为0.3.通过图 3可以得到如下结论.
1) 在节点归属社区个数变化情况下,DOC算法的NMI值最高能达到0.97,在B1数据集上(μ=0.1) 产生的NMI指标平均相对SLPA提高了2.1%,相对于CONGA算法提高了17.9%,相对于COPRA算法提高了12.2%;在B2数据集上(μ=0.3) ,相对于SLPA算法,NMI准确率提高了5.2%,相对于CONGA算法,NMI准确率提高了45.0%,相对于COPRA算法提高了39.5.2%.DOC算法较好的原因在于:在初步检测社区的基础上,对每个节点进行讨论,确保每个节点能够被划分到正确社区,而其他算法未对节点单独进行隶属度分析;
2) 随着社区混合参数的增加,社区结构将不明显,这使得各算法社区检测的能力下降.同时,随着节点归属社区数目的增加,各算法检测的准确下降趋势更明显.这与现实情况相符:当网络社区结构较弱,节点归属社区数目越多,算法对社区检测的难度会增大;
3) 实验结果同样表明:DOC算法在社区结构变化情况下,始终具有较高的社区检测准确率.
(2) 查准率.
查准率表征了社区划分算法正确识别节点占算法识别出节点的比例.图 4实验数据集A节点数从1 000增加到10 000,B1和B2数据集是由LFR基准程序生成的混合参数为0.1和0.3含5 000个节点的数据集.
图 4分别给出在LFR基准程序数据集A,B1,B2下,各种算法的查准率对比结果.查准率越高,说明算法在应用于推荐系统中时具有很好的预测用户喜好的功能.实验结果表明:在社区节点数目不断变化(数据集A)、社区结构明显程度不同及重叠节点所属社区数目变化(数据集B)的情况下,均能够取得较高的查准率.其中:DOC算法在数据集A上相对于SLPA算法的查准率提高了2.1%,相对于CONGA算法提高了40.4%,相对于COPRA算法提高了23.1%;在数据集B1上,相对于SLPA算法,查准率提高了5.2%,相对于CONGA算法提高了36.1%,相对于COPRA算法,在查准率上提高了23.7%;在数据集B2上,相对于SLPA算法,在查准率上平均提高了14.1%,相对于CONGA算法平均提高了52.3%,相对于COPRA算法平均提高了41.9%.原因在于:DOC算法在初步划分的社区基础上增加了对节点进行分类的操作,使得对节点的划分更加精准.
(3) 查全率.
查全率表征了算法给出社区划分后正确识别的节点占所有节点的比率.
图 5表示了在LFR基准程序生成的A,B1,B2数据集下,不同算法的查全率对比结果.实验结果表明:在社区节点数目不断变化(数据集A)、社区结构明显程度不同及重叠节点所属社区数目变化(数据集B)下,DOC算法均具有较高的查准率.其中:在数据集A上,相对于SLPA算法平均提高了6.6%,相对于CONGA算法平均提高了34.6%,相对于COPRA算法,在查全率上平均提高了16.0%;在数据集B1上,相对于SLPA算法平均提高了0.6%,相对于CONGA算法平均提高了40.9%,相对于COPRA算法平均提高了17.8%;在数据集B2上,相对于SLPA算法平均提高了0.2%,相对于CONGA算法平均提高了28.0%,相对于COPRA算法平均提高了27.2%.原因在于:DOC算法是采用了优化后的Fast-Newman算法进行了初步的社区检测,使得算法针对不同网络的考虑更加充分,社区识别更加全面.相对于SLPA以及COPRA算法利用标签传播思想和CONGA算法利用节点分裂思想的算法具有更高的查全率.
(4) 综合指标F-score.
F-score能够描述重叠节点检测的综合准确性,定义如公式(13) 所示.
$F\text{-}score=\frac{2\times recall\times precision}{precision+recall}$ | (13) |
图 6所示实验数据集基于LFR基准程序生成的A,B1,B2数据集生成.DOC算法的F-score值在不同数据集上的平均值均高于0.91.在数据集A上,相对于SLPA算法,F-score平均提高了4.7%,相对于CONGA算法平均提高了37.5%,相对于COPRA算法平均提高了19.7%.在数据集B1上,相对于SLPA算法平均提高了2.8%,相对于CONGA算法平均提高了38.7%,相对于COPRA算法平均提高了20.7%.在数据集B2上,相对于SLPA算法平均提高了7.4%,相对于CONGA算法平均提高了42.1%,相对于COPRA算法平均提高了35.2%.DOC算法的优势得益于应用了新的节点和边的更新策略,提高了算法的查全率.此外,本文针对初步划分的节点重新进行分类处理,使得最终的查准率大大提高.
4.3 社区识别质量分析
网络社区结构和搜索性能与聚类系数密切相关,本文使用其衡量算法在复杂网络大数据中社区识别质量.
定义 7(聚集系数). 用于描述网络的聚集度,计算公式如下.
${{C}_{i}}=\frac{2|{{e}_{jk}}|}{{{k}_{i}}\times ({{k}_{i}}-1)}$ | (14) |
其中,ejk表示节点i的相邻节点j和节点k之间的连接边,ki表示节点i的度.聚集系数C(i)∈[0,1],当C(i)=1时,表示该社区是一个完全图.整个网络的聚集系数(全网CC)是所有节点聚集系数的平均值,即:
$\bar{C}=\frac{1}{n}\sum\limits_{i=1}^{n}{{{C}_{i}}}$ | (15) |
若一个社区内所有节点的平均CC远大于整个网络作为一个社区时所有节点的平均CC,说明所识别出的社区结构是有意义的,进而说明了社区识别质量很高.
以图 7(a)为例进行说明,图 7(b)、图 7(c)的情况类似.图 7(a)显示了CA-GrQc随机选取社区的聚集系数及全网聚集系数对比,其中:社区C1,C2,C4,C5的聚集系数达到1,说明这一社区内部任意一个节点的邻接节点互相之间均有边相联系;C3社区的聚集系数也达到了极高的0.944 4.同时,全网的聚集系数为0.532 0.说明网络的社区特征并不是很明显的情况下,算法仍能较准确地识别网络的社区结构,具有较高的识别质量.
4.4 算法运行时间性能分析
本节将通过对比不同算法在LFR基准数据集上的实验效果来验证本文所提算法的时间性能优势.
图 8表示在LFR基准数据集(数据集A)上DOC算法的运行时间近似线性变化,与本文第3.4节所提的时间复杂度O(nlog2(n))吻合,明显优于传统算法的时间复杂度.其他数据集上的实验结果类似,这里不再赘述.图 8说明,DOC相比于COPRA和SLPA算法在时间性能上有极大的提高.原因在于:DOC算法通过建立平衡二叉树、对模块度增量建立索引,使得每次算法寻找最大的模块度增量的复杂程度降低.因为CONGA算法时间复杂度较高,为O(m2n),最坏情况为O(m3),算法运行时间性能较差,本节实验没有给出算法运行时间.
5 结束语
本文提出了针对复杂网络大数据的重叠社区检测算法,算法基于模块度和图计算的思想,采用了新的节点和边的更新方法,利用平衡二叉树优化经典无重叠社区发现Fast-Newman算法,提高了节点更新的效率.进行大量实验结果后的表明:本文所提出的算法能够准确地检测重叠社区节点,同时极大地降低了算法的时间复杂度.
未来工作包括:将算法应用于为真实世界的各类复杂网络大数据中,提供社区识别服务,进而给用户提供包括兴趣点推荐等多种个性化服务.因为由于网络用户信息的不断更新,设计新算法实现社区的实时检测.此外,将在静态社区检测基础上设计动态网络社区检测算法,提高社区检测算法在实际网络中的应用价值.
[1] | Barabási A, Albert R, Jeong H, Bianconi G. Power-Law distribution of the World Wide Web. Science, 2000, 287(5461): 2115 . [doi:10.1126/science.287.5461.2115a] |
[2] | Wang YZ, Jin XL, Cheng XQ. Network big data:Present and future. Chinese Journal of Computers, 2013, 36(6): 1125–1138 (in Chinese with English abstract). [doi:10.3724/SP.J.1016.2013.01125] |
[3] | Gregory S. Finding overlapping communities in networks by label propagation. New Journal of Physics, 2010, 12(10): 103018 . [doi:10.1088/1367-2630/12/10/103018] |
[4] | Xie JR, Szymanski BK, Liu XM. SLPA:Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In:Proc. of the 2011 IEEE 11th Int’l Conf. on Data Mining Workshops. Washington:IEEE, 2011. 344-349.[doi:10.1109/ICDMW.2011.154] |
[5] | Gregory S. An algorithm to find overlapping community structure in networks. In:Proc. of the European Conf. on Principles of Data Mining and Knowledge Discovery. Berlin, Heidelberg:Springer-Verlag, 2007. 91-102.[doi:10.1007/978-3-540-74976-9_12] |
[6] | Newman MEJ, Girvan M. Finding and evaluating community structure in networks. Physcial Review E, 2004, 69(2): 026111 . [doi:10.1103/PhysRevE.69.026113] |
[7] | Newman MEJ. Fast algorithm for detecting community structure in networks. Physical Review E, 2004, 69(6): 066133 . [doi:10.1103/PhysRevE.69.066133] |
[8] | Clauset A, Newman MEJ, Moore C. Finding community structure in very large networks. Physcial Review E, 2004, 70(6): 066111 . [doi:10.1103/PhysRevE.70.066111] |
[9] | Zhang XW, You HB, Zhu W, Qiao SJ, Li JW, Gutierrez LA, Zhang Z, Fan XN. Overlapping community identification approach in online social networks. Physica A, 2015, 421: 233–428 . [doi:10.1016/j.physa.2014.10.095] |
[10] | Blondel VD, Guillaume JL, Lambiotte R, Lefebvre E. Fast unfolding of communities in large networks. Journal of Statistical Mechanics:Theory and Experiment, 2008, 30(2): 155–168 . [doi:10.1088/1742-5468/2008/10/P10008]×103时间(s)乔少杰等:复杂网络大数据中重叠社区检测算法647] |
[11] | Oliveira JEM, Quiles MG. Communities detection in complex networks using coupled kuramoto oscillators. In:Proc. of the 14th Int'l Conf. on Computational Science and Its Applications. Berlin, Heidelberg: Springer-Verlag, 2014. 85 -90 . |
[12] | Chen DB, Shang MS, Lv ZH, Fu Y. Detecting overlapping communities of weighted networks via a local algorithm. Physica A, 2010, 389(19): 4177–4187 . [doi:10.1016/j.physa.2010.05.046] |
[13] | Raghavan UN, Albert R, Kumara S. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 2007, 76(3): 036106 . [doi:10.1103/PhysRevE.76.036106] |
[14] | Lancichinetti A, Fortunato S, Kertesz J. Detecting the overlapping and hierarchical community structure of complex networks. New Journal of Physics, 2008, 11(15): 19–44 . [doi:10.1088/1367-2630/11/3/033015] |
[15] | Staudt CL, Meyerhenke H. Engineering parallel algorithm for community detection in massive networks. IEEE Trans. on Parallel and Distributed Systems, 2015, 27(1): 171–184 . [doi:10.1109/TPDS.2015.239063] |
[16] | Nicosia V, Mangioni G, Carchiolo V, Malgeri M. Extending the definition of modularity to directed graphs with overlapping communities. Journal of Statistical Mechanics:Theory and Experiment, 2009, 2009(3): P03024 . [doi:10.1088/1742-5468/2009/03/P03024] |
[17] | Lancichinetti A, Fortunato S, Radicchi F. Benchmark graghs for testing community detection algorithm. Physical Review E, 2008, 78(4): 046110 . [doi:10.1103/PhysRevE.78.046110] |
[18] | Danon L, Diaz-Guilera A, Duch J, Arenas A. Comparing community structure identification. Journal of Statistical Mechnics Theroy and Experiment, 2005, 2005(9): P09008 . [doi:10.1088/1742-5468/2005/09/P09008] |
[2] | 王元卓, 靳小龙, 程学旗. 网络大数据:现状与展望. 计算机学报, 2013 , 36(6) : 1125 –1138. [doi:10.3724/SP.J.1016.2013.01125] |