Matlab中的二分图连通分量

Question

我有两种数据，X和Y。每个X中的x都与一些Y相关联，而每个Y中的y可能与一些X相关联也可能不与任何X相关联。

X不与其他X相关联，而Y不与其他Y相关联。所以情况看起来像这样：

左边是X，右边是Y。

当我只有一种数据时，我知道如何找到图的连通分量：创建一个N乘以N的矩阵并在其上调用graphconncomp。如果我有两种数据，如何找到所有连接的组件？

- rhombidodecahedron

---

你尝试过使用一个大矩阵，它有numel（X）+numel（Y）乘以numel（X）+numel（Y）个元素吗？应该可以正常工作。 - Daniel

@MohitJain 是的，如果X是Y的子字符串，则存在从X到Y的弧。我该如何利用这个来创建一个N-N矩阵？ - rhombidodecahedron

@DanielR：我尝试过这样做，但矩阵太大了，所以内存不足。在我的试运行中，大约有500个X，但有50,000个Y。虽然矩阵非常稀疏，但也许有一种我不知道的方法可以解决它（我是Matlab新手）。 - rhombidodecahedron

50,000个数据点需要可视化吗？认为可视化会失败，但可以使用稀疏矩阵进行存储：http://www.mathworks.de/de/help/matlab/ref/sparse.html - Daniel

@EarlBellinger 不不不！zeros(50000)会创建一个完整的矩阵，这就是你内存耗尽的原因。只使用sparse！ - Shai

Answer 1

如何将图的亲和矩阵构建为稀疏矩阵：

G = sparse( length(X)+length(Y), length(X)+length(Y) );

这将创建一个尺寸为|X|+|Y|-by-|X|+|Y|的“全零”稀疏矩阵。
如果您输入

>> whos G

你会发现，尽管G大约有50K^2，但几乎不占用内存。

现在你需要使用函数，在X和Y的相应节点之间设置1，然后就可以在G上运行graphconncomp了。

---

二分图情况

为构建二分图的邻接矩阵，你可以（最初）使用一个规模较小（仍然是稀疏的）大小为|X|-by-|Y|的矩阵B。设x=length(X)且y=length(Y)，则：

 B = sparse( x, y ); % if you have an estimate of the number of edges, you can preallocate here

如果节点X(ix)连接到节点Y(jy)，则将入口B( ix, jy )设置为1。
构建完成B后，只需执行以下操作即可使用B形成G。

 G = [ sparse( x, x ), B; B.', sparse(y, y)];

请注意，我不使用zeros来创建全零矩阵，而是使用sparse，因此构建将更具内存效率。

现在，您可以在G上运行graphconncomp。

- Shai

---

如果您知道需要多少边（或者有一个相当准确的猜测），使用spalloc(N,N,numEdges)可能会提高性能，因为所有必要的内存都会预先分配。 - nispio

G的(i,j)单元格代表什么？是X(i)连接到Y(j)吗？还是它必须是类似于X(i)连接到Y(j-length(Y))这样的形式？ - rhombidodecahedron

@EarlBellinger请验证答案中B的大小是否为 |X| - |Y| 或者 x- y。G由四个块构成：大小为x-x的零矩阵，顶部行为B。接着是transposed(B)和大小为y-y的零矩阵。transpose(B)与B.'相同。 - Shai

@EarlBellinger，S 的前 x 个组件是 X 的节点，剩余的 y 个组件是 Y 的节点。 - Shai

谢谢！这就是我需要的！我非常感激！ - rhombidodecahedron