基于谱聚类的二分网络社团检测算法*

刘晨晨,许 英

(新疆财经大学统计与数据科学学院,新疆 乌鲁木齐 830012)

二分网络是复杂网络中的一种重要类型,它可以将用户-产品购买关系[1]、科学家-论文合作关系[2]、蛋白质-配体作用关系[3]等相关关系直观地表示出来.社团检测在挖掘二分网络的结构、预测对象的行为特征、提取网络的有用信息等方面有广泛应用[4].目前,二分网络社团检测方法主要有2种:一是将二分网络映射为单分网络,再采用单分网络社团检测算法进行社团划分.但这个映射过程会丢失原始网络信息,致使社团划分结果不理想[5].二是直接在二分网络上实现社团划分,如通过寻找二分网络的最大模块度[6]、标签传播[7]、节点间的亲密度[8]、边密度传播[4]等方法实现.为了保留二分网络的原始信息并进一步提高社团检测的模块度,笔者拟设计一种融合奇异值分解的谱聚类(Singular Value Decomposition of Multiway Spectral,SVD-MS)算法,即将单分网络社团检测方法[9]扩展到二分网络,通过奇异值分解方法解决二分网络邻接矩阵的非对称问题,再采用启发式算法快速求解向量划分问题,从而实现二分网络的社团检测.

1 相关工作

1.1 二分网络

二分网络由2种不同类型的节点组成,直接连边只存在于不同类型的节点之间,同一类型的节点之间不存在直接连边.用G=(U,V,E)表示一个二分网络,U和V为不同类型节点的集合,E为节点之间连边的集合.在集合U(或集合V)内没有连边,在集合E内,ui∈U,vj∈V.一个等效且更直观的定义是给二分网络的节点分配2种颜色中的一种,如深灰色或浅灰色,且相同颜色的节点之间没有直接连边.

用p表示深灰色节点的数量,q表示浅灰色节点的数量,n=p+q.在不失一般性的情况下,假设节点被索引,深灰色节点标记为1,2,…,p,浅灰色节点标记为p+1,p+2,…,n.那么,邻接矩阵

1.2 Barber的二分网络模块度

模块度QB是衡量社团检测质量的标准.一个好的划分(即大多数的边位于社团内,很少的边位于不同社团之间)会得到一个高的分数,而一个糟糕的划分会得到一个低的分数.模块度是在社团结构不变的情况下,同一社团内节点间实际连边比例与随机2点间连边比例期望值的差值.在零模型中,节点i和j之间存在边的概率为P,

那么模块度矩阵是非对角形式的矩阵,即

(1)

其中:gi为节点i分配到的社团;hj为节点j分配到的社团;δij为Kronecker-delta函数.

2 二分网络的SVD-MS社团检测算法

2.1 谱算法聚类

现在考虑将n个节点的网络划分为k个社团的问题.一个好的划分应具有高模块度,现通过寻找最大的模块度来实现好的划分.注意到(1)式中的delta函数可以写成

(2)

2.2 向量划分

(3)

(4)

这样,模块度可改写成

(5)

(6)

2.3 算法描述

基于向量划分思想并结合二分网络的拓扑结构,构建以下SVD-MS算法:

图1 描述向量分区启发式操作的工作原理Fig. 1 Working Principle of Vector Partitioning Heuristic Operation

Step4更新群向量.

Step5从step 2开始重复,直至群向量停止改变(或者达到最大迭代次数时停止).

3 实证研究

为了检验SVD-MS算法的有效性,在3个真实世界的网络中进行算法评估,并与LPBRIM算法[7]、Asymlntimacy算法[10]、BiAttractor算法[11]、SVD-BRIM算法[12]、BRIM算法[6]、SCA算法[13]和BiNeTClus算法[14]作比较.

3.1 Southern Women网络

图2 Southern Women网络在SVD-MS算法下的社团划分Fig. 2 Community Detection of Southern Women Network Through SVD-MS Algorithm

Southern women数据集[15]是二分网络社团检测算法最常用的数据集之一.该网络中有18名妇女和14个活动,用妇女是否参加过活动的关系构建连边,共有93条连边.

SVD-MS算法将Southern women网络分成了3个规模大小不一的社团.社团检测结果的拓扑结构如图2所示.图2中白色、浅灰色和深灰色表示社团,方形表示妇女,圆形表示活动.经计算,SVD-MS,LPBRIM,Asymlntimacy,BiAttractor,SVD-BRIM,BRIM,SCA,BiNeTClus算法的模块度分别为0.345,0.313,0.333,0.345,0.321,0.345,0.333,0.313.由此可知,SVD-MS算法的模块度与BRIM和SVD-BRIM算法的相同,略高于其他5种算法,说明SVD-MS算法能较精准地识别Southern women网络中的社团结构.

3.2 Disease-Gene网络

图3 Disease-Gene网络在SVD-MS算法下的社团划分Fig. 3 Community Detection of Disease-Gene Network Through SVD-MS Algorithm

Kwang-II等[16]通过探讨致病基因与遗传疾病的关系构建了Disease-gene二分网络.该网络中有19个遗传疾病和19个致病基因,共有49条连边.

SVD-MS算法将Disease-gene网络分成了3个规模大小不一的社团.社团检测结果的拓扑结构如图3所示.图3中白色、浅灰色和深灰色表示社团,方形表示疾病,圆形表示致病基因.经计算,SVD-MS,LPBRIM,Asymlntimacy,BiAttractor,SVD-BRIM,BRIM,SCA,BiNeTClus算法的模块度分别为0.514,0.348,0.348,0.348,0.415,0.415,0.379,0.415.由此可知,SVD-MS算法的模块度高于其他7种算法,说明SVD-MS算法能较精准地识别Disease-gene网络中的社团结构.

3.3 American Revolution网络

American revolution数据集[17]包含5个组织和136个成员的信息.成员与组织之间的关系构建成二分网络,该网络共有160条连边.

SVD-MS算法将America revolution网络分成了5个规模大小不一的社团(表1).表1中1～136为成员,137～141为组织.经计算,SVD-MS,LPBRIM,Asymlntimacy,BiAttractor,SVD-BRIM,BRIM,SCA,BiNeTClus算法的模块度分别为0.602,0.591,0.48,0.601,0.595,0.602,0.601,0.591.由此可知,SVD-MS算法的模块度与BRIM算法的相同,比Asymlntimacy算法的高23.3%,略高于其他5种算法,说明SVD-MS算法能较精准地识别America revolution网络中的社团结构.

表1 America Revolution网络在SVD-MS算法下的社团划分结果Table 1 Community Detection Results of the American Revolution Network Through SVD-MS Algorithm

4 结语

从保留二分网络的原始信息和提高社团检测的模块度的角度出发,设计了一种基于谱聚类的社团检测算法(SVD-MS).该算法用线性代数原理作为社团检测的基础,易于形式化分析.在真实世界的网络中将SVD-MS与L-P,Asymlntimacy,BiAttractor,SVD-BRIM,BRIM,SCA,BiNeTClus等7种算法进行对比实验,结果表明,在保留二分网络原始信息的情况下,相比其他算法,SVD-MS算法更能有效地对二分网络实现社团划分.由于SVD-MS算法需要事先给定二分网络社团的数量,然后通过寻求最大模块度来找到社团划分的最优结果,而社团数量很难确定,目前只能进行多次重复实验才能找到最优结果,因此笔者下一步将着重探索确定社团数量的方法.