基于谱图小波的多尺度社区搜索方法*闫彩瑞,马慧芳,李青青(西北师范大学计算机科学与工程学院,甘肃兰州730070)摘要:作为可捕获用户个性化信息的网络分析任务,社区搜索旨在挖掘满足内聚性要求的查询节点所在的社区。大多数现有社区搜索方法仅能定位查询节点所在的单尺度社区。据此,设计了一种基于谱图小波的多尺度社区搜索方法,利用谱图小波和局部模块度挖掘查询节点所在的多尺度社区。具体地,首先,构建模块度矩阵和拉普拉斯矩阵并进行矩阵分解得到相关特征向量;其次,结合谱图理论和图小波,设计了基于谱图小波的尺度依赖局部模块度;再次,以归一化拉普拉斯矩阵和局部模块度张成的特征空间为支撑,设计了线性规划问题,以求解在给定尺度下与查询相关的稀疏指示向量;最后,利用社区边界截断策略不断添加节点,使得局部模块度最大。人工网络和真实网络上的实验结果表明了方法的高效率和有效性。关键词:多尺度;社区搜索;谱;图小波;局部模块度中图分类号:TP391.9文献标志码:Adoi:10.3969/j.issn.1007-130X.2023.06.018Amulti-scalecommunitysearchmethodbasedonspectralwaveletYANCai-rui,MAHui-fang,LIQing-qing(CollegeofComputerScienceandEngineering,NorthwestNormalUniversity,Lanzhou730070,China)Abstract:Asanetworkanalysistaskthatcancaptureuser’spersonalizedinformation,communitysearchaimsatminingthecommunityofquerynodesthatcansatisfythecohesionrequirement.Mostoftheexistingcommunitysearchmethodscanonlylocateasingle-scalecommunitywherequerynodesarelocated.AMulti-ScaleCommunitySearchmethodbasedonSpectralWavelet(MSCS_SW)isproposed,whichcanminethemulti-scalecommunityofquerynodesbyusingspectralwaveletandlocalmodulari-ty.Specifically,firstly,themodularitymatrixandtheLaplacianareconstructed,anddecomposedtoobtaintherelevanteigenvectors.Secondly,basedonthespectraltheoryandthegraphwavelet,thescale-dependentlocalmodularityisdesigned.Thirdly,basedonthenormalizedLaplacianMatrixandthefeaturespaceoflocalmodularity,alinearprogrammingproblemisdesignedtosolvethesparseindicatorvectorsrelatedtoqueryatagivenscale.Finally,thecommunityboundarytruncationstrategyisusedtoaddnodestomaximizethelocalmodularity.Experimentalresultsonsyntheticnetworkandreal-worldnetworkdatasetsdemonstrateth...
