3
$\begingroup$

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?
Improve this question
$\endgroup$
2
  • $\begingroup$ These problems are basically equivalent to different variants of matrix multiplication. $\endgroup$ – Willard Zhan Jan 5 at 18:35
  • $\begingroup$ 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. $\endgroup$ – Matthieu Latapy Jan 5 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.