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$.
- 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?