·408 智能系统学报 第6卷 式中：Q表示模块度；m表示图中包含的边数；k:表 xLx=Am(A,A)·n 示编号为i的节点的度(k类似)；：和巴只可取-1 另存在： 或1，当：≠巴是表示将节点i和j划分到不同社区， 反之则属于同一社区. 名=NI-M MI7INT- 1M1·√个NI/1MT=0, 3谱宽松方法解决图割问题 最小化比率割、规范割、平均割以及最大化模块 x好=N1(IM1/IN1)+ 度等，均为P离散最优化问题.幸运的是，谱方法 IM1·(INI/1MI)=n. 可以为该最优化问题提供一种多项式时间内的宽松 于是最小化平均割的问题与比率割的解决方法相 解.这里的“宽松”指的是将离散最优化问题宽松到 似，需求解Lx=x,x的离散化方法也与之类似 实数域，然后利用某种启发式方法将其重新转换为 3.1.3规范割 离散解.下面简要介绍从目标函数到谱方法的演 令指示向量x满足： 变39,46,56】 vol(M) 3.1图的二分割问题 Vvol(N),ie N; 3.1.1比率割 /vol(N) 设比率割为c,考虑一个最小化式(2)的图的二 Vvol(M),i M. 分割问题，令IN1=pm,IMI=gm,其中p,q≥0且满 则有 足p+q=1,簇指示向量x的元素满足： x"Lx =N (N,M).vol(V). =9,eN; 又因为x'Dx=vol(,故可得 L-p,ViE M. xLx =N (N,M). 令E表示一个包含n个元素的常向量，其每个元素 xDx 均设为1.因为拉氏矩阵L的各特征向量正交，而E 令g=DPx,代人上式得 又是L的一个特征向量，故可得x·E=0.若eg是连 g'L. 接N和M2个点集的边，则有x-=q-（-p)= 1g1 :=N(N.M). 1;相反，若eg不是连接N和M2个点集的边，则有 因此最小化规范割相当于求解Lx=入x或者Lx= x:-为=0.从而可得 入Dx,找到归一化拉氏矩阵的第二小特征值对应的 特征向量，然后将其离散化。 一)。 3.1.4模块度 又因为 对于任意无向加权图，令和表示整个图的总权 I x12=q'pn +p'gn (I NII MI )/n,(8) 值，d:代表节点i与其他节点之间的总权值.令B:= 合并式(7)、(8)，根据瑞利商定理可得 Ag-d,d/20,p为指示向量且仅可取1或-1，当m:= 脚器 时表示节点i与j属于同一个簇，反之属于不同的 簇.用于聚类的模块度函数可表达为 也即c≥入2/n,这将意味着图的二分割的实数域解x 由第二小特征值对应的特征向量给出，即求解方程 Lx=入x,找到入2及其特征向量.由于聚类问题是 式中：w可写作w=ol(V)/2=∑Ag,i>j；d可写作 “离散”最优化问题，故而需要将实数域解离散化， d:=vol(V)/=∑A因为∑：d:=2w=∑4，故存在 最简单的离散化方法是阈值法，即： 「V:∈N,x:≥0； B=(4-2)=d-器Σ4)=0， LV:E M,x:<0. 于是可得 3.1.2平均割 与上同理，令指示向量x的分量满足： Q=品豆uu=豆c 即矩阵的所有项之和等于0.进一步有 「TMI/INI,ieN; -√NI/IMT,i∈M. 中)=4-器g 可以得出，在非归一化拉氏矩阵L与平均割之间存 在如下关系： B