2.3.2基于潜在语义算法改进
大家知道计算单个极端特征值和其对应的特征向量有幂迭代、反幂迭代等比较高效的算法。根据对于算法的描述，问题在于要计算好几个的极端特征对。因此一种可行的方法，可以连续地将极端特征对通过幂迭代逐一计算出来，得益于实对称矩阵良好的袋鼠性质和本问题的特征性。因此可以通过适当的变换，将原GMC问题转化为对称矩阵的特征对问题，从而使问题迎刃而解，现在来看如何进行这种转换。
由于忽略了链接的方向性，生成的邻接矩阵C本身就是一个对称矩阵，但是由于GMC的第l步要进行规范化．导致规范化后的邻接矩阵(不妨记为A)对称性消失，从而给应用幂迭代算法造成困难。现在还原这一过程，假设C的各行元素和组成的对角阵为D，那么就有
(3)假设和是A的一对特征对，由上式，有
（4）
注意到D为正定的对角阵．因此D可以像单个正整数一样进行指数运算。根据式(4)的结果，可以发现，A的特征对(，)对应于D1/2CD-1/2的一个特征对(，D1/2 )。本文来自辣,文'论#文^网，
毕业论文 www.751com.cn由于式(4)的推理步步都是可逆的，因此A的特征对就和D1/2CD-1/2的特征对建立起一一对应的关系。这样可以先求D1/2CD-1/2的特征对，再转而求A的特征对，中间只需要经过一个简单的变换。
接下来再来看D1/2CD-1/2这个矩阵．由于C是对称阵，D是对角阵(当然也就对称)，因此D1/2CD-1/2也是对称阵，这样它的特征对通过幂迭代便不难求出；另外，C是稀疏矩阵，D1/2CD-1/相当于在C两边各乘以一个对角阵．C的每个元素只会放大或者缩小一定的倍数，丝毫不影响其稀疏性，这是这个变换的另一个优点，保持了原矩阵的稀疏性。
此外还要注意的一点是GMC中要求的是两到三个除1以外的最大特征值．而幂迭代求出的是绝对值最大的特征值，这其中只要做一个简单的变换就可以满足要求。由于A是规范化的，由矩阵的圆盘定理易知其谱半径为1，即所有的特征值都落在[-1，1]区间内，只需要再简单地对A做一个shift，让A变作A+1，就可以保证所有的特征值都是正的．这时候再作幂迭代就可以了。
上一页 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 下一页
GN算法的设计与源代码+网络社区发现算法分析与比较 第8页下载如图片无法显示或论文不完整，请联系qq752018766
