Correction

This article refers to:

Structural cohesion and embeddedness in two-mode networks

Article title: Structural cohesion and embeddedness in two-mode networks

Authors: Benjamin Cornwell and Jake Burchard

Journal: The Journal of Mathematical Sociology

Bibliometrics: Volume 43, Issues 4, pages 179–194

DOI: 10.1080/0022250X.2019.1606806

Explanation of correction

Theorem 3.1 and Corollary 3.1.1 in the article are false. While Theorem 3.1 correctly states that $\kappa \left(N\right)\le k$, the reverse inequality is not necessarily true (a family of counterexamples can be produced to show this). It should be noted that these statements, while false, are nevertheless tangential to the main emphasis of the paper, which is that cohesion in two-mode networks should be studied without one-mode projections, and that this can be done using both what we call “two-sided” and “one- sided” approaches. We have replaced Theorem 3.1 and Corollary 3.1.1 with the following new, correct theorems and accompanying text.

New Text

Theorem 3.1. Let $N$ be a two-side $k$-connected two-mode network with disjoint sets of nodes $A$ and $B$, let $N$’s regular one-mode connectivity be $\kappa \left(N\right)$, and let $\delta$ be the minimum degree of $N$. Then, $\kappa \left(N\right)\le k\le \delta$.

Proof. We prove the result by contradiction. If it were the case that $\kappa \left(N\right)>k$, then $\kappa \left(N\right)>min\left\{S_A,S_B\right\}$, so $\kappa \left(N\right)>S_A$ or $\kappa \left(N\right)>S_B$. However, by definition if $S_A$ or $S_B$ nodes are removed from $N$, $A$ or $B$ will become disconnected, respectively, and therefore so will $N$. This leads to a contradiction given that $\kappa \left(N\right)$ is defined as the minimum number of nodes needed to be removed to disconnect $N$. Therefore, $\kappa \left(N\right)\le k$.

Now assume that $k>\delta$. This implies that $min\left\{S_A,S_B\right\}>\delta$, i.e. $S_A>\delta$ and $S_B>\delta$. $\mathrm{\exists }n\in V\left(N\right)$ such that $Deg\left(n\right)=\delta$, where $V\left(N\right)$ is the set of nodes in $N$. Since $N$ is bipartite, $V\left(N_G\left(n\right)\right)\subseteq A$ or $V\left(N_G\left(n\right)\right)\subseteq B$, where $N_G\left(n\right)$ is the neighborhood of node $n$, i.e. the subgraph of $N$ induced by the nodes adjacent to $n$. Without loss of generality, assume $V\left(N_G\left(n\right)\right)\subseteq B$. Then, the subgraph induced by $V\left(N\right)$\$V\left(N_G\left(n\right)\right)$is disconnected, and since $V\left(N_G\left(n\right)\right)\subseteq B$, $S_A\le \delta$, which is a contradiction. Therefore $k\le \delta$.

Theorem 3.2. For a two-side $k$-connected network $N$ with disjoint sets of nodes $A$ and $B$, $\mathrm{\exists }u,v\in V\left(N\right)$ such that $P\left(u,v\right)\le k$, where $P\left(u,v\right)$ is the number of node-independent paths between $u$ and $v$.

Proof. We prove the result by contradiction. Assume that there does not exist such a pair of nodes $u,v$. Then $\mathrm{\forall }u,v\in V\left(N\right),P\left(u,v\right)>k$, or, since $k=min\left\{S_A,S_B\right\}$, $P\left(u,v\right)>S_A$ or $P\left(u,v\right)>S_B$. Without loss of generality, assume that $P\left(u,v\right)>S_A$. By definition, it is possible to remove a set of nodes $S=\left\{n_1,n_2,\dots ,n_{S_A}\right\}\subseteq B$ to disconnect $A$. Consider two nodes $p,q\in A$ which become disconnected after removing $S$. Since $p$ and $q$ are in the same set, and there are $P\left(p,q\right)$ node-independent paths between them, then there must be at least one node from set $B$ on each of those $P\left(p,q\right)$ paths. If we are only allowed to remove nodes from set $B$, at least $P\left(p,q\right)$ nodes from $B$ must be removed to disconnect $p$ and $q$. Since $P\left(p,q\right)>S_A$, we have contradicted our earlier statement that $S_A$ nodes from $B$ could be removed to disconnect $p$ and $q$. Therefore, $\mathrm{\exists }u,v\in V\left(N\right)$ such that $P\left(u,v\right)\le k$.

Applying Theorem 3.2 to Figure 5, since the network in Figure 5 is two-side 1-connected, $\mathrm{\exists }u,v\in V\left(N\right)$ such that $P\left(u,v\right)\le 1$. In other words, there exists some pair of nodes which only have one node independent path between them. For example, nodes $a_2$ and $a_3$: all paths between them must go through $a_1$, so there is only one node independent path between them.

Additional new text

In the Conclusion section of the paper the sentence “(2) One can identify a group that contains a mix of actors from both node sets that remain connected via multiple pathways despite the removal of some specified number of actors from both node sets” should instead read “(2) One can identify a group in which both sets of nodes are robust to the removal of nodes from the other set”.

Acknowledgments

The authors apologize for any inconvenience caused. We thank Paul Dreyer (Senior Mathematician, RAND) for bringing this error to our attention.