Assessing frustration in real-world signed networks: traditional or relaxed balance?
Anna Gallo Diego Garlaschelli Tiziano Squartini





anna.gallo@imtlucca.it
IMT School for Advanced Studies, Piazza San Francesco 19, 55100 Lucca (Italy)
INdAM-GNAMPA Istituto Nazionale di Alta Matematica `Francesco Severi', P.le Aldo Moro 5, 00185 Rome (Italy)

IMT School for Advanced Studies, Piazza San Francesco 19, 55100 Lucca (Italy)
INdAM-GNAMPA Istituto Nazionale di Alta Matematica `Francesco Severi', P.le Aldo Moro 5, 00185 Rome (Italy)
Lorentz Institute for Theoretical Physics, University of Leiden, Niels Bohrweg 2, 2333 CA Leiden (The Netherlands)

IMT School for Advanced Studies, Piazza San Francesco 19, 55100 Lucca (Italy)
Scuola Normale Superiore, Piazza dei Cavalieri 7, 56126 Pisa (Italy)
INdAM-GNAMPA Istituto Naziqonale di Alta Matematica `Francesco Severi', P.le Aldo Moro 5, 00185 Rome (Italy)




According to traditional balance theory, individual social actors avoid establishing triads with an odd number of negative links. Generalising, mesoscopic balance is realised when the nodes of a signed graph can be grouped into positively connected subsets, mutually connected by negative links. If this prescription is interpreted rigidly without allowing for statistical noise, it quickly dismisses most real graphs as frustrated. As an alternative, a relaxed, yet qualitative, definition of balance has been advanced. After rephrasing both variants in statistically testable terms, we propose an inference scheme to unambiguously assess if a signed graph is traditionally or relaxedly balanced.


Assessing frustration in real-world signed networks: traditional or relaxed balance?
    Tiziano Squartini
    April 29, 2024
====================================================================================





  
*Introduction. The interest towards signed networks dates back to the balance theory (BT), firstly proposed by Heider as a theory of behaviour <cit.>. The choice of adopting signed graphs to model it has, then, led Cartwright and Harary <cit.> to introduce its structural version <cit.>. As the name suggests, BT deals with the concept of balance: a complete, signed graph is said to be balanced if all triads have an even number of negative edges, i.e. either zero (in this case, the three edges are all positive) or two. The so-called structure theorem states that a complete, signed graph is balanced if and only if its set of nodes can be partitioned into k=2, disjoint subsets whose intra-modular links are all positive and whose inter-modular links are all negative. Cartwright and Harary extended the definition of balance to incomplete graphs <cit.> by including cycles of length larger than three: a network is, now, said to be balanced if all cycles have an even number of negative edges (although the points of each subset are no longer required to be connected). Taken together, the criteria above define the so-called strong balance theory (SBT). Such a framework has been further extended by Davis <cit.>, who introduced the concept of k-balanced networks, according to which signed graphs are balanced if their set of nodes can be partitioned into k≥2, disjoint subsets with positive, intra-modular links and negative, inter-modular links. This generalised definition of balance has led to the formulation of the weak balance theory (WBT), according to which triads whose edges are all negative are balanced as well, since each node can be thought of as a group on its own. From a mesoscopic perspective, however, both versions of the BT require the presence of positive blocks along the main diagonal of the adjacency matrix (k=2, according to the strong variant; k>2, according to the weak variant) and of negative, off-diagonal blocks. Taken together, the SBT and the WBT define what will be called traditional balance theory (TBT): hence, k-balanced networks are traditionally balanced.




  
*Setting up the formalism. Each edge of a signed graph can be positive, negative or missing: as we will focus on binary, undirected, signed networks, a generic entry of the signed adjacency matrix 𝐀 will be assumed to read a_ij=-1,0,+1, with a_ij=a_ji, ∀ i<j. To ease mathematical manipulations, let us employ Iverson's brackets (a notation ensuring all quantities of interest to be non-negative - see Appendix AppAA) and define the quantities a_ij^-=[a_ij=-1], a_ij^0=[a_ij=0], a_ij^+=[a_ij=+1]: the new variables are mutually exclusive, sum to 1 and induce the two matrices 𝐀^+ and 𝐀^-, satisfying 𝐀=𝐀^+-𝐀^- and |𝐀|=𝐀^++𝐀^-. The number of positive and negative links is defined as L^+=∑_i=1^N∑_j(>i)a_ij^+ and L^-=∑_i=1^N∑_j(>i)a_ij^-, respectively.




  
*Traditional Balance Theory. The top-down formulation of the TBT leads quite naturally to the definition of a score function for quantifying the `degree of compatibility' of a given partition with the TBT itself. It is named frustration[More formally, line index of imbalance <cit.>.] and reads


    F(σ)   =∑_i=1^N∑_j(>i)a_ij^-δ_σ_i,σ_j+∑_i=1^N∑_j(>i)a_ij^+(1-δ_σ_i,σ_j)
       =L_∙^-+L^+-L_∙^+
       =L_∙^-+L_∘^+

where σ≡{σ_i} stands for a vector of labels characterising a generic partition and δ_σ_i,σ_j is the Kronecker delta (i.e. δ_σ_i,σ_j=1 if σ_i=σ_j and 0 otherwise). In words, F(σ) counts the amount of misplaced links according to the TBT, i.e. the number of negative links within modules plus the number of positive links between modules. The simplest, operative criterion for singling out a k-balanced partition is based upon the following theorem.


Theorem I. F(σ)=0⟺ the partition σ is k-balanced.


Proof. Sufficiency condition: F(σ)=0⟹ the partition σ is k-balanced. Since L_∘^+≥0 and L_∙^-≥0, F(σ)=0 implies that L_∘^+=0 and L_∙^-=0; hence, the definition of k-balanced partition is satisfied. Necessity condition: the partition σ is k-balanced ⟹ F(σ)=0. Since a k-balanced partition is defined by the presence of a clustering with k subsets, no negative links within modules and no positive links between modules, L_∙^-=0 and L_∘^+=0; hence, F(σ)=0. 


In words, the bare, numerical value F(σ) can be thought of as acting in a threshold-like fashion, classifying the configurations characterised by F(σ)=0 as balanced and the configurations characterised by F(σ)>0 as frustrated, according to the TBT. The criterion embodied by the F-test is, however, too strict for real-world networks, which are hardly (if ever) found to obey it: as table <ref> shows, in fact, none of the listed configurations passes it.




  
*Softening frustration. As noticed by Doreian and Mrvar <cit.>, the block-structure defining the TBT is overly restrictive, dooming the vast majority of real-world, signed networks to be quickly dismissed as frustrated: in order to overcome what was perceived as a major limitation of the TBT, they proposed to replace F(σ) with its softened variant


    G(σ|α)=α L_∙^-+(1-α) L_∘^+,

allowing i) the misplaced, positive links to be weighted more upon choosing 0≤α<1/2; ii) the misplaced, negative links to be weighted more upon choosing 1/2<α≤1. Even ignoring the ambiguity due to the lack of a principled way for selecting α (the so-called `α problem' in <cit.>), the criterion embodied by the G-test is still too strict: as table <ref> shows, in fact, none of the listed configurations passes it either. This is rigorously stated by the following theorem, whose proof is immediate.


Theorem II. If 0<α<1, F(σ)=0⟺ G(σ|α)=0, i.e. the partition σ is k-balanced.


Notice that the values α=0 and α=1 would, respectively, lead to the trivially balanced partition characterised by a single community gathering all nodes together and N single-node communities (or singletons).






  
*Relaxed Balance Theory. In the light of the previous results, the second attempt pursued by Doreian and Mrvar to overcome the perceived limitations of the TBT was more radical, as they proposed to relax it by allowing for the presence of positive, off-diagonal blocks and negative, diagonal blocks - a generalisation that has gained the name of relaxed balance theory (RBT) <cit.>. Such a formulation of the RBT, however, lacks a proper mathematisation, as a score function such as F(σ), or G(σ|α), cannot be easily individuated. Besides, it is affected by the problem highlighted in <cit.>: `[…] if the number of clusters is left unspecified a priori, the best partition is the singletons partition (i.e. each node in its own cluster) […]'.






  
*Statistical Balance Theory. Re-casting the theory of balance within a statistical framework solves all the aforementioned problems at once, allowing us to define an inference scheme to unambiguously assess if a signed graph is traditionally or relaxedly balanced - hence, overcoming the limitations of the F-based and G-based tests while providing a proper mathematisation of the RBT.

In order to turn the TBT into a statistical theory of balance, let us suppose the presence of a probabilistic model behind the appearance of any, signed configuration: the TBT can be, then, rephrased by posing p_rr^-=0, r=1… k and p_rs^+=0, ∀ r<s. The starting point of our approach is that of softening these positions, replacing them with the milder relationships sgn[p_rr^+-p_rr^-]=+1, r=1… k and sgn[p_rs^+-p_rs^-]=-1, ∀ r<s which amount at requiring that p_rr^+>p_rr^-, r=1… k and p_rs^+<p_rs^-, ∀ r<s. A configuration satisfying these relationships will be claimed to obey the statistical variant of the TBT: specifically, its strong variant if k=2 and its weak variant if k>2; otherwise (because p_rr^+≤ p_rr^- for some, diagonal blocks or p_rs^+≥ p_rs^- for some, off-diagonal blocks), it will be claimed to obey the statistical variant of the RBT. Additionally, we define a partition homogeneous if either p_rs^+=0 or p_rs^-=0, ∀ r≤ s; otherwise, it will be defined heterogeneous (see Appendix AppBB).



Tuning the aforementioned parameters on a given, signed network requires a generative model to be specified: here, we will adopt the Signed Stochastic Block Model (SSBM), defined by the likelihood function


    ℒ_SSBM=   ∏_r=1^k(p_rr^+)^L_rr^+(p_rr^-)^L_rr^-(1-p_rr^+-p_rr^-)^N_r2-L_rr
       ∏_r=1^k∏_s(>r)(p_rs^+)^L^+_rs(p_rs^-)^L^-_rs(1-p_rs^+-p_rs^-)^N_rN_s-L_rs

where N_r is the number of nodes constituting block r, L_rr^+ (L_rr^-) is the number of positive (negative) links within block r, L_rs^+ (L_rs^-) is the number of positive (negative) links between blocks r and s, ∀ r<s and the probability coefficients read p_rr^+=2L_rr^+/N_r(N_r-1), p_rr^-=2L_rr^-/N_r(N_r-1), r=1… k and p_rs^+=L_rs^+/N_rN_s, p_rs^-=L_rs^-/N_rN_s, ∀ r<s. As maximising the bare likelihood is a recipe known to be affected by a number of limitations <cit.>, we have opted for the minimisation of


    BIC   =κ_SSBMln n-2lnℒ_SSBM,

named Bayesian Information Criterion and embodying a trade-off between parsimony (accounted for by the first addendum, with κ_SSBM being the number of parameters of the model[To avoid confusion with the number of modules, k, characterising k-balanced networks, we have indicated the number of a model parameters as κ: naturally, κ_SSBM=k(k+1) since we need to estimate two parameters per module.] and n=N(N-1)/2 proxying the system dimensions) and accuracy (accounted for by the second addendum, i.e. the log-likelihood term).




  
*Results. First, let us test our prescription on a number of synthetic configurations. As fig. <ref> shows, BIC minimisation always leads to recover the planted partition, irrespectively from the values of the sets of coefficients {p_rr^+}, {p_rr^-}, {p_rs^+}_r<s, {p_rs^-}_r<s, i.e. be it a homogeneous partition balanced according to the weak variant of the TBT (more precisely, a 4-balanced partition); two, homogeneous partitions, balanced according to the RBT (e.g. the third adjacency matrix is defined by p_11^+=p_22^+=p_33^+=0 and p_12^-=p_13^-=p_23^-=0); an heterogeneous partition, balanced according to the statistical variant of the RBT (i.e. the fourth adjacency matrix, defined by p_11^+<p_11^-, p_22^+>p_22^-, p_33^+>p_33^- and p_12^+<p_12^-, p_13^+<p_13^-, p_23^+<p_23^-).

Second, let us compare our recipe with that prescribing to minimise F(σ). As fig. <ref> shows, implementing the latter does not lead to recover the planted partition (in this case, a homogeneous one, compatible with the RBT): instead, it leads to a traditionally balanced configuration where the planted, negative cliques have been fragmented into singletons. More in general, minimising F(σ) can lead to a number of ambiguous situations, such as i) returning configurations that are neither traditionally nor relaxedly balanced; ii) returning more than one frustrated configuration (see Appendix AppBB).



Let us, now, apply our recipe to a number of real-world, signed configurations, i.e. four snapshots of the `Correlates of Wars' (CoW) dataset <cit.>, providing a picture of the international, political relationships over the years 1946-1997 and consisting of 13 snapshots of 4 years each: a positive edge between any two countries indicates an alliance, a political agreement or the membership to the same governmental organisation; conversely, a negative edge indicates that the two countries are enemies, have a political disagreement or are part of different, governmental organisations. As fig. <ref> shows, minimising BIC leads to recover partitions that obey the statistical variant of the RBT (a blue block is characterised by a majority of positive links; a red block is characterised by a majority of negative links); other real-world, signed configurations, instead, are found to obey the statistical variant of the TBT (see Appendix AppBB). All such partitions are heterogeneous.






  
*Discussion. The present paper proposes a statistical approach to the theory of balance, assuming that any real-world, signed configuration is the result of a generative process, probabilistic in nature. As some degree of statistical noise is expected to affect a network structure, the criterion adopted to deem if it obeys the TBT or the RBT can be re-cast in terms of the signs of the differences of the block-wise probabilities to observe a positive and a negative link, i.e. p_rs^+-p_rs^-, ∀ r≤ s. Estimating these coefficients by minimising BIC allows one to unambiguously assess which variant of the theory is obeyed, from a statistical perspective, by any, signed configuration.

On the contrary, minimising F(σ) is practically equivalent at carrying out a sort of one-sided test of hypothesis, allowing one to state if a given partition does not obey the TBT (as a matter of fact, practically always) but incapable of providing a univocal classification for a generic, signed configuration. Moreover, it `works' even with configurations generated by the Signed Random Graph Model (SRGM), i.e. a model carrying no information about a network modular structure, hence overfitting (i.e. misinterpreting statistical noise as a genuine signal - see Appendix AppBB).

Under this respect, maximising the signed modularity Q(σ) is of no help, being defined as


    Q(σ)   =∑_i=1^N∑_j(>i)[(a_ij^+-p_ij^+)-(a_ij^–p_ij^-)]δ_σ_i,σ_j
       =-F(σ)+⟨ F(σ)⟩+L^+-⟨ L^+⟩

with obvious meaning of the symbols (the addendum L^+-⟨ L^+⟩ is just an offset not depending on the specific partition and amounting at zero for any model reproducing the total number of positive links) <cit.>. In words, the signed modularity compares the empirical amount of frustration of a given, signed configuration with the one predicted by a properly-defined reference model: one may, thus, define a partition as statistically balanced if satisfying the relationship F(σ)<⟨ F(σ)⟩, i.e. Q(σ)>0. Although reasonable, such a criterion does not differ (much) from the one embodied by the F-test: more formally, it can be proven that the relationship L^+≫ L^- (often, if not always, found to hold true for real-world, signed networks) favours the fragmentation of the negative cliques into singletons, hence leading to recover traditionally balanced configurations even when there is none `by design' (see fig. <ref> and Appendix AppCC).

Existing works have completely overlooked the issue of harmonising the request of having balanced configurations with that of having modular configurations, in most of the cases verifying either the `degree of balance' of modular structures or the `degree of modularity' of balanced structures a posteriori. Ignoring the interplay between the signs and the density of connections, solely accounting for the information carried by the first ones, may, in fact, lead to `resolution errors', i.e. i) splitting modules (even fully-connected ones) into finer regions; ii) misinterpreting adjacent modules, characterised by the same, dominant sign, as single, coarser regions.

BIC, instead, is sensitive to the `signed density' of the modules `by design', hence capable of spotting the presence of groups of nodes as well as attributing to each of them the sign of the majority of its constituting links: beside lying the basis of a more comprehensive theory of balance, grounded on probability theory, such a desirable feature reconciles the generally contradictory results one gets when combining a purely structure-based community detection with a purely sign-based one.







AppA


§ APPENDIX A.
REPRESENTING BINARY, UNDIRECTED, SIGNED NETWORKS


The three functions a_ij^-=[a_ij=-1], a_ij^0=[a_ij=0] and a_ij^+=[a_ij=+1] have been defined via the Iverson's brackets notation. Iverson's brackets work in a way that is reminiscent of the Heaviside step function, i.e. Θ[x]=[x>0]; in fact,


    a_ij^-=[a_ij=-1]=
    1,    if   a_ij=-1
    
    0,    if   a_ij=0,+1

(i.e. a_ij^-=1 if a_ij<0 and zero otherwise),


    a_ij^0=[a_ij=0]=
    1,    if   a_ij=0
    
    0,    if   a_ij=-1,+1

(i.e. a_ij^0=1 if a_ij=0 and zero otherwise),


    a_ij^+=[a_ij=+1]=
    1,    if   a_ij=+1
    
    0,    if   a_ij=-1,0

(i.e. a_ij^+=1 if a_ij>0 and zero otherwise). These new variables are mutually exclusive, i.e. {a_ij^-,a_ij^0,a_ij^+}={(1,0,0),(0,1,0),(0,0,1)} and sum to 1, i.e. a_ij^-+a_ij^0+a_ij^+=1. The matrices 𝐀^+≡{a_ij^+}_i,j=1^N and 𝐀^-≡{a_ij^-}_i,j=1^N remain naturally defined, inducing the relationships 𝐀=𝐀^+-𝐀^-, i.e. a_ij=a_ij^+-a_ij^-, ∀ i≠ j and |𝐀|=𝐀^++𝐀^-, i.e. |a_ij|=a_ij^++a_ij^-, ∀ i≠ j.



AppB


§ APPENDIX B.
MINIMISATION OF THE BAYESIAN INFORMATION CRITERION




 §.§ Signed Stochastic Block Model (SSBM) and Bayesian Information Criterion (BIC)




Let us, first, recall the derivation of the SSBM. It is defined by the Hamiltonian


    H(𝐀)   =∑_r≤ s[α_rs L_rs^+(𝐀)+β_rs L_rs^-(𝐀)]
       =∑_r≤ s{α_rs[∑_i=1^N∑_j(>i)δ_g_irδ_g_jsa_ij^+]+β_rs[∑_i=1^N∑_j(>i)δ_g_irδ_g_jsa_ij^-]}
       =∑_i=1^N∑_j(>i)[α_g_ig_j a_ij^++β_g_ig_j a_ij^-]

leading to


    Z=∑_𝐀∈𝔸e^-H(𝐀)=∑_𝐀∈𝔸∏_i=1^N∏_j(>i)e^-[α_g_ig_j a_ij^++β_g_ig_j a_ij^-]   =∏_i=1^N∏_j(>i)∑_a_ij=-1,0,+1e^-[α_g_ig_j a_ij^++β_g_ig_j a_ij^-]
       =∏_i=1^N∏_j(>i)[1+e^-α_g_ig_j+e^-β_g_ig_j].


As a consequence, 


    P_SSBM(𝐀)=e^-H(𝐀)/Z=∏_i=1^N∏_j(>i)e^-[α_g_ig_j a_ij^++β_g_ig_j]/∏_i=1^N∏_j(>i)[1+e^-α_g_ig_j+e^-β_g_ig_j]   ≡∏_i=1^N∏_j(>i)x_g_ig_j^a_ij^+y_g_ig_j^a_ij^-/1+x_g_ig_j+y_g_ig_j
       ≡∏_i=1^N∏_j(>i)(p_g_ig_j^+)^a_ij^+(p_g_ig_j^0)^a_ij^0(p_g_ig_j^-)^a_ij^-

having posed e^-α_g_ig_j≡ x_g_ig_j, e^-β_g_ig_j≡ y_g_ig_j, p_ij^+≡ x_g_ig_j/(1+x_g_ig_j+y_g_ig_j), p_ij^-≡ y_g_ig_j/(1+x_g_ig_j+y_g_ig_j), p_ij^0≡ 1/(1+x_g_ig_j+y_g_ig_j); let us notice that


    P_SSBM(𝐀)   =∏_i=1^N∏_j(>i)∏_r=1^k∏_s(≥ r)[(p_rs^+)^a_ij^+(p_rs^0)^a_ij^0(p_rs^-)^a_ij^-]^δ_g_irδ_g_js
       =∏_r=1^k∏_s(≥ r)∏_i=1^N∏_j(>i)[(p_rs^+)^δ_g_irδ_g_jsa_ij^+(p_rs^0)^δ_g_irδ_g_jsa_ij^0(p_rs^-)^δ_g_irδ_g_jsa_ij^-]
       =∏_r=1^k∏_s(≥ r)[(p_rs^+)^∑_i=1^N∑_j(>i)δ_g_irδ_g_jsa_ij^+(p_rs^0)^∑_i=1^N∑_j(>i)δ_g_irδ_g_jsa_ij^0(p_rs^-)^∑_i=1^N∑_j(>i)δ_g_irδ_g_jsa_ij^-]
       =∏_r=1^k(p_rr^+)^L_rr^+(p_rr^0)^L_rr^0(p_rr^-)^L_rr^-·∏_r=1^k∏_s(>r)(p_rs^+)^L_rs^+(p_rs^0)^L_rs^0(p_rs^-)^L_rs^-
       =∏_r=1^k(p_rr^+)^L_rr^+(p_rr^-)^L_rr^-(1-p_rr^+-p_rr^-)^N_r2-L_rr·∏_r=1^k∏_s(>r)(p_rs^+)^L^+_rs(p_rs^-)^L^-_rs(1-p_rs^+-p_rs^-)^N_rN_s-L_rs
       =∏_r=1^kx_rr^L_rr^+y_rr^L_rr^-/[1+x_rr+y_rr]^N_r2·∏_r=1^k∏_s(>r)x_rs^L_rs^+y_rs^L_rs^-/[1+x_rs+y_rs]^N_r N_s

where p_rr^+=x_rr/(1+x_rr+y_rr), p_rr^-=y_rr/(1+x_rr+y_rr), r=1… k and p_rs^+=x_rs/(1+x_rs+y_rs), p_rs^-=y_rs/(1+x_rs+y_rs), ∀ r<s. Its log-likelihood reads




    lnℒ_SSBM=   ∑_r=1^k[L_rr^+(𝐀)ln x_rr+L_rr^-(𝐀)ln y_rr-N_r2ln[1+x_rr+y_rr]]
       +∑_r=1^k∑_s(>r)[L_rs^+(𝐀)ln x_rs+L_rs^-(𝐀)ln y_rs-N_rN_rln[1+x_rs+y_rs]]

and its maximisation leads to recover the conditions p_rr^+=2L_rs^+(𝐀)/N_r(N_r-1), p_rr^-=2L_rs^-(𝐀)/N_r(N_r-1), r=1… k and p_rs^+=L_rs^+(𝐀)/N_rN_s, p_rs^-=L_rs^-(𝐀)/N_rN_s, ∀ r<s.


Let us, now, recall that BIC is defined as


    BIC=κln n-2lnℒ

where ℒ is a model likelihood and κ indicates the number of parameters entering into its definition. Here, we have posed ℒ≡ℒ_SSBM, κ≡κ_SSBM=k(k+1) (i.e. k+k(k-1)/2 parameters to be tuned on the set of values L_rs^+, ∀ r≤ s and k+k(k-1)/2 parameters to be tuned on the set of values L_rs^-, ∀ r≤ s) and n=N(N-1)/2.

Figure <ref> shows three, ideal partitions: one compatible with the strong balance theory, one compatible with the weak balance theory and one compatible with the relaxed balanced theory.



 §.§ Comparing BIC minimisation with F minimisation


Let us, now, carry out another comparison between the recipe prescribing to minimise F(σ) and the one prescribing to minimise BIC. As fig. <ref> shows. the partitions that are recovered upon minimising BIC match the planted ones, a result confirming that BIC is sensitive to the `signed density' of the modules. As a consequence, the partitions recovered upon minimising it coincide with the ones recovered upon minimising F(σ) only if the former ones are k-balanced, i.e. satisfy the relationships p_rr^-=0, r=1… k and p_rs^+=0, ∀ r<s.



Minimising F(σ) can lead to a number of ambiguous situations, such as i) returning configurations that are neither traditionally nor relaxedly balanced; ii) returning more than one frustrated configuration.

Figure <ref> depicts the first situation. Nodes of the same colour are those put together as a consequence of minimising F(σ): although the presence of negative links between and within modules makes the recovered partitions `traditionally' frustrated, the original formulation of the RBT would lead us to conclude that they are `relaxedly' frustrated as well; only within our, novel, statistical framework these configurations can be unambiguously classified as balanced according to the statistical variant of the TBT.

Figure <ref> depicts the second situation: the minimisation of F(σ) can return more than one frustrated configuration; our BIC-based test, however, `prefers' the one on the left, classifying it as balanced according to the statistical variant of the TBT.



 §.§ Minimising BIC on configurations generated by the Signed Random Graph Model (SRGM)


Let us, first, recall the derivation of the SRGM. It is defined by the Hamiltonian


    H(𝐀)=α L^+(𝐀)+β L^-(𝐀)=∑_i=1^N∑_j(>i)[α a_ij^++β a_ij^-]

leading to


    Z=∑_𝐀∈𝔸e^-H(𝐀)=∑_𝐀∈𝔸∏_i=1^N∏_j(>i)e^-[α a_ij^++β a_ij^-]   =∏_i=1^N∏_j(>i)∑_a_ij=-1,0,+1e^-[α a_ij^++β a_ij^-]
       =∏_i=1^N∏_j(>i)[1+e^-α-β]=[1+e^-α-β]^N2.




As a consequence, 


    P_SRGM(𝐀)=e^-H(𝐀)/Z=e^-[α L^+(𝐀)+β L^-(𝐀]/[1+e^-α-β]^N2≡x^L^+(𝐀)y^L^-(𝐀)/[1+x+y]^N2≡(p^-)^L^-(𝐀)(p^0)^L^0(𝐀)(p^+)^L^+(𝐀)

where p^+=x/(1+x+y), p^-=y/(1+x+y) and p^0=1/(1+x+y). Its log-likelihood reads


    lnℒ_SRGM=L^+(𝐀)ln x+L^-(𝐀)ln y-N2ln[1+x+y]

and its maximisation leads to recover the conditions p^+=2L^+(𝐀)/N(N-1), p^-=2L^-(𝐀)/N(N-1).

Figure <ref> shows three configurations generated by the SRGM. As such a model does not carry any information about a network modular structure, no groups of nodes should be recognised. This is precisely the output of our BIC-based recipe, returning a single community gathering all nodes together (i.e. k=1), irrespectively from the choice of the parameters (i.e. be p^+<p^-, p^+≃ p^- or p^+>p^-). Minimising F(σ) (or maximising Q(σ) - see Appendix AppCC), instead, leads to recover a number of modules k≥1 (in the case L^+<L^-, k_F=25 and k_Q=13; in the case L^+≃ L^-, k_F=6 and k_Q=5; in the case L^+>L^-, k_F=k_Q=1).



 §.§ Minimising BIC on negative and positive cliques


Let us, now, consider a negative clique composed by N nodes; evaluating BIC on the partition defined by k modules returns the value k(k+1)ln[N(N-1)/2]; since N≥ k≥ 1, keeping all nodes together is the most convenient choice. The same result holds true if we consider a positive clique composed by N nodes, the reason lying in the completely symmetric role played by negative and positive links, both contributing to the density of the (potential) network modules.



 §.§ Minimising BIC on complete, signed graphs


When dealing with complete graphs, the signs come into play in a quite peculiar fashion. Let us, in fact, consider a complete graph of size N=N_1+N_2, constituted by two, negative cliques having, respectively, N_1 and N_2 nodes and such that each node of a clique is connected to each node of the other via a positive link. Let us, now, pose k>2 and consider the following inequality


    k(k+1)lnN2-2lnℒ_SSBM>6lnN2

stating that evaluating BIC on a generic partition defined by k>2 modules returns a value that is strictly larger than the value of BIC calculated on the bi-partition whose modules coincide with the cliques themselves (in fact, N≥ k>2 and lnℒ_SSBM>0).



Let us, now, compare the bi-partition induced by the negative cliques with the partition induced by imposing the presence of just one module: in this, last case, evaluating BIC returns the value


    BIC(k=1)   =2lnN2-2ln[(p^+)^L^+(p^-)^L^-]
       =2lnN2-2ln[(2N_1N_2/N(N-1))^N_1N_2(N_1(N_1-1)+N_2(N_2-1)/N(N-1))^N_12+N_22]
       =2lnN2-2ln[(2N_1(N-N_1)/N(N-1))^N_1(N-N_1)(N_1(N_1-1)+(N-N_1)(N-N_1-1)/N(N-1))^N_12+N-N_12]

where we have used the relationship N_2=N-N_1. As depicted in fig. <ref>, splitting nodes according to the partition induced by the signs is always `more convenient' than partitioning them in a different way, a result suggesting that signs keep playing a role as long as the information embodied by the network density becomes irrelevant.

The same reasoning can be repeated for any number of cliques, the last relationship becoming


    c(c+1)lnN2   <2lnN2-2ln[(2∑_i<jN_iN_j/N(N-1))^∑_i<jN_iN_j(∑_i N_i(N_i-1)/N(N-1))^∑_iN_i2],

i.e. the partition defined by c modules coinciding with the cliques is the one characterised by the minimum value of BIC (see also fig. <ref>).











 §.§ Minimising BIC on more, real-world configurations


Let us, now, apply our recipe to a number of real-world, signed configurations, i.e. Fraternity, N.G.H. Tribes, Monastery and <cit.> and Slovenian Parliament <cit.>: as fig. <ref> shows, minimising BIC leads to recover partitions that obey the statistical variant of the TBT (either in its strong or weak form) in most of the cases (a blue block is characterised by a majority of positive links; a red block is characterised by a majority of negative links).

On the other hand, US Senate, EGFR, Macrophage, Bitcoin Alpha and Bitcoin OTC datasets <cit.> are characterised by k=1 (either because p^+≃ p^- or because p^+≫ p^-).



AppC


§ APPENDIX C.
MORE ON SIGNED MODULARITY


A deterministic theory of balance can be turned into a statistical theory of balance by answering the following question: is it possible to define a reference level of misplaced links by means of which discerning frustrated graphs from balanced ones? The answer is affirmative and calls for comparing the empirical amount of frustration of a given, signed configuration with the one predicted by a properly-defined reference model: in formulas, one may define a partition as statistically balanced if satisfying the relationship F(σ)<⟨ F(σ)⟩.

A quantity embodying such a comparison already exists: it is the signed modularity, reading


    Q(σ)   =∑_i=1^N∑_j(>i)[(a_ij^+-p_ij^+)-(a_ij^–p_ij^-)]δ_σ_i,σ_j
       =L_∙^+-⟨ L_∙^+⟩-(L_∙^–⟨ L_∙^-⟩)
       =(L^+-L_∘^+)-⟨ L^+-L_∘^+⟩-(L_∙^–⟨ L_∙^-⟩)
       =-(L_∘^++L_∙^-)+⟨ L_∘^++L_∙^-⟩+L^+-⟨ L^+⟩
       =-F(σ)+⟨ F(σ)⟩+L^+-⟨ L^+⟩

with obvious meaning of the symbols (the addendum L^+-⟨ L^+⟩ is just an offset not depending on the specific partition and amounting at zero for any model reproducing the total number of positive links) <cit.>. Since the total number of positive links is preserved under any model considered in the present paper, we obtain


    Q(σ)=-F(σ)+⟨ F(σ)⟩.


Q(σ) has been widely employed to spot communities on signed networks, with the positions p_ij^+=k_i^+k_j^+/2L^+ and p_ij^-=k_i^-k_j^-/2L^-, ∀ i<j. Such a recipe, instantiating the Chung-Lu (CL) model, is applicable only in case p_ij^+≤1 and p_ij^-≤1, ∀ i<j: these conditions, however, do not hold in several cases of interest, an example of paramount importance being provided by sparse networks whose degree distribution is scale-free <cit.>. In order to overcome the aforementioned limitation, a different framework is needed.

One may follow the analytical approach introduced in <cit.> and further developed in <cit.>, aimed at identifying the functional form of the maximum-entropy probability distribution that preserves a desired set of empirical constraints, on average. Specifically, this approach looks for the graph probability P(𝐀) that maximises Shannon entropy S=-∑_𝐀∈𝔸P(𝐀)ln P(𝐀), under constraints enforcing the expected value of a chosen set of properties. The formal solution to this problem is the exponential probability P(𝐀)=e^-H(𝐀)/Z where the Hamiltonian H(𝐀) is a linear combination of the constrained properties and the partition function Z=∑_𝐀∈𝔸e^-H(𝐀) plays the role of normalising constant, the sum running over the set 𝔸 of all binary, undirected, signed graphs whose cardinality amounts to |𝔸|=3^N2. Two examples of models of the kind are the Signed Random Graph Model (SRGM) and the Signed Configuration Model (SCM) <cit.>.

According to the TBT, several ways exist in which a given configuration can be frustrated. Let us, now, analyse them in detail.



  §.§.§ Evaluating frustration due to negative links




  
*Positive subgraphs connected by negative links. In order to understand how a Q-based test would work, let us consider two subgraphs with, respectively, m and n nodes, positive intra-modular links and negative inter-modular links. Let us denote with V_∙=m(m-1)/2+n(n-1)/2 the total number of intra-modular pairs of nodes and with Q_0 the value of modularity associated to the partition of the entire graph, except our, two subgraphs; let us also call L_∙^+ the total number of positive links within modules and L_∘^- the total number of negative links between modules. Then,


    Q_A   =Q_0+[L_∙^+-p^+V_∙]-[0-p^-V_∙],
    
    Q_B   =Q_0+[L_∙^+-p^+(V_∙+mn)]-[L_∘^–p^-(V_∙+mn)]

with Q_A being the SRGM-induced modularity of the configuration identifying our subgraphs as two, separate communities and Q_B being the SRGM-induced modularity of the configuration identifying our subgraphs as a single community. In order to be fully consistent with the TBT, one should require


    Q_A>Q_B=Q_A-L_∘^–(p^+-p^-)mn,

a condition that it is satisfied whenever L_∘^->(p^–p^+)mn, i.e. whenever the probability p_∘^-≡ L_∘^-/mn of establishing a negative link within modules is larger than p^–p^+=2(L^–L^+)/N(N-1). This condition sheds light on the role played by the signed variant of the resolution limit, naturally re-interpretable as a threshold-based criterion for discerning if a given, signed configuration is balanced or not: in words, the `acceptable' level of frustration, according to which our subgraphs can be safely interpreted as a single community, is represented by (p^–p^+)mn.



  §.§.§ Evaluating frustration due to positive links




  
*Positive subgraphs connected by positive links. Let us, now, consider two subgraphs with, respectively, m and n nodes, positive intra- and inter-modular links; let us also call L_∙^+ the total number of positive links within modules and L_∘^+ the total number of positive links between modules. Then,


    Q_A   =Q_0+[L_∙^+-p^+V_∙]-[0-p^-V_∙],
    
    Q_B   =Q_0+[L_∙^++L_∘^+-p^+(V_∙+mn)]-[0-p^-(V_∙+mn)]

with Q_A being the SRGM-induced modularity of the configuration identifying our subgraphs as two, separate communities and Q_B being the SRGM-induced modularity of the configuration identifying our subgraphs as a single community. In order to be fully consistent with the TBT, one should require


    Q_B=Q_A+L_∘^+-(p^+-p^-)mn>Q_A,

a condition that it is satisfied whenever L_∘^+>(p^+-p^-)mn, i.e. whenever the probability p_∘^+≡ L_∘^+/mn of establishing a positive link between modules is larger than p^+-p^-=2(L^+-L^-)/N(N-1). The threshold-based criterion for discerning balance represented by the signed variant of the resolution limit, now, sets the `acceptable' level of frustration, according to which our subgraphs can be safely interpreted as two, separate communities, at (p^+-p^-)mn.





  §.§.§ Evaluating frustration in real-world networks


Interestingly enough, when studying real-world, signed networks, the relationship L^+≫ L^- is often (if not always) found to hold true: as a consequence, the condition


    L_∘^->(p^–p^+)mn<0

is trivially satisfied. Such an evidence has several consequences. In order to discuss them, let us focus on i) the case of negative subgraphs connected by negative links; ii) the case of negative subgraphs connected by positive links.






  
*Negative subgraphs connected by negative links. Let us consider two subgraphs with, respectively, m and n nodes, negative intra- and inter-modular links; let us also call L_∙^- the total number of negative links within modules and L_∘^- the total number of negative links between modules. Then,


    Q_A   =Q_0+[0-p^+V_∙]-[L_∙^–p^-V_∙],
    
    Q_B   =Q_0+[0-p^+(V_∙+mn)]-[L_∙^-+L_∘^–p^-(V_∙+mn)]

with Q_A being the SRGM-induced modularity of the configuration identifying our subgraphs as two, separate communities and Q_B being the SRGM-induced modularity of the configuration identifying our subgraphs as a single community. In order to limit the number of links that would be deemed as misplaced according to the TBT, one should require


    Q_A>Q_B=Q_A-L_∘^–(p^+-p^-)mn,

a condition that it is satisfied whenever L_∘^->(p^–p^+)mn, i.e. whenever the probability p_∘^-≡ L_∘^-/mn of establishing a negative link between modules is larger than p^–p^+=2(L^–L^+)/N(N-1)<0. Hence, it is always convenient to separate negatively connected modules and, if such a line of reasoning is repeated in a hierarchical fashion, it is always convenient to separate negatively connected nodes. Otherwise stated, one should not expect the presence of negative links within blocks since negatively connected modules will always lead to singletons: in this sense, the signed modularity is resolution limit-free.




  
*Negative subgraphs connected by positive links. Let us, now, focus on the case of negative subgraphs connected by positive links and consider two subgraphs with, respectively, m and n nodes, negative intra-modular links and positive inter-modular links; let us also call L_∙^- the total number of negative links within modules and L_∘^+ the total number of positive links between modules. Then,


    Q_A   =Q_0+[0-p^+V_∙]-[L_∙^–p^-V_∙],
    
    Q_B   =Q_0+[L_∘^+-p^+(V_∙+mn)]-[L_∙^–p^-(V_∙+mn)]

with Q_A being the SRGM-induced modularity of the configuration identifying our subgraphs as two, separate communities and Q_B being the SRGM-induced modularity of the configuration identifying our subgraphs as a single community. In order to limit the number of links that would be deemed as misplaced according to the TBT, one should require


    Q_B=Q_A+L_∘^+-(p^+-p^-)mn>Q_A,

a condition that it is satisfied whenever L_∘^+>(p^+-p^-)mn, i.e. whenever the probability p_∘^+≡ L_∘^+/mn of establishing a positive link between modules is larger than p^+-p^-=2(L^+-L^-)/N(N-1). Now, as a consequence of eq. (<ref>), it is convenient to fragment negatively connected modules into singletons; hence, according to the TBT, frustration can only occur because of misplaced, positive links appearing between blocks.

Figure <ref> depicts the results of the signed modularity maximisation on three rings of cliques: since the relationship L^+≫ L^- holds true, one should not expect the presence of negative links within blocks (as we said, the signed modularity is resolution limit-free, in this sense). Notice that our exercise is defined in such a way that the numerical value of the generic addendum (a_ij^+-p_ij^+)-(a_ij^–p_ij^-) is fixed, once and for all, by the choice of the benchmark to be solved: in other words, the definition of modularity does not change with the level of aggregation, being just recomputed (as any other score function) as the partition changes <cit.>.

As fig. <ref> shows, minimising BIC returns partitions that coincide with those returned by maximising modularity, or minimising F(σ), solely in case they are k-balanced (i.e. obey the TBT). In case subgraphs constituted by negative links are, instead, present, minimising BIC leads to the planted partition induced by gathering such nodes together while maximising Q(σ) leads to their fragmentation, hence recovering singletons. In other words, the Q-based test (exactly as the F-based test and the G-based test) seeks to recover traditionally balanced configurations even when there is none `by design'.

From a purely numerical perspective, partitioning nodes by minimising BIC is accomplished as described in Algorithms <ref> - <ref>.










