基于谱聚类的二分网络社团检测算法*
2023-12-21刘晨晨
吉首大学学报(自然科学版) 2023年6期
关键词:检测
刘晨晨,许 英
(新疆财经大学统计与数据科学学院,新疆 乌鲁木齐 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种颜……
登录APP查看全文