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

二部图论-从二部邻接矩阵中找到成对重叠(共享边)

adjacency-matrix discrete-mathematics graph-algorithm graph-theory algorithm

ToBeGeek · 技术社区 · 11 年前

我有一个存储在邻接矩阵中的二分图 A. (100*1900),100行,1900列。简单地说,我表示100行代表因子A,1900列代表因子B。图告诉了100个因子a和1900个因子B之间的联系,因此它是一个二部图。

因此,矩阵是|factorA|*|factorB|,矩阵的维数是100*1900。

我需要找到因子B之间的成对重叠。这样做的一种方式是得到 A. 和转置 A. ,表示为 T(A) .

然后得到 A’=T(A)*A 所以 一个' 将为100*100矩阵,则项目 A’[i,j] 对应于因子A共享的因子B的数量我和因子A j .

为什么上述算法有效?可以提供任何参考出版物或数学证明吗?

1 回复 | 直到 11 年前

Timothy Shields 11 年前

设A'=A*转置(A)。

A'[i,j]是A的第i行和A的第j行的内积。假设这两行如下:

行(A,i)=[0,0,1,0,2,1,1,2,1]
行(A,j)=[1,0,1,1,0,2,1,0]

这两者的元素乘积是

行(A,i).*行(A、j)=[0,0,1,0,0,2,0,0]

两行的内积是这些值的总和2。这就是为什么A'[i,j]是第i行和第j行之间共享连接的数量的直觉。

如果您查看转置(A)*A,您将同样能够找到列之间的共享连接。

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

4 月前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

5 月前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

5 月前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

6 月前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

6 月前

b39b332d · 使用C++标准库实现高效间隔存储

9 月前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

10 月前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

10 月前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

10 月前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

10 月前