正在加载图片...
·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
<<向上翻页向下翻页>>
©2008-现在 cucdc.com 高等教育资讯网 版权所有