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.
My two cents:

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&gt;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)}&gt;\alpha$ can have a Jaccard similarity higher than $\alpha$.