一种基于共识社团布谷鸟算法的动态网络聚类方法及系统

技术领域

本发明属于动态网络社团检测技术领域，尤其涉及一种基于共识社团布谷鸟算法的动态网络聚类方法及系统。

背景技术

随着计算机技术的迅猛发展，从复杂网络中发现社团结构在这十几年里得到了广泛研究。复杂网络可以将现实中抽象的复杂系统进行建模，其中节点代表系统中的实体，边代表实体间的联系。复杂网络的社团发现已经在社会网络、信息网络、生物网络中得到了充分的应用。例如，在科学家协作网络中，社团结构表示发表过相同或相似领域的科学家们；在Web页面网络，社团结构表示有着相同或相似主题的一组页面；在蛋白质相互作用网络中，社团结构表示提供相同或者辅助作用的蛋白质集合。寻找这种结构的研究问题称为社团检测(聚类)问题。

社区检测可以转化为对优化问题求最优解，其难度为NP级。因此，许多研究人员将进化算法(EAs)引入到这一技术领域，并开发了一些有前途的解决方案。然而，这些算法只能发现静态网络中的社区。但是，现实世界的网络不总是静态的，而是处于动态变化中。例如，在科学协作网络中，社区是动态发展的，由于科学家对研究兴趣和方向发生改变，相应的社团结构也会发生变化；蛋白质与蛋白质的相互作用随时间和空间而变化，从而导致蛋白质复合物在细胞周期过程中组装和拆卸。随着科学家们逐渐重视事物的动态变化，动态网络在许多领域越来越受欢迎，因为它在为跟踪网络结构的动态变化提供了大量的机会。

进化聚类是目前广泛用于动态网络社团检测的框架。它的主要思想是在一种时间平滑框架下，在每个时间步上生成聚类。这个时间平滑框架假定在一段很短的时间间隔内社团的改变很小，且最好的社团结构应当通过同时考虑当前时刻和前一时刻的社团结构来获得。因此，进化聚类符合动态网络社区检测涉及的两个相互冲突的准则。第一个是快照质量的最大化，它衡量的是当前时刻社团对快照的效率。第二种是时间代价最小化，表示两个聚类在连续时间步长的距离。动态网络中社区结构的检测可表示为一个多目标优化问题(MOP)。为此，提出了一种动态多目标遗传算法(dynamic multiobjective geneticalgorithms,DYNMOGA)[D.Chakrabarti,R.Kumar,and A.Tomkins,“Evolutionaryclustering,”in Proc.ACM SIGKDD Int.Conf.Knowl.Disc.Data Min.,2006,pp.554–560.]，利用遗传算法发现动态网络中的群落，优化了归一化互信息(NMI)[L.Danon,A.Díaz-Guilera,J.Duch,and A.Arenas,“Comparing community structureidentifification,”J.Stat.Mech.Theory Exp.,vol.2005,no.9,2005,Art.no.P09008.]和模块化[M.Girvan and M.E.Newman,“Community structure in social andbiological networks,”Proc.Nat.Acad.Sci.USA,vol.99,no.12,pp.7821–7826,2002.]。第一个目标NMI是信息论中一个众所周知的熵度量，它量化了当前时刻和上一时刻的两个社团结构的相似性。第二个目标，模块化，是快照质量的最大化，它度量社团在当前时间代表网络的程度。

然而，DYNMOGA有一个缺陷。虽然模块化和NMI在每个时刻同时优化，但该算法不能保证社团朝着与上一时刻相似的方向进化。在进化过程中，如果社团发现的解是高度模块化的，但是在进化过程中NMI很差，那么这些解将被保留，因为它们不是非支配解。因此，该算法不能保证新发现的解决方案能够改进NMI。

发明内容

本发明针对现有动态网络聚类方法存在的不能保证新发现的解决方案能够改进归一化互信息的问题，提出一种基于共识社团布谷鸟算法的动态网络聚类方法及系统。

为了实现上述目的，本发明采用以下技术方案：

本发明一方面提出一种基于共识社团布谷鸟算法的动态网络聚类方法，包括：

步骤1：采用标签传播算法得到初始时刻的社团划分，获得社团内共识；

步骤2：从第2个时刻开始，采用基于有序邻居列表的编码方式生成鸟巢群落；

步骤3：采用经过重定义的莱维飞行公式对鸟巢的位置进行更新，按照放弃算子对部分鸟巢进行重建，从整体上完成对群落的更新操作；

步骤4：采用拥挤度距离和非占优排序机制对鸟巢进行排序，经过精英选择策略从群落中保留适应度好的鸟巢取代原有的鸟巢；

步骤5：完成择优操作后，鸟巢对社团内共识进行投票以获得当前时刻的社团间共识，将社团间共识插入到群落当中；

步骤6：重新计算社团内共识用于下一时刻群落的更新，从非占优解中选择knee解作为最优解，输出该时刻所对应的动态网络划分结果，重复上述操作得到每个时刻下的社团结构。

进一步地，所述社团内共识按照如下方式获得：

采用求交集的方法从如下三个解决方案中获得社团的一致性意见：

1)最小KKM的解；2)最小RC的解；3)膝关节knee解决方案；

膝关节knee解决方案定义如下：

式中，KKM和RC是公式(1)中所定义的目标函数，其中KKM和RC的解空间构成目标空间；PS是Pareto最优解集；x是属于PS中的解；KKM(x)和RC(x)是解x的目标函数值；KKM

社团内共识定义为：

intraCC(CR

其中CR

进一步地，所述莱维飞行公式的重定义过程为：

采用映射方式将飞行方式进行重定义，设随机步长

经过重定义后，得到新的位置更新公式，具体如下：

式中u和v是符合正态分布的随机数，

进一步地，所述社团间共识的计算过程包括：

采用支持度作为指标来衡量当前群体中出现共识社区的频率：

给出一个节点集s，则群体是POP＝{p

本发明另一方面提出一种基于共识社团布谷鸟算法的动态网络聚类系统，包括：

初始社团划分模块，用于采用标签传播算法得到初始时刻的社团划分，获得社团内共识；

编码模块，用于从第2个时刻开始，采用基于有序邻居列表的编码方式生成鸟巢群落；

位置更新模块，用于采用经过重定义的莱维飞行公式对鸟巢的位置进行更新，按照放弃算子对部分鸟巢进行重建，从整体上完成对群落的更新操作；

择优模块，用于采用拥挤度距离和非占优排序机制对鸟巢进行排序，经过精英选择策略从群落中保留适应度好的鸟巢取代原有的鸟巢；

投票模块，用于完成择优操作后，鸟巢对社团内共识进行投票以获得当前时刻的社团间共识，将社团间共识插入到群落当中；

网络聚类模块，用于重新计算社团内共识用于下一时刻群落的更新，从非占优解中选择knee解作为最优解，输出该时刻所对应的动态网络划分结果，重复上述操作得到每个时刻下的社团结构。

进一步地，所述社团内共识按照如下方式获得：

采用求交集的方法从如下三个解决方案中获得社团的一致性意见：

1)最小KKM的解；2)最小RC的解；3)膝关节knee解决方案；

膝关节knee解决方案定义如下：

式中，KKM和RC是公式(1)中所定义的目标函数，其中KKM和RC的解空间构成目标空间；PS是Pareto最优解集；x是属于PS中的解；KKM(x)和RC(x)是解x的目标函数值；KKM

社团内共识定义为：

intraCC(CR

其中CR

进一步地，所述莱维飞行公式的重定义过程为：

采用映射方式将飞行方式进行重定义，设随机步长

经过重定义后，得到新的位置更新公式，具体如下：

式中u和v是符合正态分布的随机数，

进一步地，所述社团间共识的计算过程包括：

采用支持度作为指标来衡量当前群体中出现共识社区的频率：

给出一个节点集s，则群体是POP＝{p

与现有技术相比，本发明具有的有益效果：

(1)本发明将共识社团的概念应用到动态网络当中用来优化NMI。从上一时刻中提取社团内共识，可以得到上一步的知识。利用当前时刻的社团对上一时刻的社团内共识进行投票，可以获得代表上一时刻向当前时刻转移的知识信息，即社团间共识。

(2)本发明将基于共识的进化算子与多目标布谷鸟优化(MOPCS)框架相结合，构成一个基于共识的MOPCS(CCMOPCS)，用于发现动态网络中的社区结构。当前时刻的社团可以向与上一时刻相似的方向进化，因为在进化过程中共识社团保持不变。

(3)对合成数据集和真实数据集的实验验证了本发明方法的有效性。与其他四种典型算法的比较表明，本发明方法具有较强的竞争力和良好的应用前景。此外，本发明不需要定义要查找的社团数量的参数，也不需要指定快照和时间成本的权重。因为社团的数量是由表示方法自动确定的。快照和时间成本的权重由基于共识的进化过程决定。

附图说明

图1为本发明实施例一种基于共识社团布谷鸟算法的动态网络聚类方法的流程图；

图2为本发明实施例一种基于共识社团布谷鸟算法的动态网络聚类方法的社团内共识获取示例图；

图3为基于节点邻居有序列表的鸟巢编码方式示例图；

图4为本发明实施例一种基于共识社团布谷鸟算法的动态网络聚类方法的社团间共识获取与应用示例图；

图5为动态网络实例图；

图6为五种算法在Synthetic数据集上的比较曲线图；

图7为五种算法在SYNFIX数据集上的比较曲线图；

图8为四种算法在SYNVAR数据集上的比较曲线图；

图9为四种算法在Cellphone数据集上的比较曲线图；

图10为四种算法在Enron Mail数据集上的比较曲线图；

图11为两种算法在DBLP数据集上的比较曲线图；

图12为CCMOPCS在DBLP数据集上的划分结果图；

图13为CCMOPCS在DBLP数据集上的划分结果图；

图14为CCMOPCS算法在不同数据集中设置多组投票阈值的表现曲线图。

具体实施方式

下面结合附图和具体的实施例对本发明做进一步的解释说明：

如图1所示，一种基于共识社团布谷鸟算法的动态网络聚类方法，包括：

步骤1：采用标签传播算法得到初始时刻的社团划分，获得社团内共识；

步骤2：从第2个时刻开始，采用基于有序邻居列表的编码方式生成鸟巢群落；

步骤3：采用经过重定义的莱维飞行公式对鸟巢的位置进行更新，按照放弃算子对部分鸟巢进行重建，从整体上完成对群落的更新操作；

步骤4：采用拥挤度距离和非占优排序机制对鸟巢进行排序，经过精英选择策略从群落中保留适应度好的鸟巢取代原有的鸟巢；

步骤5：完成择优操作后，鸟巢对社团内共识进行投票以获得当前时刻的社团间共识，将社团间共识插入到群落当中；

步骤6：重新计算社团内共识用于下一时刻群落的更新，从非占优解中选择knee解作为最优解，输出该时刻所对应的动态网络划分结果，重复上述操作得到每个时刻下的社团结构。

具体地，动态网络聚类的过程即为动态社团发现的过程，动态社团发现是在随着时间不断变化的网络中发现与每个时刻网络相对应的社团结构的过程。动态网络社团发现定义如下，给定一个由T个时刻构成的动态网络G＝{G

具体地，本发明的初始化采用了标签传播算法的初始化策略来生成初始时刻的解决方案。与传统的随机初始化方法产生大量冗余的初始解相比，通过标签传播，密集连接的节点组可以在标签传播过程中快速的与对应的标签节点完成划分。同时基于标签传播的算法有着接近线性的时间复杂度，并且每次运行结果因为其随机性都有可能产生不同的结果，因此会得到多组不同的解决方案。

进一步地，所述社团内共识按照如下方式获得：

采用求交集的方法从如下三个解决方案中获得社团的一致性意见：

1)最小KKM的解；2)最小RC的解；3)膝关节knee解决方案；

膝关节knee解决方案定义如下：

式中，KKM和RC是公式(1)中所定义的目标函数，其中KKM和RC的解空间构成目标空间；PS是Pareto最优解集；x是属于PS中的解；KKM(x)和RC(x)是解x的目标函数值；KKM

社团内共识定义为：

intraCC(CR

其中CR

为更好的理解社团内共识，举一个简单地例子。如图2所示，选取三个最具代表性的解决方案来获取社团内共识。CR

进一步地，所述步骤2中的编码方式具体如图3所示。在图3中，详细举例说明鸟巢编码过程。其中图3中(a)是一个简单的网络拓扑结构，图3中(b)是针对每个节点统计的相对应的邻居节点，图3中(c)是一种有效的编码方式，图3中(d)是对应图3中(c)编码方式的解码结构。鸟巢的长度是节点的个数，每个节点对应的编码是它邻居列表中的存在的随机索引值。例如第一维的编码值是4，则解码时需要在节点1的邻居列表中查找第4列所对应的真实节点是节点5，即节点1和节点5相连。最后完成解码时网络被划分成两个分别由5个节点和4个节点构成的社团结构。

进一步地，步骤3中，位置更新操作包括：

在连续求解问题上，布谷鸟基于莱维飞行的选择宿主鸟巢位置更新公式为

其中步长s表示布谷鸟从就鸟巢位置出发到新鸟巢所随机走过的距离，这种随机性保证布谷鸟位置更新时有着较强的全局搜索能力。u和v是符合正态分布的随机数，Γ是gamma函数，定义为

新的鸟巢位置会充分利用原来的位置和莱维飞行操作。但由于这是求解连续问题的，当鸟巢位置是离散型的，每一维都是整数时，原布谷鸟算法中的飞行方式就需要重新定义使其适应求解离散型社团发现问题。本发明采用映射方式将飞行方式进行重定义，设随机步长

经过重定义后，得到新的位置更新公式，具体如下：

其中L

本发明采用的编码方式在公式(9)得到的新位置

具体地，放弃算子是为了模拟布谷鸟的蛋被宿主鸟发现后而新建鸟巢的过程。假设蛋被宿主发现的概率是Pa，Pa越大则布谷鸟的蛋生存的几率越小。因此宿主鸟以Pa概率发现布谷鸟的蛋而建立因鸟巢的算法如下所示：

对鸟巢x中的每一维j，随机生成一个(0,1)之间的随机数p，如果该随机数大于Pa，Pa则寻找和第j个节点相连的所有邻居，在其所有邻居中随机生成一个不同于x

进一步地，所述社团间共识的计算过程包括：

采用支持度作为指标来衡量当前群体中出现共识社区的频率：

给出一个节点集s，则群体是POP＝{p

具体地，如何获得社团间共识和获得社团间共识后如何应用，在图4举例说明。在获得当前时刻的群落(POP

具体地，如下给出一种基于共识社团布谷鸟算法的动态网络聚类方法(简称为CCMOPCC)的具体框架。首先，采用标签传播算法得到初始时刻的社团划分，获得社团内共识。从第2个时刻开始，采用基于有序邻居列表的编码方式生成一定规模的鸟巢群落，之后采用经过重定义的莱维飞行对鸟巢的位置进行更新，按照放弃算子对部分鸟巢进行重建，从整体上完成对群落的更新操作，提高种群的多样性。再采用拥挤度距离和非占优排序机制[K.Deb,P.Amrit,A.Sameer,A fast and Elitist Multiobjective GeneticAlgorithm:NSGA-II[J],IEEE T ransactions on Evol utionary Computation,2002,6(2):182-197.]对鸟巢进行排序，经过精英选择策略从群落中保留适应度较好的鸟巢取代原有的鸟巢。完成择优操作后，鸟巢对社团内共识进行投票以获得当前时刻的社团间共识，将社团间共识插入到群落当中。之后重新计算社团内共识用于下一时刻，从非占优解中选择knee解作为最优解，输出该时刻所对应的网络划分结果，重复上述操作得到每个时刻下的社团结构。

本发明通过不断将知识(社团间共识)从前一时刻转移到当前时刻的步骤，为动态网络的进化聚类框架做出了贡献。与现有文献中的共识不同，本发明中的知识(社团间共识)是用来在进化聚类过程中增强搜索过程的。当完成进化聚类算法的更新步骤后，将可转移的知识(社团间共识)插入到当前群落(POP

值得说明的是，网络的动态性是指网络中的成员之间的互相关系会随着时间的变化而变化。定义一个动态网络G＝{G

为验证本发明效果，进行如下实验：

通过对CCMOPCS方法的结果与4种著名的算法，包括FacetNet[文献1：T.Chakraborty,S.Srinivasan,N.Ganguly,S.Bhowmick,and A.Mukherjee,“Constantcommunities in complex networks,”Sci.Rep.,vol.3,no.1,p.1825,2013.]、MODPSO[文献2：M.Gong,Q.Cai,X.Chen,and L.Ma,“Complex network clustering bymultiobjective discrete particle swarm optimization based on decomposition,”IEEE Trans.Evol.Comput.,vol.18,no.1,pp.82–97,Feb.2014.]、DYNMOGA[文献3：D.Chakrabarti,R.Kumar,and A.Tomkins,“Evolutionary clustering,”in Proc.ACMSIGKDD Int.Conf.Knowl.Disc.Data Min.,2006,pp.554–560.]和Infomap[文献4：R.Agrawal,T.Imielinski,and A.Swami,“Mining association rules between sets ofitems in large databases,”ACM SIGMOD Rec.,vol.22,no.2,pp.207–216,1993.]进行比较，来评价所提出方法的性能。在这4种比较算法中，FacetNet是比较著名的进化聚类算法，MODPSO是用于检测静态网络社团的算法，DYNMOGA是一种基于多目标优化的进化聚类算法，Infomap是常用于检测动态网络的框架。

a、比较算法的参数设置

在本次实验中，参数的设置遵循了文献3和文献1中的建议。其中，FacetNet中参数α根据文献1设置为0.8。DYNMOGA、MODPSO和CCMOPCS的种群规模设置为100，迭代数设置为100。而且DYNMOGA中交叉率设置为0.8，变异率设置为0.2。Infomap中的多个参数根据文献4设置。在CCMOPCS中，投票过程中的最小支持阈值设置为70％，将获得社团间共识插入到群体中，放弃算子中的鸟巢被发现的概率Pa＝0.8。由于每次算法运行得到的解不同，为了保证算法的准确性，在每个数据集独立运行20次，记录结果的平均值进行算法间的比较。

b、在合成网络上的表现

在实验中，将算法在合成网络上测试性能。实验在两个已知划分结果的合成数据集上进行。

Dataset1：为了使合成的数据集更接近真实世界网络的数据，Greene等人[Raghavan Usha Nandini,Albert Réka,Kumara Soundar.Near linear time algorithmto detect community structures in large-scale networks.[J].Physical review.E,Statistical,nonlinear,and soft matter physics,2007,76(3Pt 2).]合成了一个具有四种不同基本事件的数据集。该数据集具备1000个节点，每个节点的平均度是15，其中节点最大度取50。在第一个时刻中，社团的平均数量为33个，社团之间的边所占百分比为0.2。四种事件包括：

(1)出生与死亡：在每个时刻中，10％的社团被建立，通过从已经存在的社团中随机移除10％的节点。

(2)合并与分裂：在每个时刻中，10％的社团进行分裂，其他10％的社团被选中并且两两合并。

(3)扩张与收缩：在每个时刻中，10％的社团被随机选择，然后在原来的大小上扩大或者缩小25％的规模。

(4)间歇性社团：在每个时刻中，10％的社团在此时刻从原始网络中消失，并在下一个时刻中重新出现。实验结果如图6所示。

通过以上四种基本事件，对20个时刻生成4个合成数据集。图6描述五种聚类算法在不同数据集上的NMI比较情况，从中可以看出CCMOPCS算法在四个数据集中的性能最好，FacetNet的NMI随着时刻的增加而显著降低，Infomap的NMI在Intermittent communities数据集随着时刻的增加波动较大，其它数据集较为稳定，MODPSO算法在Expansion andcontraction较为不稳定，说明算法稳定性还有待提高。DYNMOGA和CCMOPCS在四个数据集的20个时刻中NMI的波动较小，说明算法具有稳定性。

Dataset2：在第二种合成网络数据集中，引入在[M.-S.Kim and J.Han,“Aparticle-and-density based evolutionary clustering method for dynamicnetworks,”Proc.VLDB Endow.,vol.2,no.1,pp.622–633,2009.]提出的两种动态网络人工数据集。第一个动态网络数据集是在每一个时刻都有固定社团数量的社团(SYNFIX)，第二个动态网络数据集是在每一个时刻都有可变社团数量的社团(SYNVAR)。

其中，SYNFIX由128个节点组成，共划分了4个社团，每个社团由32个节点组成，节点的平均度为16，节点与网络中的其他社团中的节点之间有Z条边。为了引入动态网络的概念，从前一时刻的每个社团中随机抽取3个节点，并随机添加到三个其他的社团中。SYNVAR是通过添加和删除SYNFIX中的节点来生成的，引入了社团的生成和消失，以及节点的加入和离开。初始网络包含256个节点，被划分为4个社团，每个社团有64的节点。在生成第二个时刻到第五个时刻的网络时，每次从前一个时刻的每个社团中选取8个节点并生成新社团，社团中的节点数量为32。在余下的5个时刻，与上述过程相反。因此，在后动态网络的10个时刻的社团数量是4,5,6,7,8,8,7,6,5,4。此外，社团中每个节点的平均度被设置为该社团大小的一半。同时，在每个时刻，随机删除16个节点同时也要增加16个新节点。因此，在SYNVAR数据集的10个网络中，共涉及到的节点有400个。

为了更详细说明数据集，表1统计了合成数据集的聚类系数c和平均度k，这两个指标均是T时刻网络的平均值。图7，图8是多个聚类算法的实验结果比较。

表1.合成网络数据集的统计特征

图7绘制了五个聚类算法在SYNFIX数据集上的NMI，图8绘制了四个聚类算法在SYNVAR数据集上的NMI，其中数据集都包含Z＝3和Z＝5两种情况。结果表明，FaceNet算法在SYNFIX数据集上的NMI相比其它算法较低，无法得到最好的社团结构。DYNMOGA、Infomap和MODPSO在SYNFIX数据集上有较为接近的NMI，但是随着时刻的增加有着较为轻微的波动，但是在SYNVAR数据集上，这些算法的NMI都有着较为明显的波动。CCMOPCS算法在四个动态网络的数据集上都有着较高的性能，不仅有着较高的NMI并且在时间轴上也有着较为稳定的表现。

c、在真实网络上的表现

以上两个数据集都是人工合成的，其中社团中的节点成员的关系是已知的。下面，本文将CCMOPCS算法应用到三个真实的动态网络：1)Cell phone calls；2)Enron mail；3)DBLP collaboration networks。

1)Cellphone：这个手机数据集是虚拟Paraiso移动成员之间的手机通话动态网络，并在2006年6月运行了10天。在手机通话网络中，将每个成员个体作为节点，成员之间的联系作为边，每一天，一个手机通话网络被构建。该网络中节点共有400个，详细情况看表2。

表2.CELL DATASET的统计信息

其中，T表示时刻，|C|表示社团数，|V|表示节点数，|E|表示边数，|E|*表示两个节点之间不同电话的数量，Z表示平均度。

因为这是真实网络，对真实网络的社团结构是未知的，所以本文采用FacetNet和DYNOMGA的方法，将所有时刻中的网络组合成一个新的网络，然后将新的网络的聚类结果(由Infomap产生)作为基本事实。其中图9是多个聚类算法在Cellphone数据集上的比较情况。

图9描绘所比较算法的性能。该图显示了NMI在时刻上的变化。每一时刻得到的社团结构与真实社区结构之间的NMI被认为是精度。从图9可以看出，CCMOPCS的NMI高于Infomap、MODPSO和DYNMOGA，这证实CCMOPCS的性能更为优越。

2)Enron Mail：这个数据集是1999年至2002年美国Enron公司的电子邮件集合。本实验采用了[Raghavan Usha Nandini,Albert Réka,Kumara Soundar.Near linear timealgorithm to detect community structures in large-scale networks.[J].Physicalreview.E,Statistical,nonlinear,and soft matter physics,2007,76(3Pt 2).]中提供的缩减版本，其中包含大约50000封电子邮件。其中，数据集集中在2001年，分成了12个时刻，每月一个，详细数据看表3。

表3.ENRONDATASET的统计信息

其中，T表示时刻，|C|表示社团数，|V|表示节点数，|E|表示边数，|E|*表示两个节点之间不同邮件的数量，Z表示平均度。

和Cellphone数据集相似，真实的社团结构是未知的。因此采用和Cellphone数据集相同的方法来构建真实的网络社团结构。其中图10是多个聚类算法在Enron Mail数据集的比较情况。

Enron Mail数据集的NMI如图10所示。可以看到，CCMOPCS的NMI整体优于Infomap、MODPSO和DYNMOGA。具体来说，CCMOPCS的平均NMI为0.60，Infomap方法的平均NMI为0.51，MODPSO方法的平均NMI为0.47，DYNMOGA方法的平均NMI为0.42。结果表明，本发明提出的CCMOPCS算法对于邮件网络中动态社区的发现也是有效的。

1)DBLP：DBLP(Digital Bibliography&Library Project)是计算机领域科学文献搜索服务的项目。其中每年代表一个时刻，节点代表作者，链接代表合著论文的协作关系。本文采用了DBLP里2012年到2016年的数据集，详细情况如表4：

表4.DBLPDATASET的统计信息

其中，T表示时刻，|N|表示论文数量，|V|表示节点(作者)数，|E|表示边数(即作者之间的不同合著者的数量)，Z表示平均度。图11显示聚类算法在DBLP数据集上NMI和模块度Q的比较。

和上两个真实数据集一样，该数据集的真实社区结构同样未知，本实验使用两个指标来评估所获得的划分。NMI用于度量两个连续时刻的社团结构之间的相似性，而模块度Q用于度量每个快照的社团结构的质量。图11显示了CCMOPCS和DYNMOGA在五个不同时刻(2012-2016)的表现。CCMOPCS和DYNMOGA在模块度Q上的表现极为接近，说明都能发现明显的社团结构，聚类效果较好。CCMOPCS发现的动态社团结构NMI明显高于DYNMOGA，说明CCMOPCS发现的动态社团结构比DYNMOGA更为稳定。

d、使用共识社团的意义

为了展示共识社团是如何平滑的帮助构建两个时刻的社团结构的，本实施例采用了在DBLP数据集中的两个计算机科学家的社团来进行验证，其中包括有来自香港城市大学的Kay Chen Tan团队和来自新西兰惠灵顿维多利亚大学的Mengjie Zhang团队。该动态社团被CCMOPCS发现如图12所示。

从图12可以看出，图12中(a)是CCMOPCS没有使用社团间共识的聚类结果，图12中(b)是CCMOPCS使用社团间共识的聚类结果。从图12中(a)可以看出，Su Nguyen和MarkJohnston是属于Kay Chen Tan的团队，在右图经过转移上一时刻的社团间共识，Su Nguyen和Mark Johnston被分配到Mengjie Zhang的团队。实际上，Su Nguyen和Mark Johnston是Mengjie Zhang团队的成员，只是和Kay Chen Tan的团队有过合作。

e、使用多目标框架的意义

与只优化模块度的单目标算法相比，多目标布谷鸟算法(如CCMOPCS)生成一组具有不同KKM、RC和knee的解，每个解对应给定网络的一个分区。较小的RC解能够表示社团间的较低互连密度，也就是说可以检测到较大社团，但忽视较小社团。较小的KKM解能够表示社团内的较高内连密度，也就是说可以检测到较小社团，但忽视较大社团。因此使用多目标算法的好处如图13所示。图13给出了三种非支配解所对应的分区的可视化，分别是RC最小解、knee解和KKM最小解。

如图13中(a)所示，最小RC解将网络划分为两个社团，分别是Xin Yao社团和Mengjie Zhang的社团。从图13中(b)可以看出，knee方案进一步将Xin Yao的社团划分为两个社团:Xin Yao社团和Rustam Stolkin社团；将Mengjie Zhang社团划分为两个社团:Mengjie Zhang社团和Kay Chen Tan社团。另一方面，图13中(c)显示最小KKM值的社团划分，则会检测到更多的社团，但这些社团都普遍较小。可以得出结论，这三种解决方案都是合理的分区，但它们揭示了网络在不同层次上的分区。上面的例子说明了CCMOPCS算法可以提供给定网络的层次化社团结构。

f、CCMOPCS中最小投票阈值参数

根据共识社团的框架，需要通过投票机制从上一时刻的社团内共识中得到这个时刻的社团间共识，在这个过程中需要设定一个阈值S来从社团内共识中筛选出社团间共识。接下来，本实验对五种合成网络和三种真实网络中S对CCMOPCS性能的影响用图14表示。

图14给出设置不同阈值S下CCMPOCS在不同网络上的性能。从图14可以看出，将S设置为70％或80％时，CCMPOCS的表现最好。出现这样结果的原因是，低阈值倾向于产生不正确的共识，而高阈值将阻碍所确定的共识。因此，建议将阈值S设置在70％～80％之间。

综上，本发明提出了一种基于共识社团布谷鸟算法的动态网络聚类方法CCMOPCS。在CCMOPCS中，通过提取当前时刻群落中存在的公共社团和前一时刻中群落的公共社团来引入共识社团。然后，在共识社团的基础上，当前时刻的社团结构可以朝着前一时刻结构相似的方向发展，保持连续性。因此，CCMOPCS能够精确地发现动态社团结构。本发明实验研究了CCMOPCS算法在两个合成网络和3个真实网络上的性能。对四种最具代表性的算法进行了大量的实验，结果表明该算法具有较强的竞争力和良好的应用前景。

在上述实施例的基础上，本发明另一方面提出一种基于共识社团布谷鸟算法的动态网络聚类系统，包括：

初始社团划分模块，用于采用标签传播算法得到初始时刻的社团划分，获得社团内共识；

编码模块，用于从第2个时刻开始，采用基于有序邻居列表的编码方式生成鸟巢群落；

位置更新模块，用于采用经过重定义的莱维飞行公式对鸟巢的位置进行更新，按照放弃算子对部分鸟巢进行重建，从整体上完成对群落的更新操作；

择优模块，用于采用拥挤度距离和非占优排序机制对鸟巢进行排序，经过精英选择策略从群落中保留适应度好的鸟巢取代原有的鸟巢；

投票模块，用于完成择优操作后，鸟巢对社团内共识进行投票以获得当前时刻的社团间共识，将社团间共识插入到群落当中；

网络聚类模块，用于重新计算社团内共识用于下一时刻群落的更新，从非占优解中选择knee解作为最优解，输出该时刻所对应的动态网络划分结果，重复上述操作得到每个时刻下的社团结构。

进一步地，所述社团内共识按照如下方式获得：

采用求交集的方法从如下三个解决方案中获得社团的一致性意见：

1)最小KKM的解；2)最小RC的解；3)膝关节knee解决方案；

膝关节knee解决方案定义如下：

式中，KKM和RC是公式(1)中所定义的目标函数，其中KKM和RC的解空间构成目标空间；PS是Pareto最优解集；x是属于PS中的解；KKM(x)和RC(x)是解x的目标函数值；KKM

社团内共识定义为：

intraCC(CR

其中CR

进一步地，所述莱维飞行公式的重定义过程为：

采用映射方式将飞行方式进行重定义，设随机步长

经过重定义后，得到新的位置更新公式，具体如下：

式中u和v是符合正态分布的随机数，

进一步地，所述社团间共识的计算过程包括：

采用支持度作为指标来衡量当前群体中出现共识社区的频率：

给出一个节点集s，则群体是POP＝{p

以上所示仅是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。