# Bipartite graph projections, with threshold

Let $$G=(\top,\bot,E)$$ be a bipartite graph: $$E\subseteq \top\times\bot$$.

The projections $$G_\bot = (\bot,E_\bot)$$ and $$G_\top = (\top,E_\top)$$ of $$G$$ are defined as follows: two vertices are linked together if they have a common neighbor in $$G$$.

Weighted projections are defined by adding the following weight function: $$\omega(u,v)$$ is the number of common neighbors of $$u$$ and $$v$$ in $$G$$.

For any $$k$$, the $$k$$-projections $$G^k_\bot = (\bot,E^k_\bot)$$ and $$G^k_\top = (\top,E^k_\top)$$ are defined as follows: two vertices are linked together if they have at least $$k$$ common neighbors in $$G$$.

Assume that both $$G$$, $$G_{\bot}$$, and $$G_{\top}$$ are sparse.

Questions:

• What is the (time and space) complexity of building $$G_\bot$$ and $$G_\top$$?
• Is it possible to build their weighted version with same complexity?
• Is there a significantly better way to build $$G^k_\bot$$ and $$G^k_\top$$ than first building weighted $$G_\bot$$ and $$G_\top$$ and then removing the edges of weight lower than $$k$$?

These questions are important in social network analysis and related fields. For instance, many studies consider co-authorship networks: $$G$$ is graph where authors are linked to papers, and $$G^k_{\bot}$$ is the graph of authors who co-signed at least $$k$$ papers.

• The worst case of building $$G_\top$$ is in $$\Omega(n^2)$$ time and space: assume $$\bot$$ contains a single node linked to all nodes in $$\top$$.
• Maybe you are not looking for a worst case complexity? Then, $$O(\sum_{u\in\bot}(d_u)^2)$$ time to build $$G_\top$$ by listing all edges $$u,v$$ such that $$u$$ and $$v$$ are neighbors of the same node in $$\bot$$.
• You can use some pruning in the case $$k$$ is large with the following algorithm. For each node $$u\in \top$$ such that its degree is $$k$$ or more: For each neighbor $$v$$ of $$u$$: For each neighbor $$w$$ of $$v$$ such that $$w>u$$: List the edge $$u,w$$. Then postprocess the listed edges to find the ones that appear $$k$$ times or more. Here is a code that does something like that efficiently.
• Some related code here for simple graphs (not bipartite, but can be adapted) where we look for pairs of nodes with Jaccard similarity higher than a threshold. It seems that Jaccard allows to leverage a more aggressive pruning: only a pair of nodes $$u,v$$ such that $$\frac{\min(d_u,d_v)}{\max(d_u,d_v)}>\alpha$$ can have a Jaccard similarity higher than $$\alpha$$.
• Nice answer, thank you! The $n^2$ bound is not what I am looking for, as the considered graphs are sparse; and the $\sum d^2$ is frustrating, as it may end up to be $n^2$, right? Your pruning methods are closer to what I am looking for, and maybe there is nothing better... It may lead to a complexity expressed in function of the input or output degree distribution, I think. Thanks for the implementation too! I add that your remark on the fact that other kinds of weights may be easier to compute is very interesting! This extends my question nicely! – Matthieu Latapy Mar 22 at 6:14