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

Spectral approximation community search for bipartite network

社区搜索旨在从网络中查找给定查询节点所在的局部社区,基于谱的社区搜索方法是流行的方法之一。现有基于谱的社区搜索方法多面向简单网络而无法处理具有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.