代码之家 › 专栏 › 技术社区 › 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,您将同样能够找到列之间的共享连接。

推荐文章

Ahmad · 此图中有多少强连通组件?

7 年前

user8303828 · 如何使用Dijkstra找到更多路线?

7 年前

LMHull · 使用apoc。周期性迭代以基于Neo4j中的计算创建新关系

7 年前

André · 如何在Neo4j中存储的Web图中进行社区检测

7 年前

erans · 有向图中穿过特定顶点的最轻圆

7 年前

AnoHito · 寻找图算法的封闭部分

7 年前

Abbas Perçin · 计算具有“E”边的所有可能的连通平面图

7 年前

Ben · 聚类和匹配之间有什么区别?

7 年前

toofun · 图匹配算法

7 年前

Etherian · 我如何变异我正在循环的结构?

7 年前