基于标签传播的半监督社区发现算法研究

魏芳芳 睢世杰 睢世凯

摘 要：近年来，许多关于社区发现的优秀算法被提出并取得了较好的社区划分效果。但是到目前为止，没有任何一种算法能够同时在时间复杂度和准确度方面取得较好的表现。现实网络中往往存在一些有利于指导社区发现的标签信息，如must-link信息、cannot-link信息等。因此提出基于少量标签信息传播、拓扑结构的半监督社区发现算法S_LPA，分别在karate网络、dolphins网络、LFR基准网络上进行测试。实验结果表明，该算法S_LPA时间复杂度为O（m），相对其它算法，S_LPA在karate网络和dolphins网络的NMI值高于CNM、InfoMap、LPA算法，在LRF网络上准确度高出约20%;提高参数u后，S_LPA算法可识别其它算法不能识别的社区结构。

关键词：社区发现; 半监督; 标签信息;标签传播

DOI：10. 11907/rjdk. 191234 开放科学（资源服务）标识码（OSID）：

中图分类号：TP312文献标识码：A 文章编号：1672-7800（2019）007-0092-04

Semi-supervised Community Detection Based on Label Propagation

WEI Fang-fang1，SUI Shi-jie2， SUI Shi-kai3

（1. The Open University of China Information Department，Beijing 100039，China;

2. Fujian Nanwei Software Co.， Ltd.， Fuzhou 350000，China;

3. School of Computer Science and Engineering， University of Electronic Science and Technology of China， Chengdu 610054，China）

Abstract：In recent years， many algorithms about community detection have been proposed and achieved good results， but they belong to unsupervised learning and none of them can play a role in both time complexity and accuracy. In fact， many information in the network， like must-link information or cannot-link information， can help guide the community detection. So we propose the semi-supervised algorithm S_LPA based on label propagation， and combine the small information of the network with the topological structure. The S_LPA verifies that a small amount of label information in the network is helpful to guide community discovery. With the increase of label information， the NMI value increases continuously. The time complexity of S_LPA proposed in this paper is O（m）. Compared with other algorithms， the NMI value of S_LPA in karate networks and dolphins networks is higher than that of CNM， dolphins networks， InfoMap， LPA algorithm， and the accuracy is about 20% higher in LRF network; after improving the parameter u， S_LPA algorithm can also identify community structures that other algorithms can not recognize.

Key Words：community detection; semi-supervised; label information; label propogation

基金項目：国家开放大学校级项目（G18F0023Y）

作者简介：魏芳芳（1991-），女，硕士，国家开放大学信息化部研究实习员，研究方向为网络信息采集与整合。

0 引言

许多复杂系统可以被描述成复杂网络的形式[1-2]。社区结构是网络统计特征的体现。至今还没有关于社区结构的规范性定义，广义上社区结构的特点是不同社区的边连接较少，社区自身的边连接较多 [3]。如何发现有价值的社区结构并应用于复杂网络具有重要意义。国内外关于社区发现的算法很丰富[4-8]。Girvan &Newman[9-10]提出GN算法，该算法通过计算网络各边的边介数，删除网络中边介数最大的边，使算法准确率和复杂度均较高，但如果未知社区个数，则难以确定GN算法终止时间;Xie等[11]提出基于新规则和标签传播的算法LPA，该算法可提高计算效率和社区检测效果;Wu 等[12]提出BMLPA算法，在算法初始化标签时，快速生成粗糙核，对LAP算法进行改进;Liu[13]将标签传播和BRIM算法结合进行社区发现，BRIM算法能够通过在二分网络中递归地诱导两类节点之间的划分，从而生成更好的社区结构;Taher等[14]将公共邻域相似性融入InfoMap算法，得到的加权单模网络可以用随机游走技术进行聚类。

改进的benchmark网络模型LFR benchmark网络更符合真实网络的结构特征，具有社区大小和节点度数不均匀性的特征。图1展示了[n=600]，[=40]，[max（k）=50]，[τ2=2]，[τ1=1]，[u=0.1]，[min（C）=50]，[max（C）=120]的LFR benchmark网络结构。其中[n]为网络节点总数，[]为网络节点平均度，[max（k）]为网络节点最大度，[τ2]为度分布的指数幂，[τ1]为社区大小的指数幂，[u]为混合系数，[min（C）]为社区大小的最小值，[max（C）]为社区大小的最大值[18-19]。

图1 LFR基准网络

3 评价标准

3.1 模块度函数

模块度是评价社区发现算法准确率的重要指标，模块度值越大，社区发现效果越好;模块度值越小，则社区发现效果越差[20-21]。

定义[A]是网络邻接矩阵，[ki]是节点[vi]的度，[m]是边数，则模块度[Q]为两点间边数与随机网络中边数的差值，其计算公式如式（2）所示。

[Q=12mij[Aij-kikj2m]δ（Ci，Cj）]        （2）

[δ（Ci，Cj）]为二值函数，如果节点[vi]和[vj]同属一个社区，则[δ=1]，否则[δ=0]。

令[Bij=Aij-kikj2m]，定义矩阵[D]，其中[Dic]表示节点[vi]是否属于社区[c]，则模块度[Q]如公式（3）所示。

[Q=12mTr（DTBD）]        （3）

如果社区划分效果与随机网络一致，则[Q=0]。如果社区划分效果非常好，则[Q]值偏大。一般而言，[Q]的取值区间为[0.3，0.7]。

3.2 标准化互斥信息

标准化互斥信息代表了网络中两种不同的社区划分差异性，如果从一种社区划分到另一种划分所需的信息量较大，则两个划分差异性比较大;反之，则两个划分差异性较小[18-20]。基于此，本文使用[NMI]作为社区发现算法好坏的评价标准。

假设混合矩阵[N]，其中行表示真实社区，列表示算法发现的社区。[Nij]表示真实社区[ci]与算法发现的社区[cj]中节点交集中节点数目。[NMI]如公式（4）所示。

[NMI（A，B）=-2i=1CAj=1CBNijlog（NijN/Ni.N.j）i=1CANi.log（Ni./N）+j=1CBN.jlog（N.j/N）] （4）

其中，[CA]表示网络中存在的实际社区数，[CB]表示算法发现的社区数，[Ni.]表示[N]中第[i]行的和，[N.j]表示[N]中第[j]列的和，[NMI（A，B）]的变动区间为[0，1]。如果算法发现的社区结构与真实社区结构一致，则[NMI]值趋近于1;反之，[NMI]值趋近于0。

4 实验分析

首先，本文将S_LPA算法在真实网络上进行实验，并与传统CNM算法、InfoMap算法和LPA算法对比。为了衡量社区发现准确度，本文分别采用模块度[Q]值和标准化互斥信息[NMI]作为评价标准。S_LPA初始化时，将随机选择网络中20%的节点对作为先验信息，并标注上must-link先验信息和cannot-link先验信息。本文将LPA算法和S_LPA算法运行10次，以其结果均值作为最终结果，如图4所示。

图2 真实网络社区发现实验结果

从图2可以看出，如果以模块度值[Q]作为社区发现准确度衡量标准，以上4种算法均可很好地识别出网络社区结构。而基于模块度优化的CNM算法准确度最高，其[Q]值远远高于其它几种算法。但也可以看出，虽然S_LPA算法的[Q]值不是最高，但也可以得到一个较好的社区划分结果。如果以标准化互斥信息[NMI]作为社区发现准确度评价标准，S_LPA算法准确度明显高于其它几种算法。[NMI]作为衡量真实社区结构与算法找到的社区结构间差异的标准，更能反映算法优劣。所以总的来说，S_LPA算法在真实网络上的社区发现效果优于其它几种算法。

其次，本文将S_LPA算法在LFR 基准网络上进行实验，并与传统CNM算法、InfoMap算法和LPA算法对比。由于在生成LFR 基准网络的过程中，每个节点均有自己的社区归属，本文将[NMI]作为社区发现的准确度评价标准。在实验过程中，将产生混合系数[u]从0.1到0.9的9组数据集测试网络，其中[u]值越大代表网络社区结构越不明显。在S_LPA起始阶段，本文将随机选择网络20%的节点对作为先验信息，并为其随机标上must-link先验信息和cannot-link先验信息。由于LPA算法和S_LPA算法的随机性，本文分别将LPA算法和S_LPA算法运行10次，并将其结果计算平均值作为最终社区发现结果，实验结果如图3所示。

图3 LFR基准网络上的实验结果

从图3可以看出，当[u0.8]时，网络社区结构不明显，LPA算法和CNM算法均不能很好地识别出网络社区结构，而S_LPA算法和InfoMap算法却有不错的表现。但当[u]值很小时，尤其是当[u=0.1]时，网络社区结构非常明显，但InfoMap社区发现准确度不高。故在LFR 基准网络测试中，S_LPA算法社区发现准确度高于其它3种算法。

网络中少量标签信息能够有效指导社区发现过程。为验证少量标签信息的作用，本文将S_LPA算法在社区结构不明显、[u=0.9]的LFR 基准网络上进行实验，并将网络中含有先验信息的节点比例从0%逐渐增大至30%。从图4可以看出，随着网络中含有先验信息的节点比例增大，社区发现准确度NMI值逐漸增大，所以可以得出网络中少量标签信息可有效指导社区发现过程的结论。

图4 NMI随标签信息增加变化的量

5 结语

本文提出半监督社区发现算法S_LPA，验证了网络中少量标签信息有助于指导社区发现的设想。随着标签信息增多，NMI值不断增大;相对其它算法，S_LPA算法在karate网络和dolphins网络的NMI值均高于CNM、InfoMap、LPA算法，在LRF网络上准确度高出约20%;提高参数u后，S_LPA算法可识别出其它算法不能识别的社区结构。因此该算法具有较强的适用性，尤其是对于社区结构不明显的网络，S_LPA依然可进行有效识别。

参考文献：

[1] HARENBERG S，BELLO G，GJELTEMA，et al. Community detection in large-scale networks： a survey and empirical evaluation[J]. Wiley Interdisciplinary Reviews Computational Statistics，2015，6（6）：426-439.

[2] WANG T， QIAN X， WANG X. Label propagation based community detection algorithm with dpark[C]. International Conference on Computational Social Networks， 2015：116-127.

[3] LU Z， SUN X， WEN Y， et al. Algorithms and applications for community detection in weighted networks[J]. IEEE Transactions on Parallel & Distributed Systems， 2015， 26（11）：2916-2926.

[4] XIE J， KELLEY S， SZYMANSKI B K. Overlapping community detection in networks： the state-of-the-art and comparative study[J]. ACM Computing Surveys （CSUR）， 2013， 45（4）：1-35.

[5] 潘潇，王斌君. 基于社交网络的犯罪团伙发现算法研究[J]. 软件导刊，2018，17（12）：77-80+86.

[6] 李卫疆，谢志勇，余正涛. 一种基于节点相似度的标签传播算法[J]. 软件导刊，2018，17（02）：63-67.

[7] 赵中英，李超. 大数据环境下复杂社会网络的社区发现方法研究综述[J]. 软件导刊，2016，15（12）：164-167.

[8] 沈海燕，李星毅. 一种新的基于标签传播的重叠社区发现算法[J]. 软件导刊，2015，14（04）：59-62.

[9] EATON E，MANSBACH R. A spin-glass model for semi-supervised community detection[C]. Twenty-Sixth AAAI Conference on Artificial Intelligence，2012：900-906.

[10] ZHANG Z Y，SUN K D，WANG S Q. Enhanced community structure detection in complex networks with partial background information[J]. Scientific Reports，2013，3（11）：32-41.

[11] XIE J，SZYMANSKI B K. Community detection using a neighborhood strength driven label propagation algorithm[C]. IEEE Network Science Workshop，2011：1-8.

[12] WU Z H，LIN Y F，Gregory S，et al. Balanced multi-label propagation for overlapping community detection in Social Networks[J].  Journal of Computer Science and Technology，2012，27（3）：468-479.

[13] LIU X，MURATA T. Community detection in large-scale bipartite networks[J].  Transactions of the Japanese Society for Artificial Intelligence， 2010， 1（1）：50-57.

[14] ALZAHRANI T，HORADAM K J，BOZTAS S. Community detection in bipartite networks using random walks[C].  Proceedings of the 5th Workshop on Complex Networks CompleNet， 2014：157-163.

[15] WU Z， LIU Y， NIU J. A novel graph-based method to study community evolutions in social interactions[C]. 2015 IEEE Conference on Ubiquitous Intelligence and Computing ， 2016：62-67.

[16] XIE J， SZYMANSKI B K. Towards linear time overlapping community detection in social networks[C]. Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining， 2012：25-36.

[17] HUANG Z， WANG Z， ZHANG Z. Detecting overlapping and hierarchical communities in complex network based on maximal cliques[C]. Chinese National Conference on Social Media Processing， 2015：184-191.

[18] ZHANG P. Evaluating accuracy of community detection using the relative normalized mutual information[J]. Computer Science， 2015（11）：1-7.

[19] 杨晓波，陈楚湘，王至婉. 基于节点相似性的LFM社团发现算法[J]. 复杂系统与复杂性科学，2017，14（3）：85-90.

[20] 睢世凯，基于局部标签信息的半监督社区发现算法研究[D]. 成都：电子科技大学，2015.

[21] 陈东明，王云开，黄新宇，等. 基于社团密合度的复杂网络社团发现算法[J]. 東北大学学报：自然科学版，2019，40（2）：186-191.

（责任编辑：江 艳）