Network bipartitioning in the anti-communicability Euclidean space

1.   Introduction

An important set of problems in graph theory are those consisting on splitting the set of vertices $V$ of a graph $G = \left(V, E\right)$ into two sets $V_{1}$ and $V_{2}$, with cardinalities $n = \left|V\right|,$$n_{1} = \left|V_{1}\right|,$ $n_{2} = \left|V_{2}\right|, \;$such that $V = V_{1}\cup V_{2}$ and fulfilling certain requirements about the cut $C$, i.e., the sum of weights of edges which contain one vertex in $V_{1}$ and another in $V_{2}$ ^[1,2]. One of these problems, the min-cut bipartitioning problem, seeks a solution $P = \left\{ V_{1}, V_{2}\right\}$ that minimizes $C$ subject to $(1-\varepsilon)n/2\leq n_{1}, n_{2}\leq\left(1+\varepsilon\right)n/2$, $\varepsilon\geq0$ ^[3]. In particular, if $\varepsilon$ is as small as possible the problem is known as a bisection. Although several exact solution approaches exist, due to the $\mathcal{NP}$-completeness nature of these problems ^[3] we need to rely on heuristic approaches that minimize $C$ ^[3,4]. Particularly, for large networks, there are several heuristics that produce near optimum solutions in reasonable time ^{[5,6,7,8,9,10,11,12,13,14,15,16]}.

The problem of graph bipartitioning also has a history of connections with physics. For instance, statistical physics has benefited from graph theoretical tools to tackle optimal cuts in arrays of coupled spins in which frustration prevents a simple identification of the lowest energy configurations ^[17]. In particular, models such as the Ising one subjected to random fields or its spin glass version demands graph partitioning techniques to identify the ground state of the system and quantify the energy barriers between metastable states. In its turn, these problems have been usually tackled by physicists through statistical mechanics methods, such as simulated annealing techniques ^[18] or the replica method ^[19]. Therefore, the feed-back loop between physics and graph theory is established when the first applications of the latter techniques to the graph partitioning problem appeared ^[20,21,22]. Another promising research avenue involving the contribution of graph partitioning techniques to the analysis of physical systems is the study of multipartite entanglements in quantum systems composed of $n$ $q$-bits ^[23].

More recently, the topic of graph partitioning has received some revival by its study in complex networks. These networks represent many physical, biological, social and engineering systems ^[24,25] where $k$-partitions may appear in different scenarios. In 2006 Newman ^[26] uses eigenvectors of graph-theoretic matrices to identify the bipartite structure present in a network of nouns and adjectives of the novel David Copperfield by Charles Dickens. The "concept" of anti-community then emerges as "groups of nodes which are poorly connected among them but highly connected with the nodes in another group". This vague definition produces that anticommunities are sometimes identified as bipartitions ^[27] and sometimes not necessarily ^{[28,29,30,31]}.

In some situations it is also important to know "how bipartite" a network is. That is, a network that is not bipartite could be similar to a bipartite one, for instance because eliminating a small number of edges it is transformed into a bipartite graph. This was the idea used by Holme et al. ^[32] to quantify the degree of bipartivity of a network by counting the number of "frustrated" edges, i.e., those whose removal transform the network into bipartite (the name comes from its use in statistical mechanics of spin systems). The "problem" of this approach is that we have to know beforehand what it is the "best" bipartition of the corresponding network, which as mentioned before is an $\mathcal{NP}$-complete problem. Therefore, the use of the previously mentioned heuristics is in general needed to quantify the degree of bipartivity using the number of frustrating edges. Other approaches that do not need an a priori knowledge of the "best" bipartition have been proposed, which use spectral properties of the exponential of the adjacency matrix ^[33,34] or other structural properties of graphs ^[35].

Here, we focus on the use of geometric parameters of graphs derived from the use of the exponential of the adjacency matrix $A$ to detect $k$-partitions in networks. The nondiagonal entries of $\exp\left(A\right)$ are know as the communicability function between the corresponding nodes of the graph ^[36,37,38]. It has been recently proved that it induces an embedding of any graph into an $n$-dimensional Euclidean sphere ^{[39,40,41,42]}. One of the geometrical parameters defined by this embedding, namely the communicability angle, has been succesfully used as a similarity metric for detecting clusters in networks ^[43]. In the current work we will propose an anti-communicability angle, which is based on the generalized communicability function, to detect graph $k$-partitions. We will prove analytically that in a given $k$-partition the anti-communicability angle is larger than $90^{\circ}$ for every pair of nodes in different partitions and smaller than $90^{\circ}$ for those in the same partition. By using the anti-communicability angle as a similarity metric we will apply K-means techniques to detect the "best" $k$-partitions in networks where certain level of edge frustration exists. We show here that the current method identifies $k$-partitions (mainly bipartitions) in many real-world networks representing a variety of systems. In general, those partitions have large bipartivity according to the index of Holme et al. ^[32], which can be considered as a quality criterion for the partitions found.

2.   Preliminaries

Here we consider simple connected graphs $G = \left(V, E\right), \;$also named indistinctly networks, with $n = \left|V\right|$ nodes and $m = \left|E\right|$ edges. Let $A$ be the adjacency matrix of $G$. Then, $A$ is symmetric and has eigenvalues $\lambda_{1} > \lambda_{2}\geq\cdots\geq\lambda_{n}$, with eigenvectors $\vec{\psi}_{1}, \vec{\psi}_{2}, \cdots, \vec{\psi}_{n}$, which are taken here orthonormalized. A graph is bipartite if $V = V_{1}\cup V_{2}$, where $V_{1}$ and $V_{2}$ are mutually disjoint sets. We recall that a bipartite graph does not contain any cycle of odd length.

Let $p\in V$ and $q\in V$ be any two nodes of $G$, and let $\gamma\in\mathbb{R}$ be a parameter. The generalized communicability function ^[36,37,38] between these two nodes is defined as:

where $\left(A^{k}\right)_{pq}$ counts the number of walks of length $k$ between $p$ and $q$, and $e^{\gamma A}$ is the matrix exponential function. We recall that a walk is a sequence of (not necessarily different) consecutive nodes and edges, and its length the number of edges in it. Because the adjacency matrix of simple connected graphs is always diagonalizable we can write the communicability function as

where $\psi_{jp}$ represents the $p$th entry of the $j$th eigenvector of the adjacency matrix corresponding to the eigenvalue $\lambda_{j}$. The parameter $\gamma$ can be understood as a homogeneous weight given to all the edges of the graph. When $\gamma = 1$ we have a simple graph and when $\gamma\neq1$ we have a graph with edge weights $\gamma$ and adjacency matrix $\gamma A$.

3.   Anti-communicability geometry

3.1.   Generalized communicability function

In this subsection we extend the definition of communicability distance ^[39,40] and angle ^[41] for the generalized communicability function.

Lemma 1. Let $\mathcal{G} = \exp\left(\gamma A\right)$ for $\gamma\in\mathbb{R}$. Then, $\mathcal{G}$ is positive definite (p.d).

Proof. The function $\mathcal{G} = \exp\left(\gamma A\right)$ is p.d. iff $eig\left(\mathcal{G}\right) = \exp\left(\gamma\lambda_{j}\right) > 0$, which is obviously the case for any value of $\gamma\in\mathbb{R}$.

Lemma 2. The function,

is a square Euclidean distance between the nodes $p$ and $q$.

Proof. The matrix function $e^{\gamma A}$ can be written as $e^{\gamma A} = Ve^{\gamma\varLambda}V^{-1}$, where $V = \left[\vec{\psi}_{1}\cdots\vec{\psi}_{n}\right]$ and $\varLambda = diag\left(\lambda_{r}\right)$. Let $\vec{\varphi}_{u} = \left[\psi_{1, u}, \psi_{2, u}, \cdots, \psi_{n, u}\right]^{T}$. Then,

Thus, because $e^{\gamma A}$ is p.d. (notice that it is enough that the matrix function is positive semi-definite) we can write

where $\vec{x}_{p} = e^{\gamma\varLambda/2}\vec{\varphi}_{p}$.

Because $\vec{x}_{p}$ is obviously the position vector of the node $p$ in the corresponding Euclidean space (see ^[42]) we have that $\vec{x}_{p}\cdot\vec{x}_{q} = \left(e^{\gamma A}\right)_{pq}$, and $\left\Vert \vec{x}_{p}\right\Vert ^{2} = \left(e^{\gamma A}\right)_{pp}$. Thus, the following result follows.

Lemma 3. The function,

is the Euclidean angle spanned by the position vectors of the nodes $p$ and $q$ of the graph in the Euclidean embedding space for any $\gamma\in\mathbb{R}$.

3.2.   Anti-communicability angles in graphs

In order to understand the motivation of the current approach we will start by considering that $\gamma < 0$, in particular let us fix $\gamma = -1$. This is equivalent to consider that every edge of the graph has a negative weight equal to $-1$. We can think of this weighting as if a "repulsion" force is trying to pull apart every pair of connected nodes (see Figure 1). In the particular case that the graph is bipartite, this repulsive force will separate the nodes according to their disjoint sets. We should notice here that when $\gamma > 0$ the communicability angles identifies the nodes that tend to display similar topological features. In this case the clustering of the nodes form communities of nodes that tend to communicate better among them than with the others outside their communities ^[43].

That is, let us define the communicability angle between any two nodes of the graphs for $\gamma = -1$ as:

Then, we have the main result of this work.

Theorem 4. Let $G = \left(V, E\right)$ be a bipartite graph with disjoint sets $V_{1}$ and $V_{2}$ such that $V = V_{1}\cup V_{2}.$ Let $p$ and $q$ be two nodes of $G$. Then, the angle $\tilde{\theta}_{pq}$ takes the following values:

Proof. Let us write

Then, it is easy to see that the denominator of the definition of $\tilde{\theta}_{pq}$ is positive:

Let us consider that the two nodes $p$ and $q$ are in the same bipartition set. Thus, because there are no walks of odd length starting at a node in $V_{1}$ (resp. $V_{2})$ and ending at a node in $V_{1}$ (resp. $V_{2})$, we have that $\left(\sinh\left(A\right)\right)_{pq} = 0$. Consequently,

Let us now consider that the two nodes $p$ and $q$ are in different bipartition sets. Thus, because there are no walks of even length starting at a node in $V_{1}$ (resp. $V_{2})$ and ending at a node in $V_{2}$ (resp. $V_{1})$, we have that $\left(\cosh\left(A\right)\right)_{pq} = 0$. Consequently,

Example 5. As a matter of example we give the communicability angles between the nodes of the complete bipartite graph $K_{2, 3}$ illustrated in Figure 1: $\tilde{\theta}_{a, e} = 44.9^{\circ}$, $\tilde{\theta}_{b, c} = \tilde{\theta}_{b, d} = \tilde{\theta}_{c, d} = 51.9^{\circ}$, $\tilde{\theta}_{a, b} = \tilde{\theta}_{a, c} = \tilde{\theta}_{a, d} = \tilde{\theta}_{e, b} = \tilde{\theta}_{e, c} = \bar{\theta}_{e, d} = 141.8^{\circ}$.

Remark 6. The anti-communicability angle between two nodes can be calculated directly from the eigenvalues and eigenvectors of the adjacency matrix,

where $\psi_{jp}$ represents the entry corresponding to node $p$ in the $j$th eigenvector of the adjacency matrix associated to the eigenvalue $\lambda_{j}$.

Remark 7. The anti-communicability angles can be obtained in the form of a matrix $\Theta$ in which the $p, q$ entry corresponds to the anticommunicability angle between these two nodes. Let $P\oslash Q$, represents the Hadamard division of matrix $A$ by matrix $B$, $P\odot Q$ the same for the Hadamard product of the two matrices and $P^{\circ y}$ the Hadamard power of the matrix $P$ to the power $y$. Let $\vec{p}\cdot\vec{q}$ be the inner product of the two vectors. Then,

$\vec{v} = \text{diag}\left(e^{-A}\right)$ is a column vector formed by the main diagonal entries of $e^{-A}$ and where the inverse cosine is applied in an entrywise way to the entries of the resulting matrix.

3.3.   Deviations from bipartivity

To motivate this problem let us consider the following.

Example 8. We consider a modification of the bipartite graph illustrated in Figure 1 to which we add the edge (b, c). In this case the graph is, obviously, no longer bipartite. The calculation of the communicability angles are $\tilde{\theta}_{a, e} = 48.6^{\circ}$, $\tilde{\theta}_{b, d} = \tilde{\theta}_{c, d} = 61.6^{\circ}$, $\tilde{\theta}_{a, b} = \tilde{\theta}_{a, c} = \tilde{\theta}_{e, b} = \tilde{\theta}_{e, c} = 125.3^{\circ}$, $\tilde{\theta}_{a, d} = \tilde{\theta}_{e, d} = 141.5^{\circ}$, and the most affected angle is $\tilde{\theta}_{b, c} = 96.5^{\circ}$. That is, the angle between the nodes b and c, has changed from $51.9^{\circ}$ to $96.5^{\circ}$. The nodes a and e are clearly in the same disjoint set of the partition as before because $\tilde{\theta}_{a, e} < 90$. However, for the nodes b, c and d we have that two angles are below $90^{\circ}$ ($\tilde{\theta}_{b, d} = \tilde{\theta}_{c, d} = 61.6^{\circ}$) and one angle is over 90 ($\tilde{\theta}_{b, c} = 96.5^{\circ}$).

From the previous example we can see that in order to decide what is the best place for the three nodes b, c and d we should consider the communicability angles as a similarity measure and apply some pattern recognition technique to group them according to certain criteria. Here we are going to keep thing as simple as possible and we will find the best partition into almost-disjoint clusters of nodes using K-Means ^[44,45], based on $\tilde{\theta}$. K-Means operates by considering the matrix $\hat{\theta}$ as the initial dataset consisting of column vectors which represents the nodes of the graph. That is, the $i$th column of $\hat{\theta}$ represents an $n$-dimensional vector representing node $i$. Then, K-Means generates $K$ non-empty disjoint clusters $C = \left\{ C_{1}, C_{2}, \ldots, C_{K}\right\}$ around the centroids $c = \left\{ c_{1}, c_{2}, \ldots, c_{K}\right\},$ by iteratively minimizing the sum ^[44,45]

Due to the fact that we have to preselect the number of clusters $K$, we need to compare the quality of the partition for the different values of the number of clusters selected. With this goal we use several cluster validity indices (CVIs) for estimating $K$ ^[46,47]. In particular we will consider here: (i) the Calinski-Harabasz index ^[48], (ii) the Silhouette index ^[49], and (iii) the Davies-Bouldin index ^[50]. The reader is referred to ^[47] for details and comparisons of these indices. We have then considered several networks, which are described below, and found the "best" bipartition according to these three criteria. It should be remarked that this search is computationally and that even for the same network and the same quality criterion the results vary from one realization to another. Consequently, it is recommended to carry out several realizations with the same criterion and then selecting the ones that produces the partition with the least number of frustrating edges. We have not found significant differences in the number of frustrating edges, i.e., those belonging to $C$, between the three quality criteria. Consequently, hereafter we will consider the Silhouette method in all our calculations.

3.4.   Multipartitions

Let us start by considering a complete graph $K_{n}$ in which $n$ nodes are all connected to each other. Then, we have the following.

Lemma 9. Let $p$ and $q$ be any two nodes in a complete graph $K_{n}$. Then,

which implies that $\tilde{\theta}_{pq} > 90^{\circ}$ for any pair of nodes in $K_{n}$.

Proof. In $K_{n}$ we have $\lambda_{1} = n-1$, $\lambda_{k\geq2} = -1$, $\vec{\psi}_{1} = n^{-1/2}\vec{1}$. Then,

which means that

from which the result follows.

The previous result indicates that for a complete graph we will obtain a communicability matrix angle, all of its entries are formed by angles larger than $90^{\circ}$. That is, the previous result indicates that the communicability angle correctly identifies a complete graph $K_{n}$ as an $n$-partite one. In a similar way, as can be easily derived from our main result (Theorem 1) the current approach exactly identifies the partitions of any complete $k$-partite graph. The question is whether the computational approach described in the previous section is able to recognize the $k$-partite structure of graphs in which there is some level of edge frustration. We have analyzed this question computationally using various realizations of tri- and tetra-partite graphs with different levels of frustration. In a similar way as for the case of bipartitions, the current approach using K-means with Silhouette identifies correctly the corresponding $k$-partite structures. For instance in Figure 2 we illustrate some complete $k$-partite graphs ($k = 3, 4$) without (Figure 2 (top-left) and (bottom-left)) and with (Figure 2 (top-right) and (bottom-right)) some level of edge frustration as partitioned by the current approach.

4.   Analysis of real-world networks

In this section we consider several real-world networks (see ^[24] and references therein). The first three networks contain evidences, either structural or from the way in which they were build, about bipartivity. For instance, the first network, a protein/protein interaction network, has only one odd/length cycle, i.e., a triangle. The second network is a network of subjective and nouns which is expected to be split into two almost disjoint classes of words. The third one is a network of advisors-advisees, which is also expected to reflect such kind of almost-bipartite structure.

After detecting the "best" partition according to the current method it is then easy to calculate the level of "edge frustration". That is, the relative number of edges that frustrate the bipartitivity of a given graph. For that purpose we will use an index defined by Holme et al. ^[32]:

where $\varphi\left(G\right)$ is the number of frustrating edges and $m$ is the total number of edges in the graph. For these calculations we do not take into account the number of self-loops in the graph.

We should remark here that the frustration index $b$ has a unique value for a nonbipartite graph. This is due to the fact that a nonbipartite graph $G$ is transformed into a bipartite one after the removal of $\varphi\left(G\right)$ edges. However, detecting the exact number $\varphi\left(G\right)$ for a non-bipartite graph is an NP-complete problem. Therefore, if we do not know the exact value of $\varphi\left(G\right)$ what we can do is to use the index $b$ as an indicator of the level of frustration found in the graph by the algorithm used to detect the bipartition. It is not always the case that such number is the exact frustration of the corresponding graph.

4.1.   Protein-protein interaction network (PIN) of A. fulgidus

This is a small network whose main connected component consists of 32 proteins connected through 36 protein-protein interactions. This PIN corresponds to the proteins implicated in the DNA replication in Archaeoglobus fulgidus. The network is almost bipartite except for the presence of a triangle. This network has two self-loops, i.e., edges of the type $\left(v, v\right)$, which represent interactions with a protein with itself.

As can be seen in Figure 3 the current method based on the communicability angle identifies two partitions, one containing 13 nodes and the other having 19. There is only one frustrating interaction, which is represented as a curved edge inside the set of red nodes. That is, in this case $b\approx0.972$, which indicates a high level of bipartitivity. In this particular case it is plausible to identify the two almost-disjoint sets of proteins from a biological point of view. The set of 19 proteins corresponds to those used as preys in the yeast-two hybrid (Y2H) method to identify the protein interactions. The set formed by 13 nodes is then formed by those used as baits. According to the authors of the Y2H experiment bait proteins were generated as fusion of the respective complete open reading frame with the sequence encoding the Gal4 DNA-binding domain in pGBDU. On the other hand, prey proteins were encoded by inserts from the genomics library (Y2H-screen) or correspond to those containing the complete open reading frame encoded by a fusion gene with the activation domain of Gal4 in pGAD424 (matrix mating).

4.2.   Network of nouns and adjectives

The second experiment corresponds to the analysis of a network generated by Newman and representing juxtapositions of words in a corpus of the novel David Copperfield by Charles Dickens. The network was constructed by taken the 60 most commonly occurring nouns in the novel and the 60 most commonly occurring adjectives. The vertices in the network represent words and an edge connects any two words that appear adjacent to one another at any point in the book. Eight of the words never appear adjacent to any of the others and are excluded from the network, leaving a total of 112 nodes. In this network it is expected that nouns are connected mainly to adjectives, such that they form two disjoint sets. However, it is possible for adjectives to occur next to other adjectives or for nouns to occur next to other nouns.

In Figure 4 we illustrate the partition found using the current approach which consists of two classes, one having 51 nodes and the other having 39. The class having 51 nodes corresponds to nouns and the other to adjectives. Thus, according to the classification made by Newman, our method identifies correctly 94.4% of nouns and 67.2% of adjectives. According to Holme et al. index $b\approx0.746$, the network display about 74% of bipartition.

However, a more careful analysis of the false nouns, i.e., adjectives classified as nouns by the current approach, using the Oxford Dictionary detected that 14 out of the 19 false nouns are also used in English as both adjectives and nouns (see Table 1). Thus, in reality the method identifies these words in the class in which they produce least edge frustration of the two in which they can be correctly classified.

4.3.   Advisors/advisees social network in a sawmill

The third example is a social network within a small sawmill. The nodes represent the employees of the sawmill, with two employees linked based on the frequency with which they discussed work matters on a five-point scale ranging: from less than once a week to several times a day. The employees are Spanish-speaking or English- speaking, and the sawmill contains two main sections: the mill and the planer section. Then there is a yard where two employees are working, and some managers and additional officials.

The partition of the network obtained by using the current approach is illustrated in Figure 5. This partition consists of one group of 17 workers and another of 19 ones. In total there are 13 frustrating connections, 6 among the workers in the group of 17 workers and 7 in the other group, which gives $b\approx0.790$. The analysis of these groups reveals that they are formed by a mix of employees. For instance, the group of 17 workers is formed by 8 workers from planing section (2 English speaking and 6 Hispanic), 7 workers from the mill (4 English speaking and 3 Hispanic), the forester, one worker from the yard and the kiln operator. The other group is formed by 6 workers in planing (1 English speaking and 5 Hispanic), 9 from the mill (2 English and 7 Hispanic), one worker from the yard, the mill manager, and the owner. This clearly shows that the partition of this network reflects more the structure of advisors and advisees, than a ethnic or location-related partition.

We now consider some other networks for which we do not have evidences of any bipartite structure. The first group of networks represent undirected versions of food webs where the nodes represent the species and the edges the trophic interactions. The second group is formed by two social networks and two biological networks. We discuss each of them in the next subsections.

4.4.   Foodwebs

The first of the food webs considered here is "Grassland", which is formed by all vascular plants and all insects and trophic interactions found inside stems of plants collected from 24 sites distributed within England and Wales. The best bipartition found by the current approach is illustrated in 6 (top-left), where it can be seen that there are two well defined partitions, the red ones having 48 nodes with 7 frustrating edges and the blue one having 28 nodes with 14 frustrating edges, which give a bipartivity value of $b\approx0.814$. It is easy to realize that these partitions mainly correspond to plants and insects, with frustrating edges mainly corresponding to parasitoids, hyper-parasitoids and hyper-hyper-parasitoids.

The second food web is the one of "BridgeBrook", which represents pelagic species from the largest of a set of 50 New York Adirondack lake food webs. The best partition found in the current work corresponds to a set of 28 nodes without frustration and another set of 47 nodes with 47 frustrations ($b\approx0.913$). The food web is formed by phytoplankton, herbivorous (rotiferan and crustacean) zooplankton, carnivorous zooplankton and fish. Thus, a plausible partition is in a layer formed by herbivorous without any frustrating edges, and the other by phytoplankton and carnivorous, with frustrating edges between carnivorous as well as between carnivorous and phytoplankton (see Figure 6).

The third food web represents "Canton Creek", which accounts for primarily invertebrates and algae in a tributary, surrounded by pasture, of the Taieri River in the South Island of New Zealand. The best partition is formed by a set of 61 nodes with 14 frustrations and the other formed by 47 nodes with 5 frustrations, which indicates a bipartivity of $b\approx0.973$. The fourth network represents "Stony", which is formed by primarily by invertebrates and algae in a tributary, surrounded by pasture, of the Taieri River in the South Island of New Zealand in native tussock habitat. The best partition is formed by a set of 40 nodes with 4 frustrations and the other formed by 72 nodes with 19 frustrations, which indicates a bipartivity of $b\approx0.972$.

Among the food webs analyzed we also found two for which the current method produces $k$-partite structures as the best partition. They correspond to the food web of Scotch Broom, which consists of trophic interactions between the herbivores, parasitoids, predators and pathogens associated with broom, Cytisus scoparius, collected in Silwood Park, Berkshire, England, UK, and the one of Skipwith, which contains interactions between invertebrates in an English pond. In both cases we have made several realizations of the K-means approach with the Silhouette quality criterion. As can be seen in Figures 7 (top-left) and (bottom-left) the Silhouette method identifies $k = 3$ and $k = 5$ as the best partitions for these two food webs, respectively. The corresponding $k$-partitions are illustrated in Figures 7 (top-right) and (bottom-right). The bipartivity of these two partitions are, respectively: $b\approx0.858$ and $b\approx0.836$.

4.5.   Other networks

In this subsection we study two social networks, namely "social3", which represents a social network among college students in a course about leadership. The students choose which three members they wanted to have in a committee, and "Galesburg", which accounts for friendship ties among 31 physicians. The other two networks are "Trans_sea_urchin", which is the developmental transcription network for sea urchin endomesoderm development and "KSHV", the protein-protein interaction networks in Kaposi sarcoma herpes virus (KSHV).

The first network, which is partitioned in Figure 8 (top-left) produces a bipartivity index of $b\approx0.725$ where in one of the partitions there are people who want the members of the other partition in a committee, but not those in their same partition. A similar explanation can emerge for the friendship network among physicians, which produces $b\approx0.762$. In the PPI of KSHV the partition provides a bipartivity of $b\approx0.868$ and could reflect the division of proteins into locks and keys as in the case of the PPI of A. fulgidus previously analyzed. The transcription network of sea urchins produces a partition having bipartivity $b\approx0.712,$possibly reflecting the nature of the interactions between operons–one or more genes transcribed on the same mRNA–that encode transcription factor to operons that are directly regulated.

5.   Very sparse networks

To warming up and understand the main issue here we will consider a simple example. Let $P_{n}$ be the connected graph with $n-2$ nodes of degree 2 and two nodes of degree one. This graph is obviously bipartite and if we label the nodes from 1 to n, we can split the graph into two disjoint sets, one with odd labels and the other with even ones. Then, according to what we have proven previously, if we pick one node $i$ of the path $P_{n}$ the angles between this node and every other node in the graph will alternate between values larger than $90^{\circ}$ and values smaller than $90^{\circ}$. An example is provided in Figure 9 for the node $i = 1$. Every broken line represents the angle between the node labeled as one and the corresponding node in the path. Then, according to our current analysis every node with an angle with node 1 smaller than 90 degrees should be in the same partition as this node, i.e., all nodes with odd-labels should be in the same partition as node $i = 1$. However, here we are using a method to detect these partitions which considers the angles matrix as a similarity matrix. Thus, such method is not able to distinguish between angles too close to $90^{\circ}$, such as the angles $\theta_{1, 7}$, $\theta_{1, 8}$, $\theta_{1, 9}$, and $\theta_{1, 10}$. In other words, using the anti-communicability angles as a similarity matrix, it is difficult to say which of these nodes, i.e., 7, 8, 9 and 10, are in the same partition of the node 1 and which are not.

This situation is not exclusive of the path graph, but of any network with low edge density and possibly large diameter. Thus, a simple way to "help" the method to recognize the similarities and dissimilarities between pairs of nodes is simply transforming the anti-communicability angle matrix into a binary matrix. That is, we can transform the anti-communicability angles matrix such that every angle strictly larger than $90^{\circ}$ becomes one, and every angle smaller or equal than 90 becomes zero. In this case K-means clearly identifies both partitions of the path.

In order to illustrate this problem and its solution in real-world networks we study here two sexual contact networks. In the first of the two networks only heterosexual contacts between individuals are considered. Thus, the network is bipartite, with male and female as the members of each partition. However, the current approach using directly the anti-communicability matrix as the similarity matrix produces partitions which do not correspond to the expected bipartite graph. However, the introduction of the correction based on the dichotomization of the network immediately recovers the bipartite structure of this network as illustrated in Figure 10 (left) where obviously $b = 1$. A similar situation occurs for the case in which both hetero and homosexual relations are considered in the same network. The method without preprocessing produces a partition with many frustrating edges, but the application of the dichotomization makes a bipartition with 2 frustrations in one set and 13 in the other as illustrated in Figure 10 (right) for a high value of the bipartivity index $b\approx0.944$.

6.   Conclusions

We have defined and used here the anti-communicability angles between the nodes of a graph to identify bi- and multi-partite structures in networks. We have restricted ourselves to the use of $\exp\left(-A\right)$ for the sake of simplicity. However, the anti-communicability angle can be defined in a general framework for $\exp\left(-\left|\gamma\right|A\right)$, such that we can modulate the value of the parameter $\gamma$ that produces the "best" $k$-partition for a given network. This is, of course, a more computational task and we have restricted ourselves here to the general mathematical framework of the method. Therefore, it is possible that the results presented here can be improved by using such computationally intensive method. However, we should remark here that for the real-world networks that we have studied the partitions found by the current approach display large bipartivity indices (according to Holme et al. ^[32] index). For instance, among the 15 real-world networks studied here the average values of this index is $\bar{b}\approx0.859\pm0.096$, with a minimum value of $b\approx0.712$, which was obtained for the partition of the transcription network of sea urchins. That is, the current approach produces $k$-partitions with a very low level of edge frustration in real-world networks of very different topologies and sizes.

We should emphasize that the current approach can be applied to bigger networks. Indeed, we have applied it to networks with the order of $10^{4}$. However, such networks have displayed low level of bipartivity and showed a large number of frustrating edges, such that they were not appropriate as illustrative examples. This is not strange because many real-world networks have a large number of triangles due to the transitivity of many relations. Consequently, their level of edge frustration is very high. We should remark that the computational complexity for the calculation of the matrix exponential has an upper bound of $O\left(n^{3}\right)$ and a lower bound is $O\left(n^{2}\right)$. We have previously analyzed this complexity in our paper ^[38]. However, it is known that finding the optimal solution to the k-means clustering problem in a general Euclidean space like the one used here is an $\mathcal{NP}$-hard problem ^[51]. This implies that for extremely large networks it should be better to explore the use of other algorithms showing better computational efficiency than k-means. All in all, we consider that the study of the anti-communicability angles as a proxy for the detection of multipartite structure in graphs and networks deserves attention from both a mathematical and a computational point of view.

Acknowledgments

This work was partially by Gobierno de Aragón/Fondo Social Europeo (Grant No. E36-17R), Ministerio de Economia, Industria y Competitividad (MINECO) and Fondo Europeo de Desarrollo Regional (FEDER) (Grant No. FIS2017-87519-P).

Conflict of interest

The authors declare no conflict of interest.