根据网络(图)的矩阵判断网络是否连通

Question

如何从给定的can矩阵中确定一个双模网络是否连通？

当然，一旦创建了一个数据结构，就可以找到它--但是有任何数学解决方案吗？

我发现，对于n×n矩阵(单模网络)，它很简单:解是：M * M，然后查看结果矩阵中的对角线。如果对角线上有任何零，那么它就没有连接。是真的吗？

你对这两个问题的建议是什么？

Answer 1

对于单模网络来说，这并不是那么简单，但你已经很接近了。

网络矩阵M本身告诉您哪个节点在一个步骤中连接到哪个其他节点。M * M告诉您哪个节点在两个步骤中连接到哪个其他节点，M ^ 3是否在三个步骤中连接，依此类推。“精确”很重要，因为如果节点没有连接到自己(零对角线元素)，那么M * M不仅会获得两步连接，而且还会失去一步连接。

因此，如果所有节点都连接到自己，则产品(电源)更有用：

A = (M + eye(size(M)) > 0)

此步骤还将加权矩阵转换为纯邻接矩阵。现在

(A ^ i > 0)

提供两个节点是否在i步骤中连接或更少连接的信息。在具有n = size(M, 1)节点的网络中，两个节点之间的距离最多可以是n - 1步骤。因此

C = (A ^ (n - 1) > 0)

提供两个节点是否完全连接的信息。如果没有一对未连接的节点，即

connected = (sum(C(:)) == N ^ 2)

我不知道如何在双模式网络中定义连接性.一种简单的方法就是忽略这两种类型的节点之间的差异，并将它们都看作是单模网络的一部分。如果M是大小为[m, n] = size(M)的原始双模网络矩阵，那么

M = [zeros(m, m) , M ; M' ; zeros(n, n)];

将其转换为描述相应的(m+n)x(m+n)单模网络的矩阵.

这些矩阵幂不仅可以告诉你整个网络是否连接，如果不是，它们也可以用来寻找连接的子网络(网络集群)。由于矩阵的幂的行为与它的谱分解密切相关。( 内胚层)，这一思想导致了谱聚类的出现。有关加权同步网络的应用程序，请参见例如arXiv:0706.3375。