<p>My two cents:</p>
<ul>
<li>The worst case of building <span class="math-container">$G_\top$</span> is in <span class="math-container">$\Omega(n^2)$</span> time and space: assume <span class="math-container">$\bot$</span> contains a single node linked to all nodes in <span class="math-container">$\top$</span>.</li>
<li>Maybe you are not looking for a worst case complexity? Then, <span class="math-container">$O(\sum_{u\in\bot}(d_u)^2)$</span> time to build <span class="math-container">$G_\top$</span> by listing all edges <span class="math-container">$u,v$</span> such that <span class="math-container">$u$</span> and <span class="math-container">$v$</span> are neighbors of the same node in <span class="math-container">$\bot$</span>.</li>
<li>You can use some pruning in the case <span class="math-container">$k$</span> is large with the following algorithm. For each node <span class="math-container">$u\in \top$</span> <strong>such that its degree is <span class="math-container">$k$</span> or more</strong>: For each neighbor <span class="math-container">$v$</span> of <span class="math-container">$u$</span>: For each neighbor <span class="math-container">$w$</span> of <span class="math-container">$v$</span> such that <span class="math-container">$w&gt;u$</span>: List the edge <span class="math-container">$u,w$</span>. Then postprocess the listed edges to find the ones that appear <span class="math-container">$k$</span> times or more. <a href="https://github.com/maxdan94/comcore" rel="nofollow noreferrer">Here</a> is a code that does something like that efficiently.</li>
<li>Some related code <a href="https://github.com/maxdan94/NeighSim" rel="nofollow noreferrer">here</a> 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 <span class="math-container">$u,v$</span> such that <span class="math-container">$\frac{\min(d_u,d_v)}{\max(d_u,d_v)}&gt;\alpha$</span> can have a Jaccard similarity higher than <span class="math-container">$\alpha$</span>.</li>
</ul>

CC BY-SA 4.0
2021-03-22T06:14:53.030Z
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!
Matthieu Latapy
CC BY-SA 4.0
2021-03-21T23:01:45.757Z
2021-03-21T23:06:52.507Z
2021-03-21T23:06:52.507Z
maxdan94
<p>Let <span class="math-container">$G=(\top,\bot,E)$</span> be a <em>bipartite</em> graph: <span class="math-container">$E\subseteq \top\times\bot$</span>.</p>
<p>The <strong>projections</strong> <span class="math-container">$G_\bot = (\bot,E_\bot)$</span> and <span class="math-container">$G_\top = (\top,E_\top)$</span> of <span class="math-container">$G$</span> are defined as follows: two vertices are linked together if they have a common neighbor in <span class="math-container">$G$</span>.</p>
<p><strong>Weighted projections</strong> are defined by adding the following weight function: <span class="math-container">$\omega(u,v)$</span> is the number of common neighbors of <span class="math-container">$u$</span> and <span class="math-container">$v$</span> in <span class="math-container">$G$</span>.</p>
<p>For any <span class="math-container">$k$</span>, the <strong><span class="math-container">$k$</span>-projections</strong> <span class="math-container">$G^k_\bot = (\bot,E^k_\bot)$</span> and <span class="math-container">$G^k_\top = (\top,E^k_\top)$</span> are defined as follows: two vertices are linked together if they have at least <span class="math-container">$k$</span> common neighbors in <span class="math-container">$G$</span>.</p>
<p>Assume that both <span class="math-container">$G$</span>, <span class="math-container">$G_{\bot}$</span>, and <span class="math-container">$G_{\top}$</span> are <strong>sparse</strong>.</p>
<p><strong>Questions:</strong></p>
<ul>
<li>What is the (time and space) complexity of building <span class="math-container">$G_\bot$</span> and <span class="math-container">$G_\top$</span>?</li>
<li>Is it possible to build their weighted version with same complexity?</li>
<li>Is there a significantly better way to build <span class="math-container">$G^k_\bot$</span> and <span class="math-container">$G^k_\top$</span> than first building weighted <span class="math-container">$G_\bot$</span> and <span class="math-container">$G_\top$</span> and then removing the edges of weight lower than <span class="math-container">$k$</span>?</li>
</ul>
<p>These questions are important in social network analysis and related fields. For instance, many studies consider co-authorship networks: <span class="math-container">$G$</span> is graph where authors are linked to papers, and <span class="math-container">$G^k_{\bot}$</span> is the graph of authors who co-signed at least <span class="math-container">$k$</span> papers.</p>

<graph-theory><graph-algorithms><space-complexity><network-modeling><bipartite-graphs>
Bipartite graph projections, with threshold
Matthieu Latapy
# Bipartite graph projections, with threshold

(Asked by: username_0 on 2021-03-21)

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.

**Tags:** graph-theory, graph-algorithms, space-complexity, network-modeling, bipartite-graphs


---

## 1 answers

### Answer by username_1 on 2021-03-21. Score: 1

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](https://github.com/username_1/comcore) is a code that does something like that efficiently.
* Some related code [here](https://github.com/username_1/NeighSim) 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$.

> **Comments:**
> **username_0**: 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!  

---

