Efficient algorithm based on non-backtracking matrix for community detection in signed networks

Signed networks consist of interacting individuals with both positive and negative relationships. Each individual in the network corresponds to a node in the graph. The connection between a pair of individuals is regarded as the edge between the corresponding node pair. Positive and negative relationships are represented as positive and negative edges in the network. For simplicity, the weights of positive and negative edges are defined as $1$ and $-1$, respectively.

First, we describe the signed stochastic block model [21, 22, 23]. Given an undirected network with $n$ nodes (where $n$ is assumed to be an even number), we divide the node set into two groups, $\mathcal{A}$ and $\mathcal{B}$, where each group has $n/2$ nodes. Nodes in group $\mathcal{A}$ are indexed from $1$ to $n/2$ and those in group $\mathcal{B}$ are indexed from $n/2+1$ to $n$.

A signed network can be represented by an adjacency matrix $A$ in which the entries take on values of $\left\{1,-1,0\right\}$, where 0 signifies the absence of an edge, and $1$ and $-1$ signify a positive relationship and negative relationship, respectively. The adjacency matrix is symmetric because the network is undirected. The following are some of the parameters for any pair of nodes $(i,j)$. The probability of formation of an edge between any given in-group (out-group) node pair is $d_{in}$ ($d_{out}$). The expected edge density of the entire network is $d=d_{in}+d_{out}$. Given the presence of an edge between in-group members, $p_{in}^{+}$ denotes the conditional probability that it will be positive. Analogously, $p_{out}^{+}$, $p_{in}^{-}$, and $p_{out}^{-}$ denote the conditional probabilities of a positive edge between out-group members, a negative edge between in-group members, and a negative edge between out-group members, respectively. Thus, the conditional probabilities satisfy $p_{in}^{+}+p_{in}^{-}=1$ and $p_{out}^{+}+p_{out}^{-}=1$.

Generally speaking, when we say that a network has a community structure, at least one of the following conditions holds:

1. 1.

   The number of positive intra-community links is greater than the number of negative links, i.e., $p_{in}^{+}>p_{out}^{+}$ and $p_{in}^{-}<p_{out}^{-}$.

2. 2.

   The density of intra-community links is higher than that of inter-community relationships, i.e., $d_{in}>d_{out}$.

Under the first condition, the community structure is termed relationship-sensitive and is denoted as r-community. Under the second condition, the community structure is termed link-density-sensitive and denoted as d-community.

One of the main contributions of this work is to define non-backtracking matrices for signed networks, which have great potential for community detection. Though a non-backtracking matrix of unsigned networks is well defined–which is presented herein for completeness–a proper definition of a non-backtracking matrix is far from trivial, as demonstrated in following sections.

Prior to providing a formal definition of a non-backtracking matrix of signed networks, we first present the definition of a non-backtracking matrix of unsigned or general networks. The non-backtracking matrix $\widetilde{H}$, often termed the $Hashimoto$ matrix in mathematics, is defined as follows:

where $\widetilde{A}$ is the adjacency matrix of the unsigned network and $e=(u,v)$ and $f=(w,x)$ are two directed edges. It should be noted that if the network is undirected, we treat each undirected edge as two directed edges. Hence, the matrix $\widetilde{H}$ has the dimensions $2m\times 2m$, where $m$ is the number of edges in the network.

The non-backtracking matrix $\widetilde{H}_{2m\times 2m}$ can, in fact, be expressed as

Similar to the matrix $\widetilde{H}$ defined in Eq.(1), the SNBT matrix of signed networks, denoted as $H$, can be directly derived as follows:

This matrix can be expressed as

where $\sigma\left(u\rightarrow v\right)$ denotes the sign of a directed edge $u\rightarrow v$, which takes a value of either $1$ or $-1$. The significance of the defined non-backtracking matrix $H$ is that true information will be transferred between two edge pairs with identical signs and false information will be transferred between two edge pairs with different signs, and this behavior accurately follows the structural balance theory (a triple with either one or three negative signs is unstable).

On the basis of the information flowing along the directed edges in the network, $H$ can also be deduced via linearized belief propagation (LBP). This is explained in greater detail in Appendix A.

In other words, we define the non-backtracking matrix from two different perspectives, theoretically deduce its role in community detection, and confirm the feasibility of its application to a basic stochastic block model via the linearization of the updating equation of the BP algorithm around a fixed point.

To demonstrate the applicability of the SBNT matrix to community detection, we derive the community detection threshold and a detection vector for an arbitrary signed network. By generalization on the basis of observations in unsigned networks [21, 24, 25, 26], we define $g^{out}$ and $g^{in}$ as $n$-dimensional vectors:

where $\mathcal{N}(u)$ denotes the neighbor set of node $u$ and vector $g$ is a given vector with 2m dimensions. Unlike in the case of unsigned network, we not only sum over incoming and outgoing edges but also consider the sign of the edges.

By applying $H$ to $g$, we get

where $k_{u}$ denotes the degree of node $u$ (which is independent of the sign of the edges). Rewriting the above two equations in matrix form gives

where $I$ is the identity matrix, $D$ is the diagonal matrix of vertex degrees, and $\widetilde{A}$ is the adjacency matrix of the underlying unsigned structure corresponding to the signed network.

Suppose that $Hg=\mu g$; then, we have

If $g^{in}$ and $g^{out}$ are nonzero, then $\begin{pmatrix}g^{in}\\ g^{out}\end{pmatrix}$ is an eigenvector of $H^{\prime}$ with the same eigenvalue $\mu$. Hence,

Therefore, $\mu$ is a root of the quadratic eigenvalue equation

The complexity of calculating the eigenvalues of $H^{\prime}$ will be much lower than that of the original non-backtracking matrix $H$. Eq.(6) is well known in the theory of graph zeta functions [26]. It accounts for $2n$ of the eigenvalues of $H$, and the remaining $2m-2n$ eigenvalues are $\pm 1$.

In fact, we directly and simply prove that the spectrum of $H$ is the same as that of $\widetilde{H}$, where the network for the latter matrix is considered as an unsigned network. $H$ can also be derived via multiplication of all the elements of some rows and their corresponding columns in $\widetilde{H}$ by $-1$, that is,

where $\left|\epsilon_{-}\right|$ is the number of negative edges in the network.

Therefore, the bulk of the spectrum $B$ is also confined to the radius disk $\sqrt{c}$ in signed networks. It should be noted that $c=d\cdot n$ is the average degree of the network. We can similarly and correspondingly define $c_{in}$ and $c_{out}$.

Further, we obtain the first and second eigenvalues of $H$ as

In the unsigned network, the second eigenvector of the non-backtracking matrix is a community-correlated eigenvector. If the second eigenvalue of $\widetilde{H}$ is separated from the bulk of the spectrum, then the eigenvector corresponding to the second eigenvalue can be used in the community detection (via labeling of the vertices according to the sign of the sum of all incoming edges at each vertex) [27]. Similar conclusions for signed networks are verified subsequently in the paper.

Next, we first attempt to construct a vector $g$ that is correlated to the communities and is an approximate eigenvector with eigenvalue $\mu_{c}$. We assume that $c=O(1)$, and therefore the graph is sparse and locally tree-like. For any positive integer $r$ and any directed edge $(u,v)$, we define the following:

where $\sigma_{x}=\pm 1$ denotes the community of $x$, $\sigma_{u\rightarrow v}=\pm 1$ denotes the sign of edge $(u,v)$, and $d(u\rightarrow v,w\rightarrow x)$ denotes the number of steps required to go from $u\rightarrow v$ to $w\rightarrow x$ in the graph of directed edges, as shown in Fig. 2.

Application of $H$ to $g^{(r)}$ gives

which can be simplified as

We can write $g_{u\rightarrow v}^{(r)}-g_{u\rightarrow v}^{(r+1)}$ as

Now, there are (an expected) $c^{r}$ terms in this sum, each of which is conditioned on $\sigma_{x}$ values and has an expected value of zero and a constant variance. Hence,

By summing over all the edges, we obtain

Therefore, when the community-correlated eigenvalue (the second eigenvalue) satisfies

it can be naturally considered that when this eigenvalue is separated from the bulk spectrum, the error is small and it approaches zero for large $r$. Further, from the conclusion for unsigned networks [28, 29], it can be inferred that, under the condition that the threshold is met and $n\rightarrow\infty$, for every $u\rightarrow v$,

Thus, we can draw the following conclusion:

Therefore, $g^{(r)}$ is indeed an approximate eigenvector of $H$ having an eigenvalue of $\mu_{c}$, which may be used to detect the community structure of signed networks. Further, Eq.(9) expresses the detection threshold finally derived in this study, which shows agreement with the threshold for unsigned networks.

The above-presented analysis is for stochastic block models with two communities ($q=2$). In fact, according to the above-described derivation process, the SNBT matrix can also be well applied to a model with more than two communities ($q>2$). Its detectable threshold should be similar to the conclusion for the unsigned network; that is, the community-correlated eigenvalue satisfies Eq.(9), i.e., $\mu_{c}>\sqrt{c}$.

In this case, the second eigenvalue is given as

We can take the first $k$ eigenvectors and use the k-means algorithm to determine the group labels of the nodes. However, the threshold value for detection of the network structure using the adjacency matrix when the number of communities is greater than two is yet unknown; therefore, we refrain from performing a more detailed comparative evaluation here.

From the above analysis, we know that the SNBT matrix is density sensitive rather than sign sensitive. Even in the case where the negative edges of inter-community connections and the positive edges of intra-community connections constitute the majority of the edges in the connections, the final results are not ideal as long as the density of connected edges within and between groups exceeds the above-derived threshold value. This insensitivity of the SNBT matrix to edge signs is essentially contrary to our original goal of exploring the community structure of signed networks

In fact, from the below-described threshold of the adjacency matrix, we can see that this matrix is only sign-sensitive and that is, too, does not meet our requirements for community detection. The ideal matrix should have good performance in terms of both aspects; that is, it should be both sign-sensitive and density-sensitive.

We considered both the structural balance theory and the BP theory in the construction of the non-backtracking matrix. Why does this sign insensitivity occur? We find from the discussion in Sec.IIIA that the approximation of the second eigenvector is actually related only to the $k$-order neighbors of node $x$, which is simply equal to the total number of communities the node belongs to and whether or not the path between two nodes is balanced, i.e., whether the internal relationship is friendly or hostile, is not considered.

Hence, we improve the matrix by making the following assumption. We assume that a large number of balanced or stable paths of a given length $k$ between two vertices $u$ and $v$ is expected if both the vertices belong to the same community. Then, the improved matrix, denoted by $H^{b}$, is defined as follows:

This matrix can alternatively be expressed as

Therefore, according to the BP algorithm, during the propagation process, only true information is transmitted to edges with same signs, and false information is transmitted to edges with different signs. For simplicity, we term this matrix the BNBT matrix. In fact, $H^{b}$ is an approximation of $H$, and the detection threshold for community detection is still unclear. However, the below-described experiments demonstrate that this improved matrix is ideal for community detection.

In this section, we provide a detailed description of the community detection algorithm based on the BNBT matrix. We calculate the first $q-1$ eigenvectors of the adjacency matrix for performing clustering using the $k$-means algorithm. Because the detection accuracy of BNBT matrix is not validated theoretically and the community-related eigenvectors of the BNBT matrix are also unclear, we perform clustering using all eigenvectors corresponding to the real eigenvalues. When applying the SNBT-matrix-based algorithm, we calculate the first $\min\{q,r\}$, where $r$ is the number of real eigenvalues.

[htb] Framework for community detection in signed networks. {algorithmic}[1] \REQUIRE  
Adjacency matrix of network $A$;
Number of communities $q$;
\ENSURE  
\STATEThe BNBT matrix $H^{b}$ is constructed according to Eq.(11); \STATEThe eigenvectors $[\xi_{2},\xi_{3},\dots,\xi_{r}]$ corresponding to the real eigenvalues, where $r$ is the number of real eigenvalues, are calculated; here, each $(r-1)$th-row vector represents a directed link; \STATEFor each node $u$, weighted summation of all the vectors of its out-edges $(u,v)$, $v\in\mathcal{N}(u)$ is performed to obtain its representative vector; \STATEThen, clustering is performed using the $k$-means algorithm to obtain the group label $\widetilde{g}$ of the nodes; \RETURN$\widetilde{g}$.

In the following section, we compare the community detection performances of the three matrices.

In unsigned networks, most of the eigenvalues of the adjacency matrix are within a threshold. The number of eigenvalues beyond the threshold equals the number of communities. The second eigenvector indicates the community structure[21].

Similar results have been reported in [22], that is, the bulk of the spectrum of the adjacency matrix is also within a threshold for signed networks. Unlike in the case of the unsigned network, in the signed network, the leading eigenvector represents the community structure, and the number of eigenvalues beyond the threshold is no longer equal to the number of communities (it should be equal to the number of communities minus 1). Moreover, the authors of [22] were the first to consider the detectability transition in signed networks. They concluded that when there are only two communities, as long as the following conditions (Eq.66 in [22]) are met, the sign of the principal eigenvector can be used to detect communities using perturbation analysis and random matrix theory.

Considering the average degree $c$ of the signed network, we use the SNBT matrix as long as the following inequality is satisfied:

In some cases, we can obtain better results by applying the SNBT matrix than by applying the adjacency matrix. Here, we provide a simple but general example for comparing the two methods (see Fig. 3). In all the comparisons, we assume $p_{in}^{+}=p_{out}^{-}$ for convenience. We only consider the case of $p_{in}^{+}>0.5$ here, because when $p_{in}^{+}<0.5$, the community structure can be represented by $u_{N}$ (the last eigenvector of the adjacency matrix). However, given the dynamic evolution process of the network, only the driving role of the leading eigenvector of the initial network in the evolution of structural balance yields a dynamic manifestation of the detectability transition [22].

In fact, Fig. 3 is an abstract representation of the community related parameters in a real network. Region 4 represents the situation wherein $d_{in}<d_{out}$, $p_{in}^{+}\approx p_{in}^{-}$ and $p_{out}^{+}\approx p_{out}^{-}$. In other words, the random blocks generated by the parameters in region 4 are not the two communities mentioned above. For the case that the parameters lie in region 2 (or region 3), we actually anticipate that the algorithm is not sign-sensitive (or density-sensitive), and in such a scenario, the BNBT matrix is effective.

It should be noted that because the theoretical detection threshold of the BNBT matrix is still unknown, we refrain from discussing it any further.

In the following, we provide examples to demonstrate the superior performance of the improved algorithm. The comparison results are shown in Fig. 4. The $x$-axis and $y$-axis represents the $p_{in}^{+}$ and $d_{in}$, respectively. Both the $z$-axis and the color represent the overlap. The experiments are performed on signed networks with a size of $10^{4}$ and an average degree of $10$. We set $p_{in}^{+}=p_{out}^{-}$ for convenience, which varies from $0.5$ to $1$ with an interval of $0.05$. It is worth noting that the $d_{in}$ values in the figure are normalized, i.e., $d_{in}+d_{out}=1$, which also varies from $0.5$ to $1$ with an interval of $0.05$.

We can see that the performance of the SNBT matrix is sensitive only to the link density of inter- and intra- community connections, whereas the adjacency-matrix-based algorithm is more sensitive to the link signs. The BNBT-matrix-based algorithm has the advantages of both these matrices, and its performance depends on both the link density and the link signs. Moreover, the area of the undetectable field (in which the overlap is about $0.5$) is smallest, which indicates that this matrix has the best performance.

Fig. 5 shows four concrete examples with $d_{in}\in\{0.5,0.70,0.75,0.80\}$ and varying $p^{+}_{in}$ (in the range of [$0.5$, $1$]). In fact, each line in this figure is a slice of the data in shown Fig. 4, which is obtained by considering the corresponding $d_{in}$ values. The black, red, and blue lines represent the results obtained using the adjacency matrix, the SNBT matrix, and the BNBT matrix, respectively. For each case (i.e., for each matrix), we perform 10 experiments and calculated the average value for joining the data points to form the black, blue, and red dashed lines. From all the graphs except for the first one, which is the case of $d_{in}=0.5$, we can make the following observations. The overlap is close to 0.5 (which means that the nodes are labelled almost randomly) when the detection threshold of the adjacency matrix is not met, however, the algorithms based on the two non-backtracking matrices show good performances. As discussed above, the overlap does not change with an increase in $p_{in}^{+}$. As $p_{in}^{+}$ increases, the adjacency matrix-based algorithm outperforms the SNBT-matrix-based algorithm. However, the BNBT-matrix-based algorithm outperforms the adjacency-matrix-based approach at all $p_{in}^{+}$ values. This entire analysis can lead to a satisfactory conclusion regarding the superiority of the BNBT-matrix-based algorithm. The first graph is the only exception; in this case, the density is of no use for dividing the community structure($d_{in}=d_{out}=0.5$), and therefore, the SNBT-matrix-based algorithm is invalid and the performance of the BNBT-matrix-based algorithm is poorer than that of the sign-sensitive adjacency-matrix-based algorithm.

As shown in Fig. 6, we further evaluate the performances of the three approaches from another perspective; that is, we provide three concrete examples with $p_{in}^{+}\in\{0.50,0.60,0.70\}$ and varying $d_{out}$ (in the range of $[0.5,1]$). These data lines are slices obtained from the data in Fig. 4 from a different angle. The performance of adjacency-matrix-based approach is not completely independent of $d_{out}$. When $p_{in}^{+}=0.7$, the overlap increases at a small $d_{out}$. However, after the threshold is met, the performance of this approach does not improve with decreasing $d_{out}$. It is further proved that the SNBT matrix $H$ is sign-insensitive. As was the case in the above-described analysis, density sensitivity is the only factor we need to consider when $p_{in}^{+}=0.5$, and therefore, $H$ is superior; however, at other $p_{in}^{+}$ values, $H^{b}$ is superior.

In addition, we know that detection of community structure may be difficult when the graph is sparse. For example, in an unsigned network, when $c$ is constant and $n$ is large, the network is decomposed for several reasons. Most importantly, the leading eigenvalues of $A$ are represented by maximum-degree vertices, and the corresponding eigenvectors are localized around these vertices [21, 30]. The non-backtracking matrix has better performance in the case of a sparse graph. We expect it to have superior performance even in the case of a signed network.

If the right side of the first inequality in Eq.(13) is regarded as a function of $d_{in}$, we obtain a lower bound according to the monotonicity of the function as follows:

Therefore, we theoretically prove that when the community detection using the non-backtracking matrix is feasible, the smaller the $c$ value, the better are the results obtained using the non-backtracking matrices than those obtained the adjacency matrix. It should be noted that what we refer to as better performance in the case of a sparse graph is relative. In fact, with an increase in the sparsity of the network, the detection accuracy will indeed decrease correspondingly. The observation is also confirmed by numerical simulations performed on stochastic block models with $n=10^{4}$, $p^{+}_{in}=0.7$, $d_{in}=0.75$, and varying average degree $c$ (in the range of $[10,60]$ with an interval of $5$). As shown in Fig. 7, the performances of the two non-backtracking matrix-based algorithms under varying $c$ are more stable and robust than that of the adjacency-matrix-based algorithm.

We are also interested in the performance of the newly proposed $H^{b}$ in the above comparative analysis; however, these analyses are based only on numerical simulations, and the underlying theory remains to be studied. Nevertheless, we can draw a definitive conclusion that $H^{b}$ is sensitive to both the edge sign and the connection density. In most cases, it has better performance than the other two matrices, $A$ and $H$. These two matrices have their own limitations. Although they may be the best choice in some very special scenarios, generally speaking, the BNBT-matrix-based algorithm is the most reliable and effective approach.

Finally, we select three real-world networks with ground-truth communities to compare the community detection performances of the three matrices. The basic features of the three networks are listed in Table I. However, since these networks are unsigned, we use the following method to assign a sign (positive or negative) to each link. First, we classify all the links into two categories: inter-community links and intra-community links. Then, we assign to each inter-community link a positive sign with a probability of $p^{+}_{out}$ and to each intra-community link a probability of $p_{in}^{+}$. We set $p^{+}_{out}+p^{+}_{in}=1$, which means that the larger the $p^{+}_{in}$ value, the more significant is the community structure of the network.

In Fig. 8, we have illustrated the community detection accuracies of the three matrices under variation of $p^{+}_{in}$ from $0.5$ to $1$ with an interval of $0.05$. As can be seen from this figure, the performance of the adjacency-matrix-based algorithm increases with increasing $p_{in}^{+}$. This result reveals that this algorithm is sign-sensitive, which is in agreement with the earlier discussion. Similarly, the accuracy of the SNBT-matrix-based algorithm remains almost unchanged, because it is insensitive to $p_{in}^{+}$. The BNBT-matrix-based algorithm shows the best performance and its accuracy also increases with increasing $p^{+}_{in}$. In addition, even though the number of communities in the football network is $12$, the BNBT- and SNBT-matrix-based methods still perform well. This result implies that these matrices are applicable for community detection in a signed network when the number of communities is greater than two, which further confirms our observations.