计算机应用   2017, Vol. 37 Issue (11): 3085-3089  DOI: 10.11772/j.issn.1001-9081.2017.11.3085
0

引用本文 

陈嶷瑛, 柴变芳, 李文斌, 贺毅朝, 吴聪聪. 基于迭代框架的主动链接选择半监督社区发现算法[J]. 计算机应用, 2017, 37(11): 3085-3089.DOI: 10.11772/j.issn.1001-9081.2017.11.3085.
CHEN Yiying, CHAI Bianfang, LI Wenbin, HE Yichao, WU Congcong. Semi-supervised community detection algorithm using active link selection based on iterative framework[J]. Journal of Computer Applications, 2017, 37(11): 3085-3089. DOI: 10.11772/j.issn.1001-9081.2017.11.3085.

基金项目

国家自然科学基金资助项目(61503260)

通信作者

陈嶷瑛, 电子邮箱 mrs.cyy@163.com

作者简介

陈嶷瑛(1971-), 女, 湖南宁远人, 教授, 博士, 主要研究方向:社区发现、机器学习;
柴变芳(1979-), 女, 山西运城人, 副教授, 博士, 主要研究方向:复杂网络分析、概率图模型、机器学习、社区发现;
李文斌(1974-), 男, 江西南昌人, 教授, 博士, CCF高级会员, 主要研究方向:机器学习、复杂网络分析;
贺毅朝(1969-), 男, 河北晋州人, 教授, 硕士, CCF高级会员, 主要研究方向:智能计算、组合优化、算法理论;
吴聪聪(1975-), 女, 河北唐山人, 讲师, 硕士, 主要研究方向:智能计算、信息检索

文章历史

收稿日期:2017-05-16
修回日期:2017-06-05
基于迭代框架的主动链接选择半监督社区发现算法
陈嶷瑛, 柴变芳, 李文斌, 贺毅朝, 吴聪聪    
河北地质大学 信息工程学院, 石家庄 050031
摘要: 针对非负矩阵分解(NMF)半监督社区发现方法随机选择先验约束,导致提升相同性能需要更多约束信息的问题,提出一种基于迭代框架的主动链接选择半监督社区发现算法——ALS_GNMF。在迭代框架下,首先,主动选择不确定性高且对社区划分指导性强的链接对作为先验信息;其次,为主动选择的链接对增加must-link约束,增强社区间连接,生成先验矩阵;同时,增加cannot-link约束,减弱社区间连接,修改邻接矩阵;最后,将先验矩阵作为正则项,加入基于NMF的最优化目标函数,并融合网络拓扑结构信息,以期用较少的先验信息,达到较高的社区发现准确性和鲁棒性。实验结果表明,ALS_GNMF算法在真实网络及人工网络上,相同的先验比例下,性能比未采用迭代框架和主动策略的NMF半监督社区发现方法有更大的提升,且在结构不清晰的网络中表现稳定。
关键词: 半监督学习    主动链接选择    社区发现    非负矩阵分解    
Semi-supervised community detection algorithm using active link selection based on iterative framework
CHEN Yiying, CHAI Bianfang, LI Wenbin, HE Yichao, WU Congcong     
School of Information Engineering, Hebei GEO University, Shijiazhuang Hebei 050031, China
Abstract: In order to solve the problem that large amounts of supervised information was needed to achieve satisfactory performance, owing to the implementation of the semi-supervised community detection methods based on Non-negative Matrix Factorization (NMF) which selected prior information randomly, an Active Link Selection algorithm for semi-supervised community detection based on Graph regularization NMF (ALS_GNMF) was proposed. Firstly, in the iteration framework, the most uncertain and informative links were selected actively as prior information links. Secondly, the must-link constraints of these links, which generated the prior matrix, were added to enhance the connections in a certain community. At the same time, the cannot-link constraints were added, which modified the adjacency matrix, to weaken the connections between communities. Finally, the prior matrix was used as a graph regularization term to incorporate into the optimization objective function of NMF. And combining with network topology information, higher community discovery accuracy and robustness were achieved with less prior information. At the same prior ratio on both synthetic and real networks, experimental results demonstrate that the ALS_GNMF algorithm significantly outperformes the existing semi-supervised NMF algorithms in terms of efficiency, and it is stable especially on networks with unclear structure.
Key words: semi-supervised learning    active link selection    community detection    Non-negative Matrix Factorization (NMF)    
0 引言

社区发现常见的方法有谱方法、图分割方法、聚类方法、目标函数优化方法等[1-6]。大部分方法是基于网络拓扑结构,通过算法自动地发现网络中的社区,属于无监督的方法。这类方法通常存在两个问题:1)网络过于复杂时,比如网络之间存在重叠或者存在多级结构,很难准确获得社区的边界,无法获得准确的划分结果;2)在具有数据稀疏、链路缺失或有噪声的网络中,算法性能会大幅下降,难以有效揭示真实的社区结构。

为解决上述问题,半监督方法被引入社区发现算法[7-15],利用先验信息提高社区划分的准确度以及噪声环境下社区划分的鲁棒性。Eaton等[9]提出一种spin-glass模型,引入包含背景知识的节点标签和成对约束,提升算法的性能及鲁棒性。Wang等[10]提出在标签更新时吸收其邻近节点的标签信息作为先验信息的标签传播算法,不但继承了速度快的特点,还提高了社区发现的质量。这种直接使用节点标签作为监督信息的半监督社区发现方法简单而直接,但通常情况下,节点标签不易获取,或代价昂贵。Zhang和Zhang等[12]提出一种半监督社区发现的学习框架(及增强框架),通过链接对的must-link和cannot-link约束,为社区结构矩阵降噪,同时考虑节点的拓扑结构和链接对信息,指导社区发现过程,得到更具解释性的划分结果。但这些算法多采用随机选择链接对的方法,没有更多关注对社区划分具指导性的链接对,也没有关注先验信息与目标函数的关系。Yang等[13]提出一种使用隐空间图正则化方法的统一的半监督社区发现框架,并提出了基于各种非负矩阵分解(Non-negative Matrix Factorization, NMF)变形和谱聚类的半监督社区发现算法。对属于同一社区的节点增加图正则化项,使得越相近的节点在隐空间的向量表示尽可能相近。该方法将must-link约束对信息引入目标函数,提升算法在不同网络,尤其结构不清晰网络上社区发现的准确性。但是,这种方法存在以下不足:1)只是在初始化阶段选择约束对,对先验信息不能充分利用; 2)随机选择约束对,目标性不强,可能需要增加约束对比例以期达到满意的效果; 3)不能充分利用cannot-link约束信息。2015年,Yang等[14]提出一种主动选择链接的半监督社区发现方法。基于NMF算法,提出链接策略(Connection Strategy)和断开链接策略(Disconnection Strategy),并对两种策略的4种组合在不同的社区网络中进行测试,实验表明这些策略的运用,可以降低监督信息比例。但因仅利用先验信息改变网络的拓扑结构,没能融入社区发现过程,不能更充分地利用先验信息提升算法性能。

为减小链接选择信息的比例,并将先验信息引入目标函数,本文借鉴文献[14]算法,在基于NMF的半监督社区发现算法[13]的基础上,提出一种基于迭代框架的主动链接选择半监督社区发现算法ALS_GNMF(Active Link Selection algorithm for semi-supervised community detection based on Graph regularization NMF)。该算法在迭代框架下,主动选择对社区划分有指导意义且属于相同社区的链接对。通过增加链接对两端点之间,以及它们与所在社区中心(hub)的must-link约束,增强社区内部连接的紧密性;同时,增加与相邻社区节点的cannot-link约束,使社区边界更清晰。然后将主动选择的链接对作为先验信息,引入目标函数,以期提升算法性能。

1 ALS_GNMF算法 1.1 图正则非负矩阵分解算法

非负矩阵分解(NMF)算法可以发现隐含的模块结构,因此被成功应用于无监督社区发现领域[16]。NMF算法的目的是寻找两个非负矩阵,使得它们乘积与原始矩阵的相似度最高。NMF算法描述如下:

给定一个m×n的非负矩阵A,找到m×r的非负矩阵Wn×r的非负矩阵H,使得:

$ \mathit{\boldsymbol{A}} \approx \mathit{\boldsymbol{W}}{\mathit{\boldsymbol{H}}^{\rm{T}}} $ (1)

其中:$\mathit{\boldsymbol{A}} \in {\bf{R}}_{ \ge 0}^{m \times n}$是原始矩阵,$\mathit{\boldsymbol{W}} \in {\bf{R}}_{ \ge 0}^{m \times r}$$\mathit{\boldsymbol{H}} \in {\bf{R}}_{ \ge 0}^{n \times r}$分别是分解后的基矩阵和系数矩阵,并使分解后两个矩阵的乘积与原始矩阵尽可能地相似。通常情况下,r的取值条件为(n+m)rnm,进而使得矩阵WH的秩都小于矩阵A的秩。因此,矩阵W表示对原始矩阵A进行线性组合逼近的一组基,H是样本集A在基矩阵W上的非负投影系数矩阵,并且H可以取代原始非负矩阵A

图正则非负矩阵分解(Graph regularization Non-negative Matrix Factorization, GNMF)在进行矩阵分解的同时,要求在低维空间中继续保持样本的几何结构。假设两个数据点aiaj在原始空间是邻近点,那么在新的基下hihj相应地也是邻近点。

在社区发现中,如果预先知道节点ij属于相同的社区,那么矩阵H中的第i行和第j行,即hihj应该是相似的。因此,最小化这两行的差异,即可把这两个节点指派到相同的社区。

使用平方距离和K-L散度度量节点ij的相似性

$ {D_{{\rm{LSE}}}}({\mathit{\boldsymbol{h}}_i},{\mathit{\boldsymbol{h}}_j}) = \left\| {{\mathit{\boldsymbol{h}}_i} - {\mathit{\boldsymbol{h}}_j}} \right\|_2^2 = \sum\limits_{k = 1}^K {{{({h_{ik}} - {h_{jk}})}^2}} $ (2)
$ {D_{{\rm{KL}}}}({\mathit{\boldsymbol{h}}_i}\left\| {{\mathit{\boldsymbol{h}}_j}} \right.) = \sum\limits_{k = 1}^K {({h_{ik}}\lg \;({h_{ik}}/{h_{jk}}) - {h_{ik}} + {h_{jk}})} $ (3)

其中:hikhjk分别表示节点ij属于社区k的概率, K为社区总数。

节点ij属于相同社区,可以形式化地表示为一个三元组(i, j, oij),此时oij=1。若oij=0表示没有获得ij属于相同社区的先验信息。所有节点三元组集合表示为:C={(i, j, oij)}i, j=1NN为节点总数。

基于平方距离的先验约束形式化为:

$ \begin{array}{l} {R_{{\rm{LSE}}}}(\{ {o_{ij}}\} ,\mathit{\boldsymbol{H}}) = \frac{1}{2}\sum\limits_{(i,j,{o_{ij}}) \in C} {{o_{ij}}{D_{{\rm{LSE}}}}({\mathit{\boldsymbol{h}}_i},{\mathit{\boldsymbol{h}}_j})} = \\ \quad \quad \frac{1}{2}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {{o_{ij}}\left\| {{\mathit{\boldsymbol{h}}_i} - {\mathit{\boldsymbol{h}}_j}} \right\|_2^2} } \end{array} $ (4)

定义$\mathit{\boldsymbol{O}} = [{o_{ij}}] \in {\bf{R}}_{ \ge 0}^{N \times N}$,式(4)可以改写为:

$ \begin{array}{l} {R_{{\rm{LSE}}}}(\mathit{\boldsymbol{O}},\mathit{\boldsymbol{H}}) = \sum\limits_{i = 1}^N {\mathit{\boldsymbol{h}}_i^{\rm{T}}{\mathit{\boldsymbol{h}}_i}{d_{ii}}} - \sum\limits_{i \ne j} {\mathit{\boldsymbol{h}}_i^{\rm{T}}{\mathit{\boldsymbol{h}}_j}{o_{ij}}} = \\ \quad \quad {\rm{Tr}}({\mathit{\boldsymbol{H}}^{\rm{T}}}\mathit{\boldsymbol{DH}}) - {\rm{Tr}}({\mathit{\boldsymbol{H}}^{\rm{T}}}\mathit{\boldsymbol{OH}}) = {\rm{Tr}}({\mathit{\boldsymbol{H}}^{\rm{T}}}\mathit{\boldsymbol{LH}}) \end{array} $ (5)

其中:Tr(·)表示矩阵的迹,$\mathit{\boldsymbol{D}} = [{\mathit{d}_{ij}}] \in {\bf{R}}_{ \ge 0}^{N \times N}$是对角矩阵,${d_{ii}} = \sum\limits_{j = 1}^N {{o_{ij}}} $L=D-O是先验信息O的图正则矩阵,即拉普拉斯矩阵。

同理,基于K-L散度的约束形式化为:

$ {R_{{\rm{KL}}}}(\mathit{\boldsymbol{O}},\mathit{\boldsymbol{H}}) = \frac{1}{2}\sum\limits_{(i,j,{o_{ij}}) \in C} {{o_{ij}}({D_{{\rm{KL}}}}({\mathit{\boldsymbol{h}}_i}\left\| {{\mathit{\boldsymbol{h}}_j}} \right.)} + {D_{{\rm{KL}}}}({\mathit{\boldsymbol{h}}_j}\left\| {{\mathit{\boldsymbol{h}}_i}} \right.)) $ (6)

RLSE(O, H)与RKL(O, H)即为图正则项,将它们分别引入相应的目标函数,得到:

$ \begin{array}{l} {F_{{\rm{LSE}}}}(\mathit{\boldsymbol{H}}{\left| {\mathit{\boldsymbol{A}},\mathit{\boldsymbol{O}}) = L} \right._{{\rm{LSE}}}}(\mathit{\boldsymbol{A}},\mathit{\boldsymbol{H}}) + \lambda {R_{{\rm{LSE}}}}(\mathit{\boldsymbol{O}},\mathit{\boldsymbol{H}}) = \\ \quad \left\| {\mathit{\boldsymbol{A}} - \mathit{\boldsymbol{W}}{\mathit{\boldsymbol{H}}^{\rm{T}}}} \right\|_{\rm{F}}^2 + \lambda {\rm{Tr}}({\mathit{\boldsymbol{H}}^{\rm{T}}}\mathit{\boldsymbol{LH}}) \end{array} $ (7)
$ \begin{array}{l} {F_{{\rm{KL}}}}(\mathit{\boldsymbol{H}}{\left| {\mathit{\boldsymbol{A}},\mathit{\boldsymbol{O}}) = L} \right._{{\rm{KL}}}}(\mathit{\boldsymbol{A}},\mathit{\boldsymbol{H}}) + \lambda {R_{{\rm{KL}}}}(\mathit{\boldsymbol{O}},\mathit{\boldsymbol{H}}) = \\ \quad \sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {({a_{ij}}{\rm{lg}}\;({a_{ij}}/\sum\limits_{k = 1}^K {{w_{ik}}{h_{jk}}} )} } - {a_{ij}} + \sum\limits_{k = 1}^K {{w_{ik}}{h_{jk}}} ) + \\ \quad \frac{\lambda }{2}\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^N {\sum\limits_{k = 1}^N {({h_{ik}}{\rm{lg}}\;({h_{ik}}/{h_{jk}})} } } + {h_{jk}}{\rm{lg}}\;({h_{jk}}/{h_{ik}})){o_{ij}} \end{array} $ (8)

其中λ是拓扑信息与先验信息之间的平衡参数,为非负数。

对无向无权图,其邻接矩阵A是对称的,式(7)可以改写成:

$ \begin{array}{l} {F_{{\rm{SNMF}}}}(\mathit{\boldsymbol{H}}{\left| {\mathit{\boldsymbol{A}},\mathit{\boldsymbol{O}}) = L} \right._{{\rm{SNMF}}}}(\mathit{\boldsymbol{A}},\mathit{\boldsymbol{H}}) + \lambda {R_{{\rm{SNMF}}}}(\mathit{\boldsymbol{O}},\mathit{\boldsymbol{H}}) = \\ \quad \quad \left\| {\mathit{\boldsymbol{A}} - \mathit{\boldsymbol{H}}{\mathit{\boldsymbol{H}}^{\rm{T}}}} \right\|_{\rm{F}}^2 + \lambda {\rm{Tr}}({\mathit{\boldsymbol{H}}^{\rm{T}}}\mathit{\boldsymbol{LH}}) \end{array} $ (9)

采用三重迭代算法[13],获得FLSE的更新规则:

$ \left\{ \begin{array}{l} {w_{ik}} \leftarrow {w_{ik}}\frac{{{{(\mathit{\boldsymbol{AH}})}_{ik}}}}{{{{(\mathit{\boldsymbol{W}}{\mathit{\boldsymbol{H}}^{\rm{T}}}\mathit{\boldsymbol{H}})}_{ik}}}}\\ {h_{jk}} \leftarrow {h_{jk}}\frac{{{{({\mathit{\boldsymbol{A}}^{\rm{T}}}\mathit{\boldsymbol{W}} + \lambda \mathit{\boldsymbol{OH}})}_{jk}}}}{{{{(\mathit{\boldsymbol{H}}{\mathit{\boldsymbol{W}}^{\rm{T}}}\mathit{\boldsymbol{W}} + \lambda \mathit{\boldsymbol{DH}})}_{jk}}}} \end{array} \right. $ (10)

FSNMF的更新规则:

$ {h_{ik}} \leftarrow {h_{ik}}\frac{{{{(\mathit{\boldsymbol{AH}} + \lambda \mathit{\boldsymbol{OH}})}_{ik}}}}{{{{(\mathit{\boldsymbol{H}}{\mathit{\boldsymbol{H}}^{\rm{T}}}\mathit{\boldsymbol{H}} + \lambda \mathit{\boldsymbol{DH}})}_{ik}}}} $ (11)

FKL的更新规则:

$ \left\{ \begin{array}{l} {w_{ik}} \leftarrow {w_{ik}}\frac{{\sum\limits_j {({\mathit{a}_{ij}}{\mathit{h}_{jk}}/\sum\limits_k {{w_{ik}}{h_{jk}})} } }}{{\sum\limits_j {{h_{jk}}} }}\\ {\mathit{\boldsymbol{h}}_k} \leftarrow ({\sum\limits_i {{w_{ik}}\mathit{\boldsymbol{I}} + \lambda \mathit{\boldsymbol{L}})} ^{ - 1}}{{\mathit{\boldsymbol{\hat h}}}_k} \end{array} \right. $ (12)

其中:hkH的第k列,IN×N的单位矩阵,${{\mathit{\boldsymbol{\hat h}}}_k}$为:

$ {{\mathit{\boldsymbol{\hat h}}}_k} = \left[ {\begin{array}{*{20}{c}} {{h_{1k}}\sum\limits_i {({a_{i1}}{w_{ik}}/\sum\limits_k {{w_{ik}}{h_{1k}})} } }\\ {{h_{2k}}\sum\limits_i {({a_{i2}}{w_{ik}}/\sum\limits_k {{w_{ik}}{h_{2k}})} } }\\ \vdots \\ {{h_{Nk}}\sum\limits_i {({a_{iN}}{w_{ik}}/\sum\limits_k {{w_{ik}}{h_{Nk}})} } } \end{array}} \right] $ (13)
1.2 ALS_GNMF算法

ALS_GNMF算法的基本思想是:1)利用NMF算法计算初始社区划分矩阵H,主动选择H中位于社区边界不确定性高,并对社区划分具有指导意义的链接对; 2)为主动选择链接对增加must-link约束,生成先验信息矩阵,增加cannot-link约束,修改邻接矩阵; 3)将先验信息矩阵作为正则项融入基于NMF的最优化目标函数,依据更新规则反复迭代,直到两次更新的目标函数差值达到指定的阈值为止,得到最终的社区划分矩阵H

1) 主动链接选择方法。

采用计算链接对信息熵的方法,可以找到位于社区边界的不确定性链接对。每个节点可以通过它属于某社区的概率计算信息熵,公式为:

$ \begin{array}{l} E({\mathit{x}_i}) = - \sum\limits_{k = i}^K {P({\mathit{x}_i} = \mathit{k})\;{\rm{lg}}\;\mathit{P}(} {\mathit{x}_i} = k) = \\ \quad \quad - \sum\limits_{k = i}^K {{x_{ik}}{\rm{lg}}\;({x_{ik}})} \end{array} $ (14)

如果某个节点属于k个不同社区的概率是相同的,即概率为1/k,则该节点的不确定性很大,熵值是最大的; 相反,如果节点属于某个特定社区的概率为1,属于其他社区的概率为0,则该节点的确定性很大,熵值最小。链接对的熵值定义为其端点熵值的平均值。

2) 生成先验信息矩阵修改邻接矩阵。

寻找每个社区中心(hub)节点h,即社区中熵值最小的节点。若链接对的两个端点属于同一社区,则在这两个端点之间,以及每个端点与h之间建立must-link约束。

图 1所示,链接对〈u, v〉属于同一社区,节点h为该社区hub,则在节点uvuhvh之间建立3个must-link约束,即令ouv=1,ouh=1,ovh=1。依次处理所有主动选择的链接对,生成先验信息矩阵O

图 1 增加must-link约束 Figure 1 Adding must-link constraints

为使社区边界更清晰,若链接对与其他社区相连,则增加链接对的cannot-link约束。如图 1所示,主动选择的链接对〈u, v〉,其端点u与其他社区的节点bcd均有链接,此时,断开这3组链接,为节点u增加3组cannot-link约束,形成如图 2所示的拓扑结构。同时修改网络邻接矩阵A,令aub=0,auc=0,aud=0。

图 2 增加cannot-link约束 Figure 2 Adding cannot-link constraints

3) ALS_GNMF算法。

ALS_GNMF算法步骤如下:

输入    网络邻接矩阵A,各节点与社区真实隶属关系矩阵C,先验链接对比例percent

输出    社区划分矩阵H

步骤1    初始化先验信息矩阵ON×N的零矩阵(N为节点数)。

步骤2    利用NMF算法,计算初始社区划分矩阵H

步骤3    利用式(14)计算H矩阵中各节点的熵,找到各社区的hub节点及t组最不确定链接对(为平稳且较快达到规定先验比例,每次选择3组最不确定链接对,设置t=3)。

步骤4    对照真实隶属关系矩阵C,为主动选择的链接对增加must-link约束,修改先验信息矩阵O,增加cannot-link约束,修改邻接矩阵A

步骤5    将先验信息矩阵O融入目标函数,依据更新规则反复迭代,直到两次目标函数差值达到指定阈值为止,得到新的社区划分矩阵H

步骤6    计算主动选择链接对比例ratio,重复执行步骤3~5,直到ratio的值达到percent为止。

步骤7    计算并输出社区划分矩阵H

2 实验与结果分析

为比较ALS_GNMF算法与GNMF算法[13]的性能,以标准互信息(Normalized Mutual Information, NMI)和准确率作为评价指标,选取3组真实网络和3组人工生成网络进行测试,如表 1所示。实际网络为Football、School7和Dolphin网络,3组人工网络为LFR网络,除混合参数外,其他生成参数均相同。算法用Matlab实现,在Intel Core CPU 2.60 GHz,4 GB内存的Windows7(64位)计算机上运行。

表 1 真实网络及人工网络数据 Table 1 Data of real-world and synthetic networks

两种算法分别采用3种更新规则:1)基于平方距离的LSE方法(式(10));2)基于平方距离的对称矩阵的SNMF方法(式(11));3)基于K-L散度KL方法(式(12))。每个网络均使用6种方法测试,先验比例从0增加到30%,NMI值及准确率均取10次计算的平均值,测试结果见表 2图 3图 4所示。

表 2 真实网络中ALS_GNMF与GNMF算法互信息比较 Table 2 Normalized mutual information compare of ALS_GNMF and GNMF on real-world networks
图 3 ALS_GNMF与GNMF算法在LFR网络的互信息比较 Figure 3 Normalized mutual information comparison of ALS_GNMF and GNMF on LFR networks
图 4 ALS_GNMF与GNMF算法在LFR网络的准确率比较 Figure 4 Accuracy comparison of ALS_GNMF and GNMF on LFR networks

表 2为3组真实网络的NMI测试数据。可以看出Football网络中,ALS_GNMF算法的三种方法在相同先验比例(2%~30%)下NMI值均高于GNMF算法对应方法。以ALS_GNMF算法的ALS-LSE方法为例,先验比例为2%(NMI=0.9357)时,效果与GNMF算法的LSE方法30%先验比例(NMI=0.9323)相当。同样,ALS-KL及ALS-SNMF方法2%先验比例的效果相当于GNMF对应方法20%先验比例的效果。School7网络也具有相同的特点,ALS-KL方法4%的先验比例可达到KL算法10%的效果,ALS-LSE方法仅2%的先验比例就高于LSE算法30%的效果,ALS-SNMF 8%的先验比例高于SNMF20%的效果。Dolphin网络中,ALS_GNMF算法在2%的先验比例下NMI值均已达到1。

图 3为人工网络的NMI测试结果,为验证算法在LFR网络的性能,选取不同的混合参数,生成120个节点的三组网络。参数设置为:节点数N=120,平均度k=11,度的最大值kmax=20,社区数最小值xmin=5,社区数最大值cmax=13。图 3(a)的混合参数mu=0.7,图 3(b)的混合参数mu=0.8,图 3(c)的混合参数mu=0.9。

图 3(a)中GNNF的LSE、KL方法性能较差,SNMF方法及ALS-LSE、ALS-SNMF、ALS-KL方法均随着先验比例的增加性能呈上升态势,且SNMF方法在30%的先验比例下效果与ALS-SNMF,ALS-KL相当。图 3(b)混合参数增加到0.8,SNMF方法虽仍强于LSE和KL,但与之前相比性能急剧下降,曲线仅呈微弱抬升趋势。

而ALS_GNMF算法的ALS-SNMF、ALS-KL及ALS-LSE性能基本稳定,随先验比例的增加呈明显上升趋势。图 3(c)混合参数增加到0.9,GNMF算法的三种方法的性能都很差,LSE方法甚至有下降趋势。相反,ALS_GNMF算法的三种方法依然随先验比例的增加呈上升趋势。ALS-KL和ALS-SNMF方法还能保持较高的稳定性。图 4的准确率测试结果亦可得出与NMI大致相同的结论。

综上可知:1)大多数情况下,采用相同的先验信息比例,ALS_GNMF算法比GNMF算法效果好。2)ALS_GNMF算法使用很少的先验信息比例就可以达到GNMF算法用较高的先验信息才能达到的效果。3)网络结构复杂时,GNMF算法性能较差,而ALS_GNMF算法性能良好,且随着网络结构复杂度的增加,表现出良好的稳定性和鲁棒性。

3 结语

本文提出的ALS_GNMF算法,基于迭代框架迭代地执行:1)基于当前社区发现结果,选择不确定性大的链接进行标定作为先验信息;2)增加所选链接对与其所在社区中心hub节点间的must-link约束,与相邻社区节点的cannot-link约束,以增强社区内部连接的紧密性,弱化社区间的链接,清晰化社区边界;3)将must-link作为正则项融入目标函数进行社区发现。通过使用实际网络及人工网络数据集测试,ALS_GNMF算法在相同的先验信息比例下,效果远好于GNMF算法,可以使用很少的先验信息比例,达到GNMF算法用较高的先验信息才能达到的效果。尤其在结构不清晰的网络中,ALS_GNMF算法性能稳定,具有良好的鲁棒性。

参考文献(References)
[1] KAUFMANN E, BONALD T, LELARGE M. An adaptive spectral algorithm for the recovery of overlapping communities in networks[C/OL].[2016-11-20]. http://chercheurs.lille.inria.fr/ekaufman/KBL15.pdf.
[2] FORTUNATO S. Community detection in graphs[J]. Physics Reports, 2010, 486(3): 75-174.
[3] SHEN H, CHENG X, GUO J. Exploring the structural regularities in networks[J]. Physical Review E, 2011, 84(5): 056111. DOI:10.1103/PhysRevE.84.056111
[4] JIANG Y, JIA C, YU J. An efficient community detection method based on rank centrality[J]. Physical A:Statistical Mechanics and Its Applications, 2013, 392(9): 2182-2194. DOI:10.1016/j.physa.2012.12.013
[5] ALDECOA R, MARÍN I. Surprise maximization reveals the community structure of complex networks[J]. Scientific Reports, 2013, 3(1): 1060. DOI:10.1038/srep01060
[6] JIANG Y, JIA C, YU J. An efficient community detection algorithm using greedy surprise maximization[J]. Journal of Physics A:Mathematical and Theoretical, 2014, 47(16): 165101. DOI:10.1088/1751-8113/47/16/165101
[7] 黄立威, 李彩萍, 张海粟, 等. 一种基于因子图模型的半监督社区发现方法[J]. 自动化学报, 2016, 42(10): 1520-1531. (HUANG L W, LI C P, ZHANG H S, et al. A semi-supervised community detection method based on factor graph model[J]. Acta Automatica Sinica, 2016, 42(10): 1520-1531.)
[8] 陈俊宇, 周刚, 南煜, 等. 一种半监督的局部扩展式重叠社区发现方法[J]. 计算机研究与发展, 2016, 53(6): 1376-1388. (CHEN J Y, ZHOU G, NAN Y, et al. Semi-supervised local expansion method for overlapping community detection[J]. Journal of Computer Research and Development, 2016, 53(6): 1376-1388. DOI:10.7544/issn1000-1239.2016.20148339)
[9] EATON E, MANSBACH R. A spin-glass model for semi-supervised community detection[C]//Proceedings of the 26th AAAI Conference on Artificial Intelligence. Menlo Park, CA:AAAI Press, 2012, 7:900-906.
[10] WANG Y, WANG W, LIU D, et al. Using prior knowledge for community detection by label propagation algorithm[EB/OL].[2017-05-20]. https://www.scientific.net/AMR.1049-1050.1566.
[11] ZHANG Z Y. Community structure detection in complex networks with partial background information[J]. Europhysics Letters, 2013, 101(4): 48005. DOI:10.1209/0295-5075/101/48005
[12] 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: 3241. DOI:10.1038/srep03241
[13] YANG L, CAO X, JIN D, et al. A unified semi-supervised community detection framework using latent space graph regularization[J]. IEEE Transactions on Cybernetics, 2015, 45(11): 2585-2598. DOI:10.1109/TCYB.2014.2377154
[14] YANG L, JIN D, WANG X, et al. Active link selection for efficient semi-supervised community detection[J]. Scientific Reports, 2015, 5: 9039. DOI:10.1038/srep09039
[15] CAI D, HE X, HAN J, et al. Graph regularized nonnegative matrix factorization for data representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(8): 1548-1560. DOI:10.1109/TPAMI.2010.231
[16] 李亚芳, 贾彩燕, 于剑. 应用非负矩阵分解模型的社区发现方法综述[J]. 计算机科学与探索, 2016, 10(1): 1-13. (LI Y F, JIA C Y, YU J. Survey on community detection algorithms using nonnegative matrix factorization model[J]. Journal of Frontiers of Computer Science and Technology, 2016, 10(1): 1-13.)