关键词: 多尺度, 社区搜索, 谱, 图小波, 局部模块度

Abstract: 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.

Key words: multi-scale, community search, spectral, graph wavelet, local modularity