面向二分网络的谱近似社区搜索方法  

Spectral approximation community search for bipartite network

作　　者：赵琰 金柳 马慧芳 苏变萍[3] 高玮蔚 ZHAO Yan;JIN Liu;MA Hui-fang;SU Bian-ping;GAO Wei-wei(College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070;China Transport Information Center Co.,Ltd.,Beijing 100088;College of Science,Xi’an University of Architecture and Technology,Xi’an 710043,China)

机构地区：[1]西北师范大学计算机科学与工程学院,甘肃兰州730070 [2]中国交通信息科技集团有限公司,北京100088 [3]西安建筑科技大学理学院,陕西西安710043

出　　处：《计算机工程与科学》2023年第4期743-750,共8页Computer Engineering & Science

基　　金：国家自然科学基金(61762078,61363058);甘肃省自然科学基金(21JR7RA114);甘肃省高校产业支撑项目(2022CYZC-11);西北师范大学青年教师能力提升计划(NWNU-LKQN2019-2)。

摘　　要：社区搜索旨在从网络中查找给定查询节点所在的局部社区,基于谱的社区搜索方法是流行的方法之一。现有基于谱的社区搜索方法多面向简单网络而无法处理具有2类实体关联的二分网络,且面向二分网络的社区挖掘方法多是对网络进行整体划分。据此,提出了面向二分网络的谱近似社区搜索方法,旨在将谱方法引入到二分网络中进而精确定位与查询节点关联紧密的社区。具体来说,首先考虑二分网络中2类实体的关联,基于局部模块度设计了面向二分网络的局部模块度;其次,基于谱图理论,在二分网络上利用融合不同实体关联的模块度矩阵局部逼近特征子空间,设计了适用于二分网络的谱方法;最后,利用结合谱性质的二分网络上的局部模块度,设计了谱子空间中以查询节点集为支撑的稀疏指示向量的线性规划问题,目标社区可通过线性规划问题的求解而获得。真实数据集上的实验结果表明了本文方法有效性和效率。Community search aims to find the local community of a given query node from the network.Community search based on spectrum is one of the popular methods.Existing community search methods based on spectrum are mostly oriented to simple networks,but cannot deal with binary networks with two types of entity association,and the community mining methods oriented to bipartite network are mostly to divide the whole network.Therefore,a spectral approximation community search method for bipartite network is proposed,which aims to introduce spectral method into bipartite network to accurately locate communities closely associated with query nodes.Specifically,firstly,the correlation between two entities in bipartite network is considered,and the local modularity oriented to bipartite network is designed based on the local modularity.Secondly,based on spectral graph theory,a spectral method suitable for bipartite network is designed by using the local approximation feature subspace of modularity matrix fused with different entity associations on bipartite network.Finally,the linear programming problem of sparse indicator vector supported by query node set in spectral subspace is designed by using the local modularity of bipartite network combined with spectral properties.Then the target community can be obtained by solving the linear programming problem.Experiments on real data sets verify the effectiveness and efficiency of the proposed method.

关 键 词：二分网络 社区搜索 谱近似 局部模块度 

分 类 号：TP391.9[自动化与计算机技术—计算机应用技术]