Proper network randomization is key to assessing social balance

To investigate how the topology and signed degree affect the graphlet statistics, we consider four null models for signed networks, see Fig. 2. In addition to the commonly used rewire and sign shuffle null models and our STP null model, we also consider the ‘signed rewire’ null model ²². The signed rewire null model preserves the signed degree of each node by rewiring the positive and negative subgraphs separately. As a result, the topology is not preserved and there can be edges in the signed rewire null model that are both negative and positive (see Methods). In Fig. 2, we illustrate the studied null models on a toy network satisfying SB. This toy network contains two groups of nodes (indicated by different node colors), with positive edges among group members and negative edges between the groups ²³. Note that some nodes are more friendly (like node 0) or more aggressive (like node 1), i.e., have a higher fraction of positive or negative edges than others.

To test social balance in real networks, we first consider signed triangles as illustrated in Fig. 3A for the Slashdot network. Each triangle graphlet (or equivalently motif) is counted and compared to the expected number of such triangles in four different null models. The fold change is calculated as

$$\mathrm{fold~{}change}=n_{obs}/<n_{rand}>\;,$$

(1)

indicating the relative graphlet frequency ($n_{obs}$) in the original network compared to the frequency in each randomized version ($<n_{rand}>$) in Fig. 3. As a standard measure of statistical significance, we calculate the $z$-score as

$$z=\frac{n_{obs}-<n_{rand}>}{\sigma_{rand}}\;,$$

(2)

where $\sigma_{rand}$ denotes the standard deviation of $n_{rand}$. In the Slashdot network, both the rewire and sign shuffle null models would claim that only $++-$ triangles are underrepresented. This conclusion aligns with the notion of weak structural balance (WB) ^{24; 1; 25}, which alleviates the structural balance so that triangles with exactly one negative edge should be underrepresented. In other words, WB relaxes the assumption that “the enemy of my enemy is my friend”. On the contrary, the signed rewire model would conclude that only $---$ triangles are underrepresented. At the same time, the STP null model identifies that both $---$ and $+--$ triangles are heavily underrepresented, in line with SB.

The same conclusion is observed consistently in the other studied networks as well, when both the signed degrees and the topology is conserved, meaning that signed social networks are strongly balanced at the triangle level according to STP randomization (Fig. 4). No consistent conclusions can be drawn from the rewire and signed rewire null models, most likely due to the fact that the topology is disrupted in these cases. The sign shuffle null model appears to be consistent with WB in all real networks. However, as a clear shortcoming, the sign shuffle and rewire null models fail to detect SB in our model network explicitly built as an SB reference ²⁶ (see Methods). To sum, the known null models lead to conflicting and inadequate conclusions at the triangle level. This incoherence is further amplified when analyzing four-node graphlets, as discussed next.

We start the analyses of four-node graphlets by investigating six cases of square graphlets (Fig. 3B). In the Slashdot network, STP randomization again indicates consistency with SB, while the conclusions of other null models would differ qualitatively. However, understanding SB at the square level requires further efforts. Squares are traditionally less investigated than triangles for multiple reasons. In addition to the increased computational complexity, it appears less realistic to assume that individuals know their social networks at the square level ²³. Furthermore, comparing the observed frequencies of signed squares to the current null models often leads to inconsistent conclusions (Fig. 4). Indeed, all square graphlets can be either significantly over- or underrepresented depending on the choice of network data and the null model. Existing null models again fail to detect SB at the square level even in the SB reference network. In contrast, when compared to the STP null model, all unbalanced squares are consistently underrepresented, while most balanced squares, with the exception of the $----{}$ graphlet, are overrepresented. While the $----{}$ graphlet appears to be underrepresented, it is just barely so at these network sizes, as even the strongest signal in Bitcoin-Alpha is just $z\sim 2$. Overall, the square graphlet results with STP randomization indicate that social networks are compatible with SB, with the potential exception of the $----{}$ graphlet.

Next, we show that the consistent results obtained by using the STP null model enable the formulation of hypotheses for potential wiring mechanisms. Previous studies attempted to explain square graphlet statistics by a node copying mechanism ²⁷. We first generalize the node copying mechanism to signed networks, where a new node can replicate both the connections of existing nodes in the network and the corresponding edge signs. This mechanism contributes to the formation of balanced squares, as illustrated in Fig. 5A. However, our results in Fig. 4 show that the square $+-+-{}$ graphlet is also overrepresented in all studied networks, suggesting that this simple node copying mechanism is not sufficient to explain the full extent of our observations. Moreover, signed triangle graphlets are not necessarily explained by a node copying mechanism, expected to depend also on the initial conditions.

Thus, as a potential solution, we propose an edge copying mechanism as shown in Fig. 5B. As a basic step, a node can copy one of its friend’s connections. In other words, nodes connected by positive edges are assumed to copy each other’s attitude towards other nodes. Conversely, negatively linked nodes replicate the edges of their foes while reversing the sign. The process of edge copying initially results in the formation of balanced triangles and eventually leads to larger balanced graphlets, such as ‘squareZ’ graphlets, which refer to squares with an additional edge. Eventually, this process leads to the formation of fully connected four-node subgraphs, referred to as ‘squareX’ graphlets/motifs, when other nodes also copy edges in the same subnetwork.

The proposed edge copying mechanism is compatible with the squareZ graphlet results shown in Fig. 4. Comparing the observed squareZ statistics to the STP null model, all datasets consistently agree with the SB expectation, while there is no consistent conclusion from other null models (Fig. 4). In addition to squareZ, we have also considered the fully connected four-node squareX graphlet/motifs as shown in Fig. S1. When compared to the STP null model, balanced (unbalanced) squareXs are again overrepresented (underrepresented), a pattern that is not observed with other null models. We also implemented the edge copying mechanism to generate an edge copying reference network, EC (see Methods). Note that with the chosen initial conditions, EC also satisfies SB. Yet, in general, the edge copying mechanism does not necessarily lead to the formation of balanced square graphlets. This finding is actually in line with our observations, as the statistics of $----{}$ appears to vary across datasets. Yet, our analysis indicates that $----{}$ square motifs with one or two additional positive edges are overrepresented, as suggested by the edge copying mechanism.

The proposed edge copying mechanism on its own leaves the question of balanced squares open. To potentially elucidate the presence of mostly balanced squares in the studied datasets, we also explore the implications of edge copying between disconnected nodes. In this scenario, a node may connect to the neighbors of another (unrelated) node with or without reversing the edge signs. Irrespectively of the frequency of edge reversals in this step, it will lead to balanced squares of the form $++--{}$. Events with no sign reversal also contribute to $++++{}$ and $----{}$, in addition to $++--{}$. Notably, as long as some sign reversal occurs, it leads to the enrichment of $+-+-{}$ graphlets, contrary to the above-discussed node copying mechanism. Note that this particular scenario of edge copying is more feasible when a node can access information on the signed edges of other unrelated nodes. Intriguingly, this can potentially explain why the square graphlet results depend on the datasets. For example, in Slashdot, one can easily know others’ friends and foes without establishing a direct connection, potentially resulting in more balanced squares. Under other circumstances, individuals may have access to a strangers’ friend lists but may have limited access to a strangers’ blacklists (or foes) ²⁸, potentially leading to the underrepresentation of $----{}$ squares.

The three large signed social networks analyzed in this study were downloaded from the Stanford Network Analysis Platform (http://snap.stanford.edu/): (i) Bitcoin-Alpha, the trust/distrust network among people who trade Bitcoin on a platform called Bitcoin Alpha; (ii) Slashdot, friend/foes network of the technological news site Slashdot released on February 2009; (iii) Epinions, who-trust-whom online social network of a general consumer review site Epinions. The smaller scale Congress network is from ref. ². More details of the construction of the datasets can be found in ref. ^{1; 21}. Network edges are considered to be undirected. This process leads to only a very limited number of edge sign inconsistencies. Such inconsistent edges are disregarded in our analysis, together with any self-loops ²⁹. Only the largest connected component of each network is considered.

We construct an SB reference network according to Harary’s theorem of balance ²⁶. The 3000 nodes in the SB reference network are first divided into two equal groups. We then generate two degree sequences according to power-law degree distributions with $\mathrm{exponent}=2$ and $\mathrm{exponent}=3$ for positive and negative degree sequences, respectively. The negative degree sequence is used to generate negative edges between members of different groups and the positive degree sequence is used to generate positive edges between members of the same groups. For the positive degree sequence, we swap each degree with another randomly picked degree in the sequence with $\mathrm{probability}=0.2$ to deliberately make positive degrees and negative degrees less correlated ($r=0.56$). The resulting SB reference network has comparable density and positive edge ratios to real-life social networks as shown in Table 1.

We use the edge copying mechanism to construct EC networks. We initialized the construction process with a balanced $+++$ triangle and subsequently added nodes to the network. Each new node connects to a randomly chosen node ²⁷, with the sign determined by a parameter $q$, which defines the probability of a positive edge. Additionally, each new node attempts to connect to the neighbors of the selected node with a probability $p$. If the new node is connected to the selected node with a positive (negative) edge, the new node copies (reverses) the sign between the randomly chosen node and its neighbor. We used the parameter values $p=0.3,q=0.85$. The positive and negative degrees follow the power-law degree distribution shown in Fig. S2.

In the rewire null model, we randomly pick two edges $A\rightarrow B$ and $C\rightarrow D$ and try to swap the edges as $A\rightarrow D$ and $C\rightarrow B$. Such an attempt is aborted when the resulting edges form self-loops ($A\rightarrow A$) or existing edges. To achieve sufficient network randomization, we perform $4E$ edge swap attempts, where $E$ represents the number of edges in the network. In the signed rewire null model, we use the same method as in the rewire null model but only swap edges if they have the same sign, thus preserving the signed degrees of each node. This may lead to multi-edges with both positive and negative signs. In such cases, we randomly assign a sign to the edge. In the sign shuffle null model, we randomly and independently assign positive or negative signs to each edge, while preserving the total number of positive and negative edges.

A signed network $G$, is first divided into two subnetworks, namely the positive (negative) subnetwork $G_{p}$ ($G_{n}$) that includes all the positive (negative) edges in $G$. We then randomly select a subnetwork $G_{pr}$ from $G$ while keeping the node degrees of $G_{pr}$ the same as $G_{p}$ on average. The remaining network is considered as the randomized negative subnetwork $G_{nr}$. The required constrained randomization is achieved using the maximum entropy approach ^{42; 43}. To construct $G_{pr}$, we fix its average node degree as the original degree in $G_{p}$ as $<k_{i}>_{Gpr}=k_{i}(Gp)$. The resulting probability of selecting an existing edge in $G$ to be part of the subnetwork between nodes $i$ and $j$ is given by $p_{ij}=1/(1+\alpha_{i}\alpha_{j})$, where $\alpha_{i}$ are found iteratively as

$$\alpha_{i}^{\prime}=\frac{1}{k_{i}}\sum_{j,(i,j)\in G}\frac{1}{\alpha_{j}+1/\alpha_{i}}.$$

(3)

The initial condition is simply $\alpha_{i}^{(0)}\equiv 1$ and we stop the iteration when the maximum relative change of $\alpha_{i}$ is less than $10^{-3}$ between two consecutive iterations.

For reproducibility, we provide code and processed data at https://github.com/hbj153/signed_null.