代码之家 › 专栏 › 技术社区 › user1842853

奇异值分解-社会网络分析

svd social-networking .net c#

2

user1842853 · 技术社区 · 12 年前

我有一个由邻接矩阵表示的非常大的节点网络。我想减少网络中的节点数量,以包括更重要的节点。我知道SVD可以帮助我实现这一点,我已经使用ILNumerics库在邻接矩阵上运行SVD()方法。

有人能简单地向我解释一下输出是如何帮助我减少网络规模的吗?SVD过程给我留下了一个大小相同的矩阵,其递减值在对角线上从约2到许多0之间。我如何知道要删除哪些被认为不重要的维度?

我可能在整个过程中做得不正确,所以任何帮助都将不胜感激!网上的许多解释很快就变得非常混乱。

1 回复 | 直到 12 年前

1

bigge 12 年前

我对ILNumerics不太熟悉,所以我会尝试解释SVD在您的情况下通常能做什么。首先 Wikipedia 给出了SVD可能应用的一些基本信息。在您的案例中,关于“范围、空空间和秩”和“低秩矩阵近似”的部分特别令人感兴趣。奇异值分解可以帮助您确定 真实的 系统矩阵的等级。如果你的邻接图是稀疏的,那么你的系统矩阵(比如N乘N矩阵)的秩M可能小于N。在这种情况下,你可以计算它的低秩近似。也就是说,你构造了一个M乘M(M<N),其中你忽略了N-M最小的本征值,因为它们对你的结果只有很小的影响。在这种情况下,“小”的含义当然很大程度上取决于您的应用程序。

编辑:在您的示例数据中,您的原始矩阵A已分解为A=outU svdOut outV。对角矩阵svdOut由A的特征值奇异值组成,而outU和outV的列/行分别是A的左奇异向量和右奇异向量。在您的示例中,奇异值分别为1.61803、1.41421、0.61803和0(两次)。因此,原始矩阵的秩由非零奇异值的数量给出(在您的示例中为三个)。因此,您可以定义矩阵B=outU svdOut*outV,其中星号表示已删除最低有效奇异值。例如,您可以决定忽略最小的特征值,因此

svdOut* =
| 1.61803  0        0  0  0 | 
| 0        1.41421  0  0  0 | 
| 0        0        0  0  0 |
| 0        0        0  0  0 |
| 0        0        0  0  0 |

然而,仔细想想,我认为邻接矩阵的SVD不会直接给出你想要的东西。你必须以某种方式定义 重要的 节点实际上在您的上下文中。

第2版(针对下面的评论):SVD不会直接向您提供有关节点的信息,而是提供有关矩阵的信息。奇异向量形成了一个正交基,可以用来以不同的形式表达原始矩阵。奇异值可以为您提供这些向量的影响有多大的信息。同样, Wikipedia 可能会帮助你了解如何解释这一点。回到你最初的问题,我想一个简单的SVD并不是你真正想要的。