基于谱图小波的多尺度社区搜索方法

A multi-scale community search method based on spectral wavelet

作为可捕获用户个性化信息的网络分析任务,社区搜索旨在挖掘满足内聚性要求的查询节点所在的社区。大多数现有社区搜索方法仅能定位查询节点所在的单尺度社区。据此,设计了一种基于谱图小波的多尺度社区搜索方法,利用谱图小波和局部模块度挖掘查询节点所在的多尺度社区。具体地,首先,构建模块度矩阵和拉普拉斯矩阵并进行矩阵分解得到相关特征向量;其次,结合谱图理论和图小波,设计了基于谱图小波的尺度依赖局部模块度;再次,以归一化拉普拉斯矩阵和局部模块度张成的特征空间为支撑,设计了线性规划问题,以求解在给定尺度下与查询相关的稀疏指示向量;最后,利用社区边界截断策略不断添加节点,使得局部模块度最大。人工网络和真实网络上的实验结果表明了方法的高效率和有效性。

As a network analysis task that can capture user’s personalized information,community search aims at mining the community of query nodes that can satisfy the cohesion requirement.Most of the existing community search methods can only locate a single-scale community where query nodes are located.A Multi-Scale Community Search method based on Spectral Wavelet(MSCS_SW)is proposed,which can mine the multi-scale community of query nodes by using spectral wavelet and local modularity.Specifically,firstly,the modularity matrix and the Laplacian are constructed,and decomposed to obtain the relevant eigenvectors.Secondly,based on the spectral theory and the graph wavelet,the scale-dependent local modularity is designed.Thirdly,based on the normalized Laplacian Matrix and the feature space of local modularity,a linear programming problem is designed to solve the sparse indicator vectors related to query at a given scale.Finally,the community boundary truncation strategy is used to add nodes to maximize the local modularity.Experimental results on synthetic network and real-world network datasets demonstrate the efficiency and effectiveness of the proposed method.