基于密度的半监督复杂网络聚类算法

孟凡荣，张可为，朱 牧

（中国矿业大学 计算机科学与技术学院，江苏 徐州221116）

0 引 言

目前，复杂网络聚类算法得到了广泛的研究［1－3］，算法主要包括模块度优化算法［4，5］、 启发式算法［6，7］、 基 于 模 型的算法［8，9］等，文献 ［10］给出了详细的综述。然而，大多数已有的算法都是无监督的学习方式，不能够利用少量的先验知识对复杂网络的聚类进行有效指导。而往往在很多实际应用中，可以获取少量有关社区结构的先验知识，例如类标签或者成对约束信息等，如何利用这些知识指导复杂网络的聚类，并提高社区发现的性能，具有非常重要的意义［11］。

针对上述问题，本文提出一种基于密度的半监督复杂网络聚类算法，以利用少量的先验知识来有效提高复杂网络的聚类性能。本文算法首先采用must－link和cannot－link两种常用的约束对信息来表示先验知识，并根据must－link的传递性质计算并记录所有相互之间满足must－link约束的节点集合；然后，在基于密度的复杂网络聚类算法［12］的基础上，根据所获取的所有的约束关系，在对节点集进行遍历过程中识别并记录节点之间相互连通的关系，并在先验知识的指导下发现网络中隐含的连接信息并进一步修改节点的原有遍历方式，从而发现满足连通性和最大性的社区结构。在若干真实复杂网络上的实验结果表明，新算法相对于其它几种代表性的半监督算法，能够更加有效地提高无监督聚类的性能。

1 密度聚类算法

给定复杂网络G＝ （V，E），V表示节点的集合，E表示边的集合，基于密度的复杂网络聚类算法［12］主要包含如下若干定义：

定义1 节点v的节点结构定义为节点v和其所有邻居节点组成的节点集，记为N（v），如下所示

定义2 节点v和节点w的结构相似度为将两个节点的节点结构进行余弦相似度计算得到的结果，记为Sim（v，w），如下所示

定义3 节点v的近邻节点为节点v的节点结构中所有与v的结构相似度不小于参数ε的节点构成的集合，记为Nε（v），如下所示

定义4 若节点v的近邻节点数目不小于设定的参数μ，则称节点v为核节点，表示为Cε，μ（v），如下所示

定义5 如果节点w属于节点v的近邻节点，而且节点v是核节点，那么v到w是直接结构联通，记为Dirrε，μ（v，w），如下所示

定义6 节点v到节点w结构联通即存在一个节点集，使得节点v与这些节点通过直接结构联通的传递性可以到达节点w。

定义7 结构社区表示算法对网络进行聚类得到的一个社区，这个社区内部的节点之间是结构联通的，并且这个社区包含了所有内部节点的结构联通节点集，即节点数目达到最大。

密度聚类算法遍历样本节点集，通过直接结构联通的传递关系将所有与核节点联系密切的节点都聚到同一个社区中，保证了社区的联通性和最大性，遍历过程中如果节点不是核节点则标记为特殊节点。遍历结束后即完成了对网络的社区划分。

2 半监督密度算法

在实际聚类研究中，往往可以获取少量先验知识，例如类标签或者成对约束信息等，本文选择以约束对信息作为先验知识。其中，must－link和cannot－link是两种常用的约束对信息：must－link表示两者必须隶属于同一个社区，cannot－link表示两者必须隶属于不同的社区［13］。针对普通密度聚类算法无法有效利用先验知识的问题，本文提出了基于密度的半监督复杂网络聚类算法。

2.1 先验知识的表示

定义8 Cm表示所有已知的满足must－link约束的节点对组成的集合，即

定义9 Cc表示所有已知的满足cannot－link约束的节点对组成的集合，即

定义10 TMS表示一个由若干自成集合的元素组成并且每个元素内部的任意两个节点之间满足mustlink约束的集合，即

定义11 TCS表示在已知TMS集合的情况下对Cc集合进行拓展得到的所有满足cannot－link约束的节点对组成的集合。

must－link约束具有对称性和传递性。利用这些性质对Cm集合进行计算，可以发现隐含的must－link约束，整合即可知道所有已知的和隐含的must－link约束对，最后将所有相互之间满足must－link约束的节点集都保存在TMS中。TMS的具体计算步骤见算法1：

算法1：CALTMS（G＝ （V，E），Cm ）输入：V，E，Cm输出：TMS 01 M＝formMustLinkMatrix（）；02for each vertex vinot in TMSdo 03 generate a new set S’；04 if（vj∈V） ＆ ＆ （M（i，j）＝＝1）then 05 add vjnot in TMSto S’；06 add vinot in TMSto S’；07 if（vx∈V） ＆ ＆ （M（x，j）＝＝1）then 08 add vxnot in TMSto S’；09 end if；10 end if；11 add S’to TMS；12end for；

CALTMS用于根据Cm集合计算TMS集合，为聚类过程提供输入。其中，算法第1行用于生成一个n×n维矩阵M，如果节点i和节点j满足 （i，j）∈Cm，则矩阵对应位置的元素为1，否则为0。算法第3－10行用于生成一个集合S’，里面的元素为所有与节点i之间满足must－link约束的节点。所有的子集S’共同构成了TMS集合。

随后，我们根据计算得到的TMS集合来对Cc集合进行拓展，可以得到TCS集合。内部元素为所有已知的和计算得到的满足cannot－link约束的节点对。

2.2 算法描述

算法根据前面获取的所有约束关系，识别并影响节点之间相互连通的关系，从而发现满足连通性和最大性的社区结构，见算法2，这部分是算法的核心部分。

算法2：TMSSCAN （G＝ （V，E），ε，μ，Cc，TMS）输入：V，E，ε，μ，Cc，TMS输出：聚类结果01for each unmarked vertex v∈Vdo 02if Cε，μ（v）then 03generate new cluster U ，U.id＝newid； Q.add（v）；04 while（Q.size＞0）do 05 y＝Q.poll（）；／／取出Q的第一个元素，并删除06 if（y∈cj） ＆ ＆ （cj∈TMS）then 07 for each unmarked or special vertex oin cjdo 08 o.type＝newid； Q.add（o）；09 end for；10 end if；11 R＝ ｛x∈V｜ Dirrε，μ（y，x）｝12 for each x∈Rdo 13 if each vertex pin Q （x，p）（TCSthen 14 x.type＝newid； Q.add（x）；15 end if；16 end for；17 end while；18else 19 v.type＝special；20 end if；21end for；

TMSSCAN开始时默认所有的节点都是未标记的。算法从第1行开始遍历所有的样本节点，第2行用于判断当前节点v是否为核节点，如果是则检索与节点v连接紧密的所有节点，即TMS集合中节点v所在子集的其它节点（6－10行）和节点v的直接结构联通节点 （11行），分析这些节点与当前划分跟TCS集合是否存在矛盾，不矛盾时将节点v和这些节点分配到同一个社区中，存在矛盾则分析下一个与节点v连接紧密的节点，检索结束即得到一个由节点v拓展得到的社区 （3－17行）；如果节点v不是核节点，则将其标记为特殊节点 （19行）。如此将样本节点全部遍历一遍，即可得到最终的聚类结果。

聚类过程中先验知识的指导作用主要体现在如下部分：TMSSCAN的第6－10行用于将所有与当前节点满足mustlink约束的节点都加入到队列中，保证最后能聚到同一个社区；第13行检测能否将当前节点加入队列，使得不将满足cannot－link约束的两个节点聚到同一个社区。如此，算法在对节点集进行遍历时充分考虑了TMS集合和TCS集合，保证了先验知识的有效性。

2.3 复杂度分析

CALTMS用于计算TMS集合，其时间复杂度跟Cm集合有关。考虑最坏的情况，即所有的节点标签信息已知，在构造子集S1’时，将遍历标签信息为第一类的节点，设其时间复杂度为O（a1），设构造子集数为b，则总共时间复杂度为O（a1＋a2＋a3＋…＋ab），其中a1＋a2＋a3＋…＋ab＝n，因此在最坏情况下CALTMS的时间复杂度为O（n）。

TMSSCAN在聚类过程中，需遍历网络中的每个节点。对每个节点v，必须检索其所有邻居节点，其时间复杂度为O（deg（v））。所以最终的时间复杂度为O（（deg（v1）＋deg（v2）＋deg（v3）＋…＋deg（vn））／2），其中deg（v1）＋deg（v2）＋…＋deg（vn）＝2 m，因此TMSSCAN聚类过程的时间复杂度为O（m）。

综上所述，基于密度的半监督复杂网络聚类算法的时间复杂度为O（m＋n）。在对实际网络进行分析时，网络中的边数和节点数大致相当，即m≈n，所以算法时间复杂度可以记为O（m）。可知，本文所提算法的时间复杂度较低，能应用于对大规模复杂网络进行聚类研究。

3 实验分析

实验环境为：处理器Inter（R）Core（TM）2Duo 2.8GHz PC，内存2G，操作系统为 Windows 7，编程环境为Visual Studio 2008C＋＋.Net。

3.1 数 据

为了验证算法的聚类性能，我们在Newman数据中的真实网络上进行了聚类分析，网络的具体信息见表1。

表1 Newman真实网络数据

3.2 方 法

我们用基于密度的半监督复杂网络聚类算法 （SSSCAN）对表1中的数据进行聚类分析，将结果与半监督谱聚类算法 （SS－SP）［13］、基于 Ncut的半监督核K－means算法 （SS－KK）［13］的聚类结果进行了对比。

实验中，我们选择被广为使用的NMI［14］作为算法聚类精度的评价标准，其计算公式如下

式中：N——一个矩阵，Nij——既在类Xi中又在簇Yj中的节点的个数，Ni.——矩阵第i行求和的结果，N.j——矩阵第j列求和的结果。

3.3 结 果

我们分别用SS－SCAN、SS－SP和SS－KK 算法在4个数据集上进行聚类分析，实验结果如图1、图2、图3、图4所示。其中横坐标表示数据中已知标签节点的比例，考虑实际情况中已知比例不会太多的问题，其取值范围为［0，50%］；纵坐标表示聚类结果的NMI值，NMI值越高表示聚类精度越高。

实验表明在使用半监督学习之前 （对应图中已知比例为0的聚类结果），SS－SCAN算法在football数据和karate数据上的聚类精度相比其它两个算法更高，但在其它两个数据上的聚类结果就没有这个现象，说明在使用半监督学习之前，SS－SCAN相比其它两个算法在聚类精度上并没有绝对优势。

使用半监督学习后 （对应图中已知比例不为0的聚类结果），可以发现，SS－SP算法在前3个数据集上的聚类精度比较高，但其波动现象相对比较明显 （这是由于算法利用K－means来对网络提取的特征向量进行聚类，K－means不稳定导致的），且在adjnoun上的聚类精度是最低的；SS－KK算法在football和adjnoun上的聚类精度比较高，在另外两个数据集上的表现相对较差；SS－SCAN算法的聚类精度相比其它两个算法在大多数情况下都是最高的，并且其NMI值随着已知标签比例的增加大致符合线性增长的趋势，表现相对稳定。

同时，我们统计了3个算法对4个数据集进行聚类所消耗的平均时间。在实验中我们发现引入半监督策略对算法本身的运行时间并不会有很大程度的改变，在这里我们只给出算法在各种已知比例情况下对4个数据进行聚类的平均时间，见表2。可知SS－SCAN算法的时间消耗最少。

表2 算法的聚类时间

综上所述，SS－SCAN算法的聚类精度更高，聚类结果更稳定，时间消耗更少，能够更有效的利用先验知识指导聚类。

4 结束语

本文提出了一种基于密度的半监督复杂网络聚类算法，以利用少量的先验知识提高复杂网络的聚类质量。该算法主要包含两个重要组成部分：一是利用少量的must－link和cannot－link两种常用的成对约束信息，发现网络中所有潜在的成对约束，最大化先验知识，以更好的提高聚类质量；二是在基于密度的方法基础上，判断两个节点是否属于同一个社区时，综合考虑了节点之间的可达性和成对约束两方面的因素，从而更加准确地对复杂网络进行有效划分。在若干真实网络上的实验结果表明，本文所提出的算法相对于其它几种代表性的半监督聚类算法，更能够有效利用少量的先验知识，稳定地提高聚类的质量。

［1］Fortunato Santo.Community detection in graphs ［J］.Physics Reports，2010，486 （3－5）：75－174.

［2］ZHAO Yunpeng，Levina Elizaveta，ZHU Ji.Community extraction for social networks ［J］.Proceedings of the National Academy of Sciences of the United States of America，2011，108 （18）：7321－7326.

［3］YANG Bo，LIU Dayou，LIU Jiming，et al.Complex network clustering algorithms ［J］.Journal of Software，2009，20（1）：54－66 （in Chinese）.［杨博，刘大有，LIU Jiming，等.复杂网络聚类方法 ［J］.软件学报，2009，20 （1）：54－66.］

［4］Mucha Peter J，Richardson Thomas，Macon Kevin，et al.Community structure in time－dependent，multiscale，and multiplex networks ［J］.Science，2010，328 （5980）：876－878.

［5］ZHANG X S，WANG R S，WANG Y，et al.Modularity optimization in community detection of complex networks ［J］.Europhysics Letters，2009，87 （3）：38002.

［6］Good Benjamin H，Montjoye Yves Alexandre de，CLAUSET Aaron.Performance of modularity maximization in practical contexts［J］.Physical Review E，2010，81 （4）：046106.

［7］Tantipathananandh Chayant，Tanya Berger Wolf.Constantfactor approximation algorithms for identifying dynamic communities［C］／／New York：Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2009：827－836.

［8］Hofman J M，Wiggins C H.Bayesian approach to network modularity ［J］.Physical Review Letters，2008，100（25）：258701.

［9］Clauset Aaron，Moore Cristopher，Newman M E J.Hierar－chical structure and the prediction of missing links in networks［J］.Nature，2008，453 （7191）：98－101.

［10］Coscia Michele，Giannotti Fosca，Pedreschi Dino.A classification for community discovery methods in complex networks ［J］.Statistical Analysis and Data Mining，2011，4 （5）：512－546.

［11］ZHAO Weizhong，MA Huifang，LI Zhiqing，et al.Efficiently active learning for semi－supervised document clustering［J］.Journal of Software，2012，23 （6）：1486－1499 （in Chinese）.［赵卫中，马慧芳，李志清，等.一种结合主动学习的半监督文档聚类算法 ［J］.软件学报，2012，23 （6）：1486－1499.］

［12］Xu Xiaowei，Yuruk Nurcan，Feng Zhidan，et al.SCAN：A structural clustering algorithm for networks ［C］／／New York：Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining，2007：824－833.

［13］MA Xiaoke，GAO Lin，YONG Xuerong，et al.Semi－supervised clustering algorithm for community structure detection in complex networks［J］.Physica A：Statistical Mechanics and its Applications，2010，389 （1）：187－197.

［14］TANG Lei，WANG Xufei，LIU Huan.Community detection via heterogeneous interaction analysis ［J］.Data Mining and Knowledge Discovery，2012，25 （1）：1－33.