# Bipartite graph projection, 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$$.

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$$?
• For all questions above, is the complexity lower on sparse graphs?
• These problems are basically equivalent to different variants of matrix multiplication. – Willard Zhan Jan 5 at 18:35
• Sure, this is why I specified the last line, the one on sparse graphs; in graph algorithms, we generally prefer to have complexities in terms of $n$ and $m$ (number of vertices and edges), precisely because we do not want to resort to matrices in most cases. – Matthieu Latapy Jan 5 at 19:11