我正在处理一个邻接矩阵,用于总结二分图,其中行是图中的一组,列是第二组。如果一行和一列之间有一条边,则该值为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的问题,但缺乏关于算法的培训,无法即刻知道。你有什么想法或参考资料吗?
谢谢!