在二分图中量化成对、三对等重叠

Question

我正在处理一个邻接矩阵，用于总结二分图，其中行是图中的一组，列是第二组。如果一行和一列之间有一条边，则该值为1，否则为0。因此，我的矩阵如下所示：

  X Y Z
A 0 1 0
B 0 0 1
C 1 1 1

我希望能够量化1...S选择行中行重叠的分布情况，例如，在上面的矩阵中，平均成对重叠将是（0+1/3+1/3）/ 3 = 2/9，三个以上的行重叠(这里可能有更好的说法)将是0。

我正在寻找一个高效的算法来处理N行和M列。目前为止，我所想出的方法通常不能超过仅执行所有可能的行组合。

我可以查看每个列的重叠概率 - 因此，每个长度为S的列中至少包括1个项的可能组合数量除以总行组合数之类的东西。但我还没有想到一种使用这些信息得出适当答案的方法。

我一直在思考是否有某种扫描算法或其他方式可以解决任意值S的问题，但缺乏关于算法的培训，无法即刻知道。你有什么想法或参考资料吗？

谢谢！

- jebyrnes

---

听起来是一个有趣的问题，但你应该详细说明“量化行重叠分布”的含义，不仅仅是通过例子来解释，因为我并不清楚这意味着什么，即使我试图推导出这些例子的方法。 - Kaganar

我对k行的平均重叠感兴趣，但如果可能的话，我也想研究其他时刻。平均值已经解决（见下文），但其他时刻我不太确定。 - jebyrnes

我的最终目标是能够说，好的，如果你想让三列具有1或更高的值，那么你只需要一行的概率是多少？两行呢？三行呢？等等。 - jebyrnes

Answer 1

我认为您可以通过建立一个直方图来高效地计算每列中总共有多少个1。以您的例子为例：

  X Y Z
A 0 1 0
B 0 0 1
C 1 1 1

如果你对列求和，分别得到1、2和2。 要找到成对相似性的平均值，可以考虑在每个列上找到相似度的平均值，然后取这些平均值的平均值。 在这种情况下，要找到成对相似性，您需要询问每个列有多少个元素对。 对于X列，这是0。 对于Y列，这是1，对于Z列也是1。 如果我们计算(0/3 + 1/3 + 1/3) / 3，就会得到所需的2/9。 要找到三方面的相似性，您需要询问每个列中有多少个三元组。 每个都为0，因此平均值为0。

之所以有效，是因为您想要的总和是

（所有可能的k行组合的总和）（每行上的列匹配数/列数）/ k组合数

您可以将其分解为

（所有可能的k行组合的总和）（每行上的列匹配数）/（k组合数*列数）

然后可以交换这个第一次求和，以获得

（所有列的总和）（与此列匹配的k行组合数）/（k组合数*列数）

计算此总和要容易得多，因为您只需执行以下操作：

1.计算列和。

2.对于每个列，找到从中选择k个元素的方法有多少种（这等于n choose k），然后将其除以列数。

3.将此总数除以k行集合的数量（这是行数choose k）。

您可以使用choose函数的定义相对有效地计算n choose k（时间为O（n + k））。 如果您有R行和C列，则总工作量为：

1.在每行上对列求和：O（RC）

2.对于列，计算k元素组合的数量：O（R + k），因为总和最多为R。

3.在所有列上计算此总和：O（CR + Ck）

4.将它们平均在一起：O（C）

这会给出O（CR + Ck）的总运行时间。 如果您将k限制为行数，则我认为它在时间O（CR）内运行。

希望这可以帮助你！

- templatetypedef

---

这太棒了。像魔法一样运作。现在我要继续回答这个问题的下一部分......我的最终目标是能够说，好的，如果你想让三列的值大于等于1，那么你只需要1行的概率是多少？2行？3行？等等。我不确定这个信息是否可以从这种方法中得出。 - jebyrnes

Answer 2

设n为行数，m为列数。所有组合的总数 = 列数 * 行的组合数 = m*n*(n-1)/2

设si为第i列的总和。匹配的总数量 = si*(si-1)/2。

因此解决方案为：( s1*(s1-1)/2 + s2*(s2-1)/2 +...+sm*(sm-1)/2 ) / (m*n*(n-1)/2)

例如，在您的情况下分母 = 3*3*2/2 = 9

s1 = 0, s2=2, s3=2

分子为：(0+1+1) = 2

答案= 2/9

对于一般的p路交点，改变公式。

( choose(s1,p), choose(s2,p)+...+choose(sm,p) ) / (m*choose(n,p))

其中choose(k,p) = k!/((k-p)!p!)

- ElKamina

---

虽然这对于一对工作，但是如何扩展到三方重叠或P方重叠呢？ - jebyrnes

请注意，如果您只是使用每个组合的可能组合数，例如（choose（s1，3）+ choose（s2，3）+ ... choose（sm，3））/ choose（n，3），那并不完全有效。 - jebyrnes

@jebyrnes 只需使用一个通用的 n 选 p 函数。 - ElKamina

也许是我的实现有问题。但是，这个答案或多或少地与上面的答案相一致。两者都很好，而且非常高效 - 谢谢！现在进入问题的下一部分（请参见上面的评论）。 - jebyrnes