国防科技大学学报 011年 模糊聚类结果作为最终的社团划分结果。 降低算法对初始条件的敏感性,扩大了适用范围。 上述方法在判断社团数上需要预先给定或花2.4基于种子扩展思想的重叠社团发现算法 费大量计算以确定合理的社团数目。我们在文献 此类算法的基本思想是以具有某种特征的子 [24]中提出基于通信-时间核构建距离矩阵,输网络为种子,通过合并扩展等操作向邻接节点扩 入到模糊相似性传播聚类来实现重叠社团发现, 展,直至获得评价函数最大的社团。该类算法近 在考虑节点长程相关性的同时,可以自适应地确两年来得到了迅速发展。 定社团数。值得一提的是,此类算法的关键在于 Lancichinetti等切提出以若干个节点为种子 所构建的距离矩阵,采用何种节点距离更符合实 通过扩展形成对整个网络的覆盖,即LMF算法 际情况在具体应用中是一个值得探索的问题。 该算法定义了两个适应度函数:社团的适应度和 23基于非负矩阵分解的重叠社团发现算法节点对社团的适应度。其种子扩展的基本步骤 非负矩阵分解方法是一种聚类和降维技术,是:以单个节点为初始社团g,考虑所有与其相 已经在多个领域取得广泛应用。它将特征矩阵邻的节点A,将对g的适应度最大的邻节点加入 V近似分解为两个非负矩阵Wnxk和Hx,使得到当前社团形成s,重新计算g中各节点的适应 两者的乘积尽可能等于原有特征矩阵。将非负矩度,将适应度为负的节点剔除,重复上述过程直至 阵分解应用于社团发现,其思想是特征矩阵V中扩展后的社团其邻节点对它的适应度均为负。通 的每个行向量ν可以近似地看作H的列向量的过一定的种子选取策略(每次选取尚未指派到社 线性组合:=wH,w其中是W的行向量,从而可团的节点),可以由扩展得到的若干个局部社团生 以用相对于V更少的基向量H来表示整个数据成整个网络的覆盖,保证网络中每个节点至少被 空间,而w则表示各基向量对于产生数据点所个局部社团所覆盖。 起到的权重。因此,可以利用W将各节点聚成k 此外,尚明生、陈端兵等也提出类似的种子扩 个类,而W各分量值表示每个节点到每个社团的展思想{x-列,主要区别在于种子选择策略、扩展 绝对隶属度。从图3所示的w分量曲线可以看评价函数上的不同。如文献[28]提出节点强度的 出,节点6和节点11分别与两个社团呈现出一定概念,即节点所有邻接边的权重之和,依次以最大 的隶属关系,说明节点6和节点11是潜在的社团强度的单个节点为种子;文献[29]则是以最大团 重叠区域。算法关键在于如何选取特征矩阵以表为种子,通过合并和扩展两步逐步形成最终的社 示复杂网络中所蕴含的拓扑信息 团,而两者均以考虑节点隶属度的重叠模块度Q 为扩展评价函数。 2.5基于混合概率模型的重叠社团发现 前述很多算法均是先给出社团结构的定义或 量化特征,然后再设计相应的算法寻找社团。换 句话说,这些方法均需对社团结构作出假设。针 012345678910111213l 对此问题, Newman等建立了社团结构的混合概率 模型,以概率方法对复杂网络的社团结构进行探 图3一个包含两个重叠节点的简单网络 及其对应的分量 索,以求得期望最大的社团结构,从而避开社团定 Fig 3 A simple network with two overlapping node 义的问题。他们认为社团是由具有相似连接 correspondingwentries 的节点组成的,因此定义两个模型参数和π用 张世华等首次将NMF应用于重叠社团发 来刻画社团r的特征,其中bn表示社团r中某节 现,他们以扩散核为基础,将正规化后的核矩 点对节点i的连接概率,丌,表示社团r的节点数 阵作为特征矩阵V,同时采用一种梯度下降的迭 代方法来求解W和H。该算法最大的优点在于占整个网络节点数的比例。通过这两个参数,可 能够给出节点与社团之间所属关系的绝对概率, 以将网络的邻接矩阵A看作是观察数据,并引入 这是上述算法所不具备的。但该算法依然需要预缺失数据g={g},用来表示节点i所属社团,由 先给定k参数不可避免在确定k值时带来较高此将问题转换为典型的带缺失数据的最大似然估 的计算开销仅适用较小规模的网络。Zmei等则计间题,其似然度计算如下: 引入新的节点-节点关联矩阵作为特征矩阵, L= InP(A ,) =lnP(A|g,π,)P(g|π,0)模糊聚类结果作为最终的社团划分结果。 上述方法在判断社团数上需要预先给定或花 费大量计算以确定合理的社团数目。我们在文献 ［２４］中提出基于通信 －时间核构建距离矩阵，输 入到模糊相似性传播聚类来实现重叠社团发现， 在考虑节点长程相关性的同时，可以自适应地确 定社团数。值得一提的是，此类算法的关键在于 所构建的距离矩阵，采用何种节点距离更符合实 际情况在具体应用中是一个值得探索的问题。 ２３ 基于非负矩阵分解的重叠社团发现算法 非负矩阵分解方法是一种聚类和降维技术， 已经在多个领域取得广泛应用。它将特征矩阵 Ｖ近似分解为两个非负矩阵 Ｗｎ×ｋ和 Ｈｋ×ｎ，使得 两者的乘积尽可能等于原有特征矩阵。将非负矩 阵分解应用于社团发现，其思想是特征矩阵 Ｖ中 的每个行向量 ｖ可以近似地看作 Ｈ的列向量的 线性组合：ｖ＝ｗＨ，ｗ其中是Ｗ 的行向量，从而可 以用相对于 Ｖ更少的基向量 Ｈ来表示整个数据 空间，而 ｗ则表示各基向量对于产生数据点 ｖ所 起到的权重。因此，可以利用 Ｗ 将各节点聚成 ｋ 个类，而 Ｗ 各分量值表示每个节点到每个社团的 绝对隶属度。从图 ３所示的 ｗ分量曲线可以看 出，节点 ６和节点 １１分别与两个社团呈现出一定 的隶属关系，说明节点 ６和节点 １１是潜在的社团 重叠区域。算法关键在于如何选取特征矩阵以表 示复杂网络中所蕴含的拓扑信息。 图 ３ 一个包含两个重叠节点的简单网络 及其对应的 ｗ分量 Ｆｉｇ．３ Ａｓｉｍｐｌｅｎｅｔｗｏｒｋｗｉｔｈｔｗｏｏｖｅｒｌａｐｐｉｎｇｎｏｄｅ ａｎｄｃｏｒｒｅｓｐｏｎｄｉｎｇｗｅｎｔｒｉｅｓ 张世华等首次将 ＮＭＦ应用于重叠社团发 现［２５］ ，他们以扩散核为基础，将正规化后的核矩 阵作为特征矩阵 Ｖ，同时采用一种梯度下降的迭 代方法来求解 Ｗ 和 Ｈ。该算法最大的优点在于 能够给出节点与社团之间所属关系的绝对概率， 这是上述算法所不具备的。但该算法依然需要预 先给定 ｋ参数，不可避免在确定 ｋ值时带来较高 的计算开销，仅适用较小规模的网络。Ｚａｒｅｉ等则 引入新的节点 －节点关联矩阵作为特征矩阵［２６］ ， 降低算法对初始条件的敏感性，扩大了适用范围。 ２４ 基于种子扩展思想的重叠社团发现算法 此类算法的基本思想是以具有某种特征的子 网络为种子，通过合并、扩展等操作向邻接节点扩 展，直至获得评价函数最大的社团。该类算法近 两年来得到了迅速发展。 Ｌａｎｃｉｃｈｉｎｅｔｔｉ等［２７］ 提出以若干个节点为种子， 通过扩展形成对整个网络的覆盖，即 ＬＭＦ算法。 该算法定义了两个适应度函数：社团的适应度和 节点对社团的适应度。其种子扩展的基本步骤 是：以单个节点 ｖ为初始社团 ｇ，考虑所有与其相 邻的节点 Ａ，将对 ｇ的适应度最大的邻节点加入 到当前社团形成 ｇ′，重新计算 ｇ′中各节点的适应 度，将适应度为负的节点剔除，重复上述过程直至 扩展后的社团其邻节点对它的适应度均为负。通 过一定的种子选取策略（每次选取尚未指派到社 团的节点），可以由扩展得到的若干个局部社团生 成整个网络的覆盖，保证网络中每个节点至少被 一个局部社团所覆盖。 此外，尚明生、陈端兵等也提出类似的种子扩 展思想［２８－２９］ ，主要区别在于种子选择策略、扩展 评价函数上的不同。如文献［２８］提出节点强度的 概念，即节点所有邻接边的权重之和，依次以最大 强度的单个节点为种子；文献［２９］则是以最大团 为种子，通过合并和扩展两步逐步形成最终的社 团，而两者均以考虑节点隶属度的重叠模块度 Ｑｏ 为扩展评价函数。 ２５ 基于混合概率模型的重叠社团发现 前述很多算法均是先给出社团结构的定义或 量化特征，然后再设计相应的算法寻找社团。换 句话说，这些方法均需对社团结构作出假设。针 对此问题，Ｎｅｗｍａｎ等建立了社团结构的混合概率 模型，以概率方法对复杂网络的社团结构进行探 索，以求得期望最大的社团结构，从而避开社团定 义的问题［３０］ 。他们认为社团是由具有相似连接 的节点组成的，因此定义两个模型参数θｒｉ和πｒ用 来刻画社团 ｒ的特征，其中θｒｉ表示社团 ｒ中某节 点对节点 ｉ的连接概率，πｒ表示社团 ｒ的节点数 占整个网络节点数的比例。通过这两个参数，可 以将网络的邻接矩阵 Ａ看作是观察数据，并引入 缺失数据 ｇ＝｛ｇｉ｝，用来表示节点 ｉ所属社团，由 此将问题转换为典型的带缺失数据的最大似然估 计问题，其似然度计算如下： Ｌ＝ｌｎＰ（Ａ，ｇ｜π，θ） ＝ｌｎＰ（Ａ｜ｇ，π，θ）Ｐ（ｇ｜π，θ） · ５０· 国 防 科 技 大 学 学 报 ２０１１年