基于谱图小波的多尺度社区搜索方法_闫彩瑞.pdf

基于谱图小波的多尺度社区搜索方法*闫彩瑞,马慧芳,李青青(西北师范大学计算机科学与工程学院,甘肃 兰州 7 3 0 0 7 0)摘 要:作为可捕获用户个性化信息的网络分析任务,社区搜索旨在挖掘满足内聚性要求的查询节点所在的社区。大多数现有社区搜索方法仅能定位查询节点所在的单尺度社区。据此,设计了一种基于谱图小波的多尺度社区搜索方法,利用谱图小波和局部模块度挖掘查询节点所在的多尺度社区。具体地,首先,构建模块度矩阵和拉普拉斯矩阵并进行矩阵分解得到相关特征向量;其次,结合谱图理论和图小波,设计了基于谱图小波的尺度依赖局部模块度;再次,以归一化拉普拉斯矩阵和局部模块度张成的特征空间为支撑,设计了线性规划问题,以求解在给定尺度下与查询相关的稀疏指示向量;最后,利用社区边界截断策略不断添加节点,使得局部模块度最大。人工网络和真实网络上的实验结果表明了方法的高效率和有效性。关键词:多尺度;社区搜索;谱;图小波;局部模块度中图分类号:T P 3 9 1.9文献标志码:Ad o i:1 0.3 9 6 9/j.i s s n.1 0 0 7-1 3 0 X.2 0 2 3.0 6.0 1 8A m u l t i-s c a l e c o mm u n i t y s e a r c h m e t h o d b a s e d o n s p e c t r a l w a v e l e tYAN C a i-r u i,MA H u i-f a n g,L I Q i n g-q i n g(C o l l e g e o f C o m p u t e r S c i e n c e a n d E n g i n e e r i n g,N o r t h w e s t N o r m a l U n i v e r s i t y,L a n z h o u 7 3 0 0 7 0,C h i n a)A b s t r a c t:A s a n e t w o r k a n a l y s i s t a s k t h a t c a n c a p t u r e u s e rs p e r s o n a l i z e d i n f o r m a t i o n,c o mm u n i t y s e a r c h a i m s a t m i n i n g t h e c o mm u n i t y o f q u e r y n o d e s t h a t c a n s a t i s f y t h e c o h e s i o n r e q u i r e m e n t.M o s t o f t h e e x i s t i n g c o mm u n i t y s e a r c h m e t h o d s c a n o n l y l o c a t e a s i n g l e-s c a l e c o mm u n i t y w h e r e q u e r y n o d e s a r e l o c a t e d.A M u l t i-S c a l e C o mm u n i t y S e a r c h m e t h o d b a s e d o n S p e c t r a l W a v e l e t(M S C S_SW)i s p r o p o s e d,w h i c h c a n m i n e t h e m u l t i-s c a l e c o mm u n i t y o f q u e r y n o d e s b y u s i n g s p e c t r a l w a v e l e t a n d l o c a l m o d u l a r i-t y.S p e c i f i c a l l y,f i r s t l y,t h e m o d u l a r i t y m a t r i x a n d t h e L a p l a c i a n a r e c o n s t r u c t e d,a n d d e c o m p o s e d t o o b t a i n t h e r e l e v a n t e i g e n v e c t o r s.S e c o n d l y,b a s e d o n t h e s p e c t r a l t h e o r y a n d t h e g r a p h w a v e l e t,t h e s c a l e-d e p e n d e n t l o c a l m o d u l a r i t y i s d e s i g n e d.T h i r d l y,b a s e d o n t h e n o r m a l i z e d L a p l a c i a n M a t r i x a n d t h e f e a t u r e s p a c e o f l o c a l m o d u l a r i t y,a l i n e a r p r o g r a mm i n g p r o b l e m i s d e s i g n e d t o s o l v e t h e s p a r s e i n d i c a t o r v e c t o r s r e l a t e d t o q u e r y a t a g i v e n s c a l e.F i n a l l y,t h e c o mm u n i t y b o u n d a r y t r u n c a t i o n s t r a t e g y i s u s e d t o a d d n o d e s t o m a x i m i z e t h e l o c a l m o d u l a r i t y.E x p e r i m e n t a l r e s u l t s o n s y n t h e t i c n e t w o r k a n d r e a l-w o r l d n e t w o r k d a t a s e t s d e m o n s t r a t e t h e e f f i c i e n c y a n d e f f e c t i v e n e s s o f t h e p r o p o s e d m e t h o d.K e y w o r d s:m u l t i-s c a l e;c o mm u n i t y s e a r c h;s p e c t r a l;g r a p h w a v e l e t;l o c a l m o d u l a r i t y*收稿日期:2 0 2 1-1 0-1 9;修回日期:2 0 2 2-0 1-2 4基金项目:国家自然科学基金(6 1 7 6 2 0 7 8,6 1 3 6 3 0 5 8);西北师范大学青年教师能力提升计划(NWNU-L KQN 2 0 1 9-2);甘肃省自然科学基金(2 1 J R 7 R A 1 1 4)通信地址:7 3 0 0 7 0 甘肃省兰州市西北师范大学计算机科学与工程学院A d d r e s s:C o l l e g e o f C o m p u t e r S c i e n c e a n d E n g i n e e r i n g,N o r t h w e s t N o r m a l U n i v e r s i t y,L a n z h o u 7 3 0 0 7 0,G a n s u,P.R.C h i n a C N 4 3-1 2 5 8/T PI S S N 1 0 0 7-1 3 0 X 计算机工程与科学C o m p u t e r E n g i n e e r i n g&S c i e n c e第4 5卷第6期2 0 2 3年6月 V o l.4 5,N o.6,J u n.2 0 2 3 文章编号:1 0 0 7-1 3 0 X(2 0 2 3)0 6-1 1 0 6-1 01 引言图作为一种必要的数据结构,常用来表示实体和实体间的关系。一些常见的图已被广泛用于表示不同的关系,如社交网络、生物网络和引文网络,其中节点表示复杂网络中的对象,边表示对象间的交互。图往往存在明显的社区特性,即社区内部连接稠密而社区间连接稀疏。作为网络分析中最重要和最基本的任务之一,社区搜索帮助用户更快地获得个性化的局部内聚结构,其旨在从网络中找到包含给定查询节点的内聚子网络1,2。由于社区搜索从给定的查询节点开始,更关注局部网络结构,因此能够快速得到个性化的局部社区。近年来,已有大量的社区搜索3方法被提出,这些方法多侧重于捕获社区的结构,如k-c o r e4、k-t r u s s5、k-c l i q u e6以及密集连接子图7。然而这些方法仅能检测单尺度的社区。已有一些工作开始着力于多尺度,旨在发现包含查询节点的多尺度社区,从而保证定位到正确的社区。典型的工作有L u o等人8通过对查询节点所在的候选网络不断放缩约束条件,从而得到不同尺度的社区。然而,这种解决方法获得的社区尺度比较机械。另一种研究的主流思想是从谱的角度对社区进行研究,而这种方法可以初步地探索多尺度9 1 2。其中,图的特征值集合被称为谱,主要思想是研究图的相关矩阵的谱性质与图结构间的关系,通过谱刻画图的结构性质。拉普拉斯谱是图谱理论中的一个重要研究领域,拉普拉斯特征值更能反映图的图论性质1 3。谱思想的出现增强了节点的细粒度表示,但是现有的工作仅适用于全局的社区检测任务,还未在局部社区结构上应用。针对以上问题,本文从谱图小波和多尺度2个角度出发,设计了基于谱图小波的多尺度社区搜索方法M S C S_SW(M u l t i-S c a l e C o mm u n i t y S e a r c h m e t h o d b a s e d o n S p e c t r a l W a v e l e t)。该方法面向网络的局部结构,通过谱方法获取节点的细粒度表示,可有效定位包含查询节点的多尺度社区。具体地,首先,构建图的相关矩阵并获取谱,通过谱性质刻画图的结构性质;其次,结合谱图理论和图小波的优势,设计基于谱图小波的尺度依赖的局部模块度;再次,在局部模块度和归一化拉普拉斯矩阵张成的特征空间上应用线性规划,通过稀疏松弛得到与查询节点相关的指示向量;最后,利用社区边界截断策略不断添加节点,从而使目标社区的局部模块度达到最大。遍历所有的尺度依次进行实验,获得包含查询节点所在的多尺度的局部社区。在人工数据集和真实数据集上设计了不同的实验,结果表明了本文方法的有效性。2 基础知识2.1 符号说明和问题定义本文用粗体小写字母表示向量,如x。矩阵用粗体大写字母表示,如A。集合表示为大写斜体字母,如V。标量用斜体小写字母表示,如i。用xi表示向量x中的第i个元素,用Ai j表示矩阵A的第i行、第j列对应位置的元素。给定无向图G=(V,E)是一个n节点网络,其中,V=vii=1,n表示节点集;E=(vi,vj)|vi,vjV 表示边集且|E|=m。G的拓扑结构记作邻接矩阵A,表示节点对间的连边。若(vi,vj)E,则Ai j=1;否则Ai j=0。D为G的对角度矩阵,其中Di i=ki=jiAi j,节点vi的度是ki=n-1j=0Ai j。图G的拉普拉斯矩阵定义为L=D-A,其归一化拉普拉斯矩阵为L L=D-1/2L D-1/2。由于L L是对称矩阵,可将其对角化,其谱由其排序的特征值(l)l=0,n-1组成,且0=012n-1=m a