1
$\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$.

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.

$\endgroup$
1
$\begingroup$

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>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$.
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$ – Matthieu Latapy Mar 22 at 6:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.