0 引言

社区发现是复杂网络分析的一个关键方法，其可识别网络中紧密链接子图，子图内节点链接紧密，子图间节点链接稀疏。研究者提出了大量社区发现方法^[1-2]，基于概率模型的社区发现方法因其具有解释性强的数学模型、严密的推理算法及有意义的准确结果，在各种社区发现方法中脱颖而出。大多流行的概率模型对网络的链接生成过程建模，根据模型的功能不同将其分为3类^[3-4]：1)对称的模型，假设链接的两个端点角色相同，对无向网络的链接的联合概率建模；2)条件模型，对有向网络的接收链接的端点产生链接的条件概率建模；3)非对称模型，对有向网络的有向链接的联合概率建模。前两类是第3类的特例，PPL(Popularity and Productivity Link)模型属于非对称模型，模型性能优于前两种，但其属于无监督聚类，仅能利用网络拓扑信息，导致模型性能在网络结构不清晰时不够鲁棒、准确。

近来研究者提出了一些半监督社区发现方法，先验信息被引入到社区发现中，利用先验信息提高社区划分的性能。已有的半监督社区发现方法分为两类：一类直接利用节点类标作为监督信息^[5-7]，该方法属于使用监督信息的最直接方法，但通常不易获取节点属于某类的先验信息，因此不是最有效的方法。另一类利用约束链接对must-link和cannot-link作为监督信息^[8-13]，归为3类：1)随机选择链接，标定约束类型，假设同类节点链接、异类节点不链接，利用约束改变邻接矩阵，基于传统的社区发现方法挖掘网络潜在聚类结构^[8-10]。2)随机选择链接信息，将链接信息作为罚项与无监督社区发现目标函数融合。Yang等^[11]提出一个基于潜在空间图正则化的半监督社区发现框架，将先验信息作为正则化项与社区发现模型整合。3)基于主动学习策略选择链接进行人工标记，为半监督社区发现提供效用高的约束。将这些先验依据同类节点链接、异类节点不链接的假设转化为网络拓扑结构，然后基于融入先验的拓扑实现传统无监督社区发现。Cheng等^[12]提出了一个主动半监督方法，基于启发性策略选择节点及其相关约束进行标定，对约束进行扩展，最后利用传统社区发现方法识别网络社区结构。Yang等^[13]设计了一个迭代的主动半监督聚类方法，每次迭代基于网络社区发现结果，利用最大熵原则选择最不确定的链接进行标记，基于链接策略和去链接策略，清晰化网络结构，基于此网络拓扑实现非负矩阵分解进行社区发现。

研究表明，半监督信息可以提高无监督社区发现的性能，尤其是主动选择的先验。因此，设计主动学习算法获取先验，利用先验提高PPL模型的社区发现性能。先验主要有两类，标记节点和约束标记，前者简单但不易获取，后者不易融入基于概率模型的社区发现节点隶属度变量中。Basu等^[14]提出了一个主动半监督聚类算法，其主动学习算法可以通过标记约束获得每个类的标记节点集合，但其不能直接应用到网络数据上。

借鉴已有半监督社区发现方法和主动学习方法的思想，将无监督社区发现模型PPL改进为半监督模型，可利用高质量的先验信息提高社区发现的准确性。为设计一个以较少先验获得社区发现准确率较大提升的算法，首先提出一个主动节点先验学习(Active Node Prior Learning, ANPL)算法，主动选择约束对进行标记，基于标记约束生成不相交的多个节点子集组成的标记节点集合，每个子集对应一个社区。然后，提出一个基于PPL模型的半监督社区发现(Semi-supervised PPL, SPPL)模型，将ANPL学到的标记节点集合与网络拓扑信息融合，以获得更高的社区发现准确率。最后，在人工网络和实际网络数据上验证设计的ANPL和SPPL模型的有效性。

1 主动节点先验学习算法ANPL

半监督先验的常见形式有约束对标记和节点标记，约束对形式的标记容易获得。例如，在文档聚类中，很容易根据两个文档特征的相似度判断其是否属于一类；在微信用户网络社区划分时，很容易根据两个微信用户关注主题判断其是否属于一个社区。但节点标记先验容易初始化节点的隶属度信息，进而初始化PPL模型参数。因此，设计主动节点先验学习ANPL算法，主动选择约束对进行标记，基于约束对生成标记节点集合。

ANPL算法包括两个阶段：初始类骨架构造阶段和类集合扩充阶段(针对社区发现，类指社区)。在介绍ANPL算法之前说明一些变量含义：A表示网络的邻接矩阵；K表示类个数；N_k表示第k类节点集合；{N_k}_k=1^curk表示已构造的子类集合N_k组成的集合，每个元素为集合N_k，curk为已构造类的个数；i、j表示网络节点变量；sim(i, N_k)表示节点i和集合N_k的相似度；sim(i, j)表示节点i和j的相似度；γ_ik表示节点i属于类k的概率；T(i)表示节点i的邻居节点集合。

初始类骨架构造阶段 基于最远优先遍历模式，选择与已标记节点集合最不相似的节点，标记其与已标记节点的约束关系，进而确定其属于某个标记节点集合。针对某个网络A，首先选择度最大的节点作为初始类节点，记作N₁的元素。

然后依次选择与已有标记节点集合相似度最小的节点，节点与已有N_k的相似度值计算如式(1)所示。根据与已有N_k的关系，如果与已有N_k存在must-link约束关系则添加到该集合，如果与所有{N_k}都为cannot-link关系，则新构造一个集合，将该节点加入。

$ sim(i, {N_k}) = \mathop {\min }\limits_{j \in {N_k}} sim\left( {i, j} \right) $

(1)

其中$sim(i, j) = \frac{{\left| {T\left( i \right) \cap T\left( j \right)} \right|}}{{\left| {T\left( i \right) \cup T(j)} \right|}} $。

初始类骨架构造阶段结束条件是{N_k}集合元素个数达到K，或标记成对约束超过给定数目。如果初始骨架构造阶段在约束超限结束时，{N_k}个数未达到K，则从未选择节点中选择熵大节点加入{N_k}，直到{N_k}个数达到K。

节点i熵计算公式为：

$ entropy\left( i \right) =-\sum\limits_{k = 1}^K {{\gamma _{ik}}} \ln {\gamma _{ik}} $

(2)

类集合扩充阶段 它是在类骨架已构造好且使用约束个数未超限情形下进行。根据基于PPL模型的无监督社区发现结果，得到每个节点的熵。从非{N_k}_k=1^K的节点中选择熵大的节点，判断与已有{N_k}_k=1^K集合的关系，直到约束个数达到阈值。

ANPL算法详细描述如算法1。

算法1  主动节点先验学习算法。

输入 网络节点划分类个数K，邻接矩阵A={A_ij}，节点的相似度矩阵，所有节点的熵，可使用约束对数目m；

输出 {N_k}_k=1^K集合。

网络骨架构造阶段：

1) N₁= {度最大的节点}, 当前类个数curk=1。

2) while (curk < K)

  选择与{N_k}_k=1^curk相似度最小的非{N_k}_k=1^curk节点i；

  查询i与{N_k}_k=1^curk中节点的关系：

    如果与某个N_k中节点存在must-link, 则加入N_k，

    如果与所有{N_k}_k=1^curk都是cannot-link，

      curk=curk+1，加入N_curk, 根据使用约束数量修改m

end

类集合扩展阶段：

3) while (使用约束 < m)

 按照未标记的网络节点(即非{N_k}_k=1^curk的网络节点的熵由大到小排列

 选择熵最大的节点i

 查询i与{N_k}_k=1^curk中首节点是否存在must-link

 将i加入与其具有must-link的N_k集合

end

ANPL算法可主动选择约束对进行标记，自动生成标记节点集合先验，作为半监督社区发现的先验。下面设计一个半监督社区发现SPPL模型。

2 半监督社区发现SPPL模型

PPL属于无监督社区发现模型，为独立生成网络边集合E的每条边〈i, j〉建模。相关变量定义如下：γ_ik表示节点i属于社区k的概率；a_i表示节点i产生链接的概率；b_j表示节点j接收链接的概率；c_i表示节点i在确定社区先验时的权重；〈i, j〉表示i指向j的链接。

PPL假设网络每条链接〈i, j〉生成过程如下：

1) 以概率$ \sum\limits_{i = 1}^N {{\gamma _{ik}}{c_i}} $选择社区k(k=1, 2, …, K)；

2) 给定社区k，以概率$\frac{{{\gamma _{ik}}{a_i}}}{{\sum\limits_{i'} {{\gamma _{i'k}}{a_{i'}}} }}\frac{{{\gamma _{jk}}{b_j}}}{{\sum\limits_{j'} {{\gamma _{j'k}}{b_{j'}}} }} $产生链接〈i, j〉。

PPL模型生成所有链接的似然如下：

$L = \prod\limits_{\left\langle {i, j} \right\rangle \in \{ \left\langle {i, j} \right\rangle |{A_{ij}} = 1\} } {\sum\limits_k {\frac{{{\gamma _{ik}}{a_i}}}{{\sum\limits_{i'} {{\gamma _{i'k}}{a_{i'}}} }}\frac{{{\gamma _{jk}}{b_j}}}{{\sum\limits_{j'} {{\gamma _{j'k}}{b_{j'}}} }}\sum\limits_{i'} {{\gamma _{i'k}}{c_{i'}}} } } $

(3)

半监督PPL(SPPL)模型要同时使生成网络的所有未标记链接和{N_k}_k=1^K中标记节点似然最大。因此，目标函数如下：

$ \begin{array}{l} SL = \prod\limits_{\left\langle {i, j} \right\rangle \in \{ \left\langle {i, j} \right\rangle |{A_{ij}} = 1, i \notin \{ {N_k}\} _{k = 1}^K\;{\rm{or}}\;j \notin \{ {N_k}\} _{k = 1}^K\} } {\sum\limits_k {\frac{{{\gamma _{ik}}{a_i}}}{{\sum\limits_{i'} {{\gamma _{i'k}}{a_{i'}}} }}\frac{{{\gamma _{jk}}{b_j}}}{{\sum\limits_{j'} {{\gamma _{j'k}}{b_{j'}}} }}\sum\limits_{i'} {{\gamma _{i'k}}{c_{i'}}} } } + \\ \prod\limits_{\left\langle {i, j} \right\rangle \in \{ \left\langle {i, j} \right\rangle |{A_{ij}} = 1, i, j \in \{ {N_k}\} _{k = 1}^K\} } {\sum\limits_k {I({l_i} = {l_j} = k)\frac{{{\gamma _{ik}}{a_i}}}{{\sum\limits_{i'} {{\gamma _{i'k}}{a_{i'}}} }}\frac{{{\gamma _{jk}}{b_j}}}{{\sum\limits_{j'} {{\gamma _{j'k}}{b_{j'}}} }}\sum\limits_{i'} {{\gamma _{i'k}}{c_{i'}}} } } \end{array} $

(4)

其中: i∉{N_k}_k=1^K or j∉{N_k}_k=1^K表示链接〈i, j〉的两个端点i、j至少有一个不属于标记集合{N_k}_k=1^K，若i属于第k个标记节点集合N_k，则γ_ik=1；且∀k′, k′≠k，γ_ik′=0。i, j∈{N_k}_k=1^K表示链接〈i, j〉两个端点i、j都属于标记节点集合，当i和j都属于第k个标记集合N_k，即i和j的标记l_i, l_j都为k，形式化为I(l_i=l_j=k)=1，其余情形I(l_i≠l_j)=0。

基于最大期望(Expectation Maximization, EM)框架求解SPPL模型参数。

E步按照式(5)求解网络任意链接〈i, j〉的隶属度q_ijk：

$ {q_{ijk}} \propto \frac{{{\gamma _{ik}}{a_i}}}{{\sum\limits_{i'} {{\gamma _{i'k}}{a_{i'}}} }}\frac{{{\gamma _{jk}}{b_j}}}{{\sum\limits_{j'} {{\gamma _{j'k}}{b_{j'}}} }}\sum\limits_k {{\gamma _{ik}}{c_i}} $

(5)

其中$ \sum\limits_{k = 1}^K {{q_{ijk}}} = 1 $。

M步求解模型参数:

非{N_k}_k=1^K中节点γ_ik，a_i、b_j、c_i参数，与PPL模型参数估计一致。

{N_k}_k=1^K中节点的隶属度γ_ik，根据{N_k}_k=1^K进行更新，如果某个端点i标记，γ_ik=1，且∀k′, k′≠k，γ_ik′=0。

a_i、b_j、c_i与PPL模型参数更新一致。

SPPL参数估计算法详细描述如算法2。

算法2  SPPL参数估计算法。

输入 网络节点划分类个数K，邻接矩阵A={A_ij}，{N_k}_k=1^K；

输出 γ，a, b, c。

1) 根据{N_k}_k=1^K初始化γ，随机初始化a, b, c。

2) while(阈值未达到)

    根据式(5)计算所有链接的{q_ijk}；

    计算非{N_k}_k=1^K中节点的{ γ_ik}；

    计算所有节点的{a_i}，{b_j}，{c_i}；

    计算似然阈值。

end

3 实验与结果分析

为验证基于ANPL的半监督SPPL模型的参数估计算法的有效性，与最近流行的基于非负矩阵分解(Non-negative Matrix Factorization, NMF)的半监督社区发现算法：基于KL散度(Kullback-Leibleer divergence)的非负矩阵分解方法NMF_KL和基于对称NMF的非负矩阵分解方法SNMF(Symmetric NMF)进行比较^[11]，这两种算法被验证具有较好的性能。选取4个真实无向网络数据(http://www-personal.umich.edu/~mejn/)、4个WebKB的子有向网络(http://www.cs.cmu.edu/~WebKB/)(表 1)和3个人工LFR无向网络^[15]进行测试(表 2)，表 2的混合系数表示类间链接概率。

算法在Intel Core i5-6200U CPU，8 GB内存的Windows10(64位)计算机上运行，用Matlab2012实现。主动节点先验学习算法ANPL抽取先验比例为网络节点对的一定百分比，网络节点对为N(N-1)/2，N为网络节点个数。先验比例分别设置为0.05、0.1、0.15、0.2、0.25、0.3、0.35、0.4。

在无向真实网络和人工网络上，对基于ANPL的SPPL社区发现模型性能进行测试，每个比例下的实验结果为算法运行10次的平均值和方差。为验证ANPL算法能得到比标记约束对更多的先验信息，以karate网络为例，提供0.05、0.1、0.15比例约束对先验，ANPL获得的先验信息统计结果如表 3所示。

表 3中，“主动标记约束对数量”表示ANPL算法主动选择的需要人工标记的约束对数量，“获取标记节点数量”表示ANPL算法输出的标记节点集合元素个数，“转换的约束数量”表示输出的标记节点集合转换为must-link和cannot-link约束数量。由表 3可看出，算法输出的节点标记集合转换为约束对的数量大于标记的约束对数量, 因此在karate上，ANPL算法可利用主动标记的约束对获得更大信息量的先验信息。其余网络类似，不再赘述。为验证其性能，将ANPL算法获得的标记节点集合作为SPPL模型的先验，通过基于SPPL模型的社区发现准确率来验证获取先验是否有效。

SPPL与NMF_KL、SNMF结果的标准互信息(Normalized Mutual Information, NMI)值比较如图 1~2所示(图 1(a)中，因为SNMF和SPPL模型在不同比例下的准确率都为1，因此两者的NMI曲线重合)。由于基于NMF的半监督社区发现方法针对无向网络，会将有向网络转换为无向网络进行处理，丢失网络的拓扑结构信息。

基于NMF的半监督社区发现方法只能处理无向网络的社区发现问题，基于SPPL的半监督社区发现可同时处理有向网络和无向网络。表 3给出了有向网络上基于ANPL的SPPL在不同比例先验0、0.01、0.05、0.1下社区发现结果的NMI值。

基于ANPL的SPPL社区发现的实验结果分析如下：

1) 基于SPPL模型的半监督社区发现方法，可处理有向网络和无向网络。图 1、图 2、表 4的基于SPPL模型的实验结果表明，半监督SPPL模型的性能优于无监督PPL模型的算法性能。

2) 最近提出的性能较优的NMF_KL和SNMF半监督社区发现方法只能处理无向网络。图 1~2给出了无向网络上，NMF_KL和SNMF与基于半监督SPPL模型性能比较结果。SNMF和NMF_KL在没有引入先验时大多数效果要比SPPL模型好，但随着先验的增加，SPPL模型的性能都超过基于NMF的半监督方法，并且随着先验信息的增加，半监督SPPL模型性能也随之提高，尤其类个数较多、结构不清晰条件下，SPPL性能提升更多，如在football、karate网络上。分析结果表明，在无向网络上，主动半监督社区发现模型SPPL性能优于基于NMF的半监督社区发现方法，主要原因是ANPL获得的先验信息量更大、SPPL模型能更好地对网络潜在社区结构建模。

3) 根据图 2中的NMI结果可看出：在类个数较多、混合系数较大时，即使先验增加很多，NMF_KL和SNMF不能很好地识别网络结构；主要原因是这两种算法选择随机抽取约束对进行标记。SPPL模型则能够更好地利用同等先验约束对提高算法的性能；主要原因是采用了主动选择约束及半监督技术。

因此，主动节点先验选择算法ANPL有效地为基于半监督SPPL模型选择了信息量大的先验，使得在相同先验下基于SPPL模型的社区发现方法可获得更好的性能。

4 结语

链接模型PPL是一个性能较优的社区发现模型，但其在网络结构复杂时效果不佳，且不能利用先验信息提高性能。为利用更少的先验更高效地提高模型的社区发现能力，提出了一个主动节点先验学习算法ANPL和一个半监督社区发现模型SPPL。

ANPL主动选择较少的、信息量较高的成对约束对进行标记，基于标记的约束对自动生成信息量更大的标记节点集合。SPPL模型融合节点标记先验和网络拓扑结构对社区发现任务建模，基于EM算法估计模型参数。与近来流行的半监督社区发现方法相比，基于ANPL的SPPL模型具有更好的社区发现能力。目前的算法不能处理大规模网络数据，未来将将现有算法迁移到Hadoop平台或Spark平台上，以高效、准确地处理大规模网络数据。