Quantifying pairwise, threewise, etc. overlap in a bipartite graph

Question

I'm working with an adjacency matrix summarizing a bipartate graph, such that rows are one group in the graph and columns are the second group. If a row and column have an edge between them, the value is 1, and if not, it is 0. So, my matrices look at follows

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

etc.

I want to quantify distribution of overlap in the rows for 1...S selected rows. So, for example, in the above matrix, the average pairwise overlap would be (0+1/3+1/3)/3 = 2/9, the three-wise overlap (there must be a better word for this) would be 0.

I'm searching for an efficient algorithm to do this for N rows and M columns. So far, nothing that I've come up with can typically outperform just doing all possible row combinations.

I can do something like look at the probability of overlap for each column - so, something like the number of possible combinations in each column of length S that will include at least 1 item divided by the total number of combinations of rows. But I've not figured out a way to use this information to arrive at the proper answer.

I've been thinking there must be some sort of scanning algorithm or otherwise that will address this problem for arbitrary values of S, but lack the training in algorithms to know it off of the top of my head. Any thoughts or references?

Thanks!

Answer 1

I think that you can compute this fairly efficiently by building up a histogram that tracks how many total 1's there are in each column. Take your example:

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

If you sum the columns, you get 1, 2, and 2, respectively. To find the average pairwise similarity, you can think about finding the average similarity across each column, then taking the average of that. In this case, to find the pairwise similarity, you would ask, for each column, how many pairs of elements there are. For column X this is 0. For column Y this is 1, and for column Z this is 1 as well. If we compute (0/3 + 1/3 + 1/3) / 3, you get 2/9, as required. To find the three-way similarity, you ask how many triplets there are in each column. There are 0 in each, so the average is 0.

The reason that this works is that the sum you want is

(Sum (all possible k-tuples of rows) (# column matches across rows / num columns)) / num k-tuples

You can factor this out to get

(Sum (all possible k-tuples of rows) (# column matches across rows)) / (num k-tuples * num columns)

This first sum can then be interchanged to get

(Sum (all columns) (# k-tuples of rows that match this column)) / (num k-tuples * num columns)

Computing this sum is a lot easier, because you can just do this:

1. Compute the column sums.
2. For each column, find how many ways there are to pick k elements from it (this is equal to n choose k), then divide it by the number of columns.
3. Divide this total by the number of k-element sets of rows there are (this is the number of rows choose k).

You can compute n choose k fairly efficiently using the definition of the choose function (in time O(n + k)). If you have R rows and C columns, the total work is:

1. Summing columns across each row: O(RC)
2. For column, computing the number of k-element combinations: O(R + k), since the sum is at most R.
3. Across all columns, computing this total: O(CR + Ck)
4. Averaging them together: O(C)

This gives a total runtime of O(CR + Ck). If you bound k by the number of rows, then this runs in time O(CR), I think.

Hope this helps!

Answer 2

Let n be the number of rows and m be the number of columns. Total number of combinations = m * combinations of rows = m*n*(n-1)/2

Let si be the sum of ith column. The total number of matchings = si*(si-1)/2 .

So the solution is: ( s1*(s1-1)/2 + s2*(s2-1)/2 +...+sm*(sm-1)/2 ) / (m*n*(n-1)/2)

For example, in your case denominator = 3*3*2/2 = 9

s1 = 0, s2=2, s3=2

Numerator is: (0+1+1) = 2

Answer= 2/9

For a general p-way intersection, change the formula.

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

where choose(k,p) = k!/((k-p)!p!)