量化成對，三向等重疊在一個二部圖

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，但缺乏算法的訓練，以瞭解它的頭頂。任何想法或參考？

謝謝！

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元組）（＃列跨行/ NUM列匹配））/ NUM k元組

您可以考慮此因素出去找

（總和（所有可能的行k元組）（＃列跨行匹配））/（NUM k元組* NUM列）

這第一筆然後可以互換，以獲得

（總和（所有列）（符合此列），該行＃k元組）/（NUM k元組* NUM列）

計算這筆款項是輕鬆了很多，因爲你可以這樣做：

1. 計算列總和。
2. 對於每一列，找出從中選擇k個元素的方式（這等於n選擇k），然後將其除以列數。
3. 將此總數除以有k行元素集的數量（這是行數選擇k）。

可以使用選擇函數的定義（在時間O（n + k）中）來計算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）中運行。

希望這會有所幫助！

Answer 2

設n爲行數，m爲列數。組合總數= 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

Answer = 2/9

對於一般的p路口，改變公式。

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

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