1 Introduction

A group of individuals can often be viewed as social networks, where nodes represent individuals and edges their relations (Wasserman and Faust 1994; Young 2011; Watts and Strogatz 1998; Albert and Barabási 2002; Newman 2003; Fowler and Christakis 2010; McPherson et al. 1992; Borgatti et al. 2009; Hanaki et al. 2007; Schilling and Phelps 2007; Lazer et al. 2009; Carrington et al. 2005; Wang et al. 2011, 2012; Liang et al. 2013; He et al. 2013; Zheng et al. 2008, 2009a, b; Cui et al. 2013a). Traditionally, these social networks are depicted in basic forms such as undirected, directed or weighted, and analyzed by mainly considering their topological patterns. However, in many interesting real-world social systems, links between two nodes may display diversity, and the content of the relations in a social community is often more important than their topological patterns (Facchetti et al. 2011). For example, each person can express his positive or negative sentiments such as like, or dislike on others from an individual perspective (Wasserman and Faust 1994; Zajonc and Sherman 1967; Tang et al. 2012), while for international relations among nations, different countries may have exhibit different states of equilibrium and disequilibrium (Harary 1961). Users in cyberspace can also vote the nominated persons as administrators (Burke and Kraut 2008), or express trust or distrust of others (Guha et al. 2004; Brzozowski et al. 2008; Kim 2007; Ziegler and Lausen 2005).

To quantify and extrapolate the content-related features of reciprocated relations between social entities presented above, we should further develop more efficient analytical and computational approaches. Signed networks, whose links are often labeled as different signs, for instance “+” or “−” (Wasserman and Faust 1994; Easley and Kleinberg 2010; Yang et al. 2007; Katai and Iwai 1978), have recently attracted more and more attentions. By analyzing the properties of these signed social networks, we can better identify the key role of that network structure plays when some relations between social entities are positive while others are negative (Leskovec et al. 2010a). This type of information, which may not be provided by other traditional network representations, can provide us significant insights into understanding in depth the cognition or awareness of social interactions in one social system and further inferring how the targeted social system evolves and when the system will reach balanced or relative stable status.

This presented above has been formed to one significant theory, called social balance or structural balance, which is originated from several early studies of Heider (1944, 1946) at the individual level and generalized by Cartwright and Harary (1956; Harary 1953, 1955, 1960; Harary and Kommel 1979) in the graph-theoretical formation at the group level. The basic principles underlying social balance are commonly characterized with the aphorisms: “The friend of my friend is my friend, the friend of my enemy is my enemy, the enemy of my enemy is my friend” (Thomas 2010; Aronson and Cope 1968; Lerner 2008; Van De Rijt 2011). The social balance theory affirms that human societies tend to avoid tensions and conflictual relations (Facchetti et al. 2011; Easley and Kleinberg 2010; Newcomb 1956, 1961, 1981; Srinivasan 2011). These results can offer us reasonable explanations for some interesting social phenomena, such as the cascade effect of feeling, opinion and belief diffusion over the whole group (Hummon and Doreian 2003), the political conflicts among international nations (Harary 1961), the social situation where polarization is frequent, such as in national elections (Srinivasan 2011), the intergroup conflict within an organization (Labianca et al. 1998), and human cooperation in some specific social activities (Traag et al. 2013). Furthermore, these social balance studies can also help us to design and develop effective social computing applications to infer the hidden attitude of one user toward another based on the observed positive and negative links (Leskovec et al. 2010b).

Traditional studies of social balance mainly focus on static state. However, real social systems are dynamic evolution and changing at each time. This has led naturally to incorporate theories of dynamic complex systems into social balance and even further develop a new dynamic theory of social balance recently (Leskovec et al. 2010a; Marvel et al. 2009, 2011; Abell and Ludwig 2009; Antal et al. 2005). Recent studies have attempted to capture how the social balance of a signed network can evolve from dynamic changes to the links’ signs over time (Terzi and Winkler 2011). A comprehensive review of these research results can provide us significant insights into understanding the evolutionary patterns of real-world social systems and finding the key impact factors of social balance. Based on these previous studies, we can further analyzing and modeling real-world social systems more practically. Yet to our investigation, existing studies have not done, especially from a dynamical perspective.

The following work is an attempt toward conducting a brief review of significant research results regarding social balance, including fundamental measures and detecting algorithms, empirical results, and social models. In order to ensure a coherent, integrated presentation of the related studies, the remainder of this paper is organized as follows: in Section 2, we firstly introduce some general definitions and theories of social balance. Section 3 presents the approaches of balance computing. In Section 4, we describe the empirical analyzing results in both traditional physical space and new emerging cyberspace. Section 5 gives us social balance models and illustrates their mechanisms. Finally, Section 6 concludes the main content of this paper and further discusses existing research problems of social balance and presents several possible solutions.

2 Concepts and properties

From the seminal studies conducted by Heider (1944, 1946) in 1940s to now, there are more than half a century. Many fundamental concepts and significant theories have been proposed and generalized with the development of social balance. In this section, we firstly describe several important concepts relevant to signed social networks. Then we further present the fundamental definitions and properties of social balance from four perspectives, including balance of nodes, triangles, complete networks and general (or arbitrary) networks.

2.1 Basic definitions

For a signed network G, we can represent it in a mathematical form: G = (V, L), where V denotes the set of vertices or nodes and L the set of links or edges. Each link l ij  ∈ L is labeled with either a sign “+” or “−”. “+” indicates that its two ending points are positive relations and “−” negative relations. We view a link labeled “+” sign as a positive link and that with “−” sign as a negative link. The positive/negative links indicate many real social relations in different perspectives such as: trust/distrust, like/dislike, praise/blame, influence/ negative influence (Facchetti et al. 2011; Szell et al. 2010; Sampson 1968). If node i connects node j directly, this kind of link between these two nodes is defined as the direct labeled link, while the connection through the third node k is the indirect labeled link. A cycle CP i in G is the closed path beginning and ending on the same node i. The sign of a cycle CP i is the product of links of the cycle. These basic symbols are presented in Table 1. Other symbols of this paper will be described in the following sections when they are firstly mentioned.

Table 1 Descriptions of basic symbols
Full size table

2.2 Balance of nodes

A signed network is balanced at one node is also known as locally balanced at this node, which can be generally defined as all cycles containing this node are positive. Mathematically, for a signed network G and one randomly selected node n i (i = 1, …, n), if the sign s c j of every cycle CP j (j = 1, …, k) encompassing node n i is larger than 0, that is s c j  > 0, then we can say that the signed network G is balanced at n i . Here, k means that there are totally k cycles passing through node n i . The local balance have been proved to be strong inter-depended on articulation nodes (Harary 1955). An articulation node n a i is defined as the key node that a well-connected signed social network G will be separated into multiple disconnected subgroups G 1, …, G m (m ≥ 2) if we remove it.

2.3 Balance of triangles

A signed social network is said to be balanced at triangles if direct and indirect labeled links has the same sign or the sign of the product of three labeled links are positive. As shown in Fig. 1, triangles in Fig. 1a and c are balanced while unbalanced in Fig. 1b and d. If a triangle shown in Fig. 1 contains three nodes i, j and k, then we will obtain that the triangle is balanced if s ij s jk s ki  = 1 while unbalanced if s ij s jk s ki  = − 1, where s ij represents the sign of link l ij . s ij is equal to 1 when l ij is positive link otherwise −1. This means that a triangle is balanced when the amount of its positive links is odd otherwise unbalanced (Davol 1959). If C + denotes the number of positive triangles and C − that of negative triangles respectively, we can further define the degree of balance B (Harary 1959) as the proportion of either positive triangles

Fig. 1
figure 1

Four fundamental undirected triads in signed networks. Red links represent positive relations, blue negative. a and c are balanced and relative stable. b and d are unbalanced and relative unstable

Full size image
$$ B={C}^{+}/\left({C}^{+}+{C}^{-}\right) $$
(1)

or negative triangles

$$ B=1-6{C}^{-}/\left(N\left(N-1\right)\left(N-2\right)\right), $$
(2)

where N is the order of the signed network. B usually ranges from 0 to 1 (Frank and Harary 1979).

2.4 Balance of complete networks

For a complete network, we can claim that it is balanced if each constituent triangle is balanced (Wasserman and Faust 1994; Heider 1944, 1946). Mathematically, if the sign s c j of each cycle CP j (j = 1, …, k) is equal to 1, we call this complete network G c is balanced while unbalanced when s c j  = − 1. Harary (1953; Cartwright and Harary 1956) and Antal et al. (2006) further found that a complete signed network G c is balanced (shown in Fig. 2) if and only if the set V of nodes in G c can be divided into two subsets X and Y, such that each pair of nodes within the same subset has a positive relation while all links between X and Y are negative. This significant property, which is the basis of some social balance theories, has been widely applied in various domains.

Fig. 2
figure 2

Illustration of judging the balance state of a complete network. a the complete network; b the balanced complete network can be cut into two subsets X and Y

Full size image

2.5 Balance of arbitrary networks

Since a large number of real-world social systems can not be represented by complete signed networks G c (Nooy 1999), we further consider the case of a social network with its edges not necessarily complete, which can be called a general or an arbitrary network G a . An arbitrary signed network G a may have three possible links: a positive link, a negative link, and a neutral link denoting the absence of a relation between the two nodes. According to existing studies, there are two equivalent ways to judge whether an arbitrary signed network G a is balanced or unbalanced. One is called local view, which mainly focuses on evaluating each triangle of the network, the other is global view, by dividing the whole network into two opposed sets (Easley and Kleinberg 2010). For a local view, an arbitrary signed network G a can be dealt by filling the missing links to form a complete signed network G c . If the complete signed network G c is balanced, we can say that the arbitrary signed network G a is balanced (as illustrated in Fig. 3). For a global view, if individuals within each cluster or subgroup have positive relations and negative between these two clusters or subgroups, we regard the arbitrary signed network G a as a balanced network (as described in Fig. 4). These concepts and properties described in this section are presented in Table 2.

Fig. 3
figure 3

Illustration of judging the balanced state of an arbitrary network from a local view. a the original arbitrary network; b the balanced complete network by filling the missing signed links (the dashed lines) into the arbitrary network, can be divided into two exclusive subgroups X and Y

Full size image
Fig. 4
figure 4

Illustration of judging the balance state of an arbitrary network from a global view. a the original arbitrary network; b the balanced arbitrary network can divided into two exclusive clusters X and Y

Full size image
Table 2 Concepts and properties
Full size table

3 Balance computing

As described in Section 2, if a signed network is balanced, the nodes either are unique clique or else can be partitioned into two mutually exclusive clusters. Several significant studies (Wasserman and Faust 1994; Easley and Kleinberg 2010; Davis 1963, 1967; Cheng et al. 2011; Kunegis et al. 2010; Harary and Kabell 1980) have further found that some signed networks can be split into more than two clusters. Social balance researchers (Morrissette et al. 1967; Cartwright and Gleason 1966; Henley et al. 1969; Norman and Roberts 1972; Taylor 1970; Stix 1974) have proposed some important criteria to detect balance status of the targeted signed networks and develop the partitioning algorithms to cut the networks into multiple exclusive but balanced clusters from various views. In this section, we firstly present existing social balance measures, which can be used to evaluate the degree of balance, and then describe the correlations between clustering and balance. We next systematically discuss and compare existing partitioning algorithms.

3.1 Measures

The balance status in a given signed network G is determined by the number of balanced or unbalanced cycles. To detect the degree of balance or unbalance, it is natural for us to consider how many cycles that have negative or positive signs. One of the simplest indices to detect the balance status B of G is given by

$$ B={C}_p/{C}_t, $$
(3)

where C p denotes the number of cycles with positive signs and C t the total number of cycles. This index can be calculated by using the adjacency matrix A of G (Cartwright and Gleason 1966) and weighting the components of this ratio by using the length of the cycles of this network (Henley et al. 1969; Norman and Roberts 1972). Harary (1959, 1960) proposed an index by considering the number of signs which must be changed when the signed network G changes its status from unbalanced to balanced. Taylor (1970) discussed and reviewed more indices to measure the degree of social balance.

The measures described above mainly focus on counting the distinct configurations of the signed edges within all possible cycles that appear in the networks. These measures would require time that is cubic to the total number of nodes. Such an algorithm is infeasible for large real-world social systems. To solve this problem, Terzi and Winkler (2011) proposed a computational algorithm to evaluate the degree of balance. In his algorithms, for a complete signed network G c , the degree of balance B c is given by

$$ {B}_c=1/2+\left({\displaystyle \sum_{i=1}^n{\lambda}_i^3}\right)/\left(4{N}_c\left({N}_c-1\right)\left({N}_c-2\right)\right), $$
(4)

where λ i denotes the eigenvalue of the adjacency matrix A c , and N c is the total number of nodes in G c . When the targeting signed network is non-complete G a , the degree of balance B a can be computed by

$$ {B}_a=\left(1+\left({\displaystyle {\sum}_{i=1}^{N_a}{\lambda}_i^3}\right)/{\displaystyle {\sum}_{i=1}^{N_a}{\mu}_i^3}\right)/2, $$
(5)

where μ i is an eigenvalue of the connectivity matrix A a of G c , and N a is the total number of nodes in G a .

Most of existing studies to judge the balance status of a given signed network must require the condition that if the signs of all cycles are positive, then the network regarded as balanced. This condition is very strict and may not be applied widely in some real-world social systems. We should further relax this condition in a very natural way. Recently, Easley and Kleinberg (2010) extended this and proved that: if at least 1 − ε of all triangles in a labeled complete graph are balanced, then there is a set consisting of at least 1 − δ of the nodes in which at least 1 − δ of all pairs are friends, where ε is any number ranging from 0 to 18 and δ is equal to \( \sqrt[3]{\varepsilon } \).

3.2 Clustering and balance

The seminal works conducted by Heider and Harary (Heider 1944, 1946; Harary 1953, 1955) have inspired many researchers (Harary 1955; Davis 1967, 1977, 1979; Doreian and Mrvar 1996; Abell 1968) from a variety of domains to generalize the original theories of social balance (Wasserman and Faust 1994; Davis 1979) and further developed many significant theories and approaches. These theories can provide for us to better understand the inherent mechanisms and key properties of signed networks.

One of these existing significant studies is conducted by David during 1960s–1970s (Davis 1967, 1977, 1979), who proposed the concept of clustering in a signed social network. Clustering defined by David is partition of the node set of a given signed network into k subsets, such that each pair of nodes in the same subset has a positive relation and a negative relation exists between each pair of nodes from different subsets. The subsets derived from the clustering are called clusters (Wasserman and Faust 1994). After some significant empirical analysis, Davis (1967) further found that a signed network has a clustering or is clusterable if and only if it contains no cycle with exactly one negative link.

Another significant and interesting studies are performed by Harary (1955) and Doreian and Mrvar (1996). Their studies mainly focused on exploring the correlation between k-balanced at one node and k-clusters in a given signed network. A signed social network is defined to be k-balanced if its cycles length not exceeding k are positive (Cartwright and Harary 1956). Harary (1955) proved that a signed network G is k-balanced at node n i if and only if k-clusters containing n i are balanced. Doreian and Mrvar (1996) found that a signed network G is k-balanced if and only if it contains no semicycles with exactly one negative link. When k = 2, it is traditional balance problem, while k > 2 corresponding to generalized balance.

Most of theories and approaches described above are just suitable for complete signed networks. This can not be applied directly to analyze the real-world social systems. More generalized approaches should be further developed to understand the dynamics patterns of signed networks with some links between nodes within clusters absented. Abell (1968) gave some useful approaches to judge the relation between k-balance and k-clusters for incomplete and directed signed networks. He proved that an incomplete, affective, symmetric structure with k-clusters is balanced if and only if there are 2k − 1 ways to divide the node set of a given signed network such that: all intra-cluster links are positive or unconnected and all inter-cluster links are negative or unconnected.

3.3 Partitioning algorithms

Partitioning or clustering based on social balance has proven useful for representing the structure of signed social networks (Doreian and Mrvar 2009). Existing partitioning algorithms can be classified into two types: edge-based partitioning and node-based partitioning. Edge-based partitioning algorithms aim to cut the resulting network into multiple clusters by selecting a set of edges to be removed. While nodes often serve as bridges in most of existing node-based partitioning algorithms.

3.3.1 Edge-based partitioning algorithms

The problem of social balance in edge-based partitioning algorithms is often solved by considering the adjacency matrix A of the given signed network G, where the entries of matrix A represent the values of signed links. Significant partitioning algorithms (Terzi and Winkler 2011; Kunegis et al. 2010; Doreian and Mrvar 1996, 2009; Wu et al. 2011; Gill 1981; Doreian and Krackhardt 2001) have been developed for different applicable purposes. A common place of existing studies is that these proposed algorithms usually first select some edges as bridges and then remove them in such a way that the resulting social network can be partitioned into multiple subgroups (Kim and Candan 2012). The differences among these algorithms are the definitions and computational methods of cut functions. The cut function C D proposed by Doreian et al. (Doreian and Mrvar 1996, 2009; Doreian and Krackhardt 2001) has the following form,

$$ {C}_D=\alpha {N}_n+\left(1-\alpha \right){N}_P, $$
(6)

where N n is the total number of negative links within subgroups, N P represents the total number of positive links between subgroups, and the tunable parameter α ranges from 0 to1. While Kunegis et al. (2010) recently developed another form of cut function C K , which is defined by,

$$ {C}_K=2\cdot {C}_K^{+}\left(X,Y\right)+{C}_K^{-}\left(X,X\right)+{C}_K^{-}\left(X,Y\right). $$
(7)

In this form, C + K is given by

$$ {C}_K^{+}={\displaystyle {\sum}_{i\in X,j\in Y}{A}_{ij}^{+}} $$
(8)

and C − K is computed as follow,

$$ {C}_K^{-}={\displaystyle {\sum}_{i\in X,j\in Y}{A}_{ij}^{-}}. $$
(9)

A + indicates the adjacency matrix containing only positive links and A − represents the matrix just encompassing negative links. By investigating the spectral properties of the Laplacian and minimizing the cut function C K , we can partition the original network G into two subgroups X and Y, where few positive links connecting subgroup X and Y , and little negative links within each subgroup.

These partitioning approaches help us understand the overall amount of frustration of the network, but they do not provide any information on which links or triangles remain unbalanced. By the gauge transformation theory (Toulouse 1977) in the spin glass literature, Iacono et al. (2010) introduced a heuristic algorithm for ground-state search on sign networks and utilized it to analyze biological networks. Based on this work, Facchetti et al. (2011) further improved this algorithm and generalized it to compute the global social balance in large-scale signed social networks. In this algorithm, they proposed an energy function E F , which is given by

$$ {E}_F={\displaystyle {\sum}_{\left(i,j\right)}\left(1-{l}_{ij}{s}_i{s}_j\right)}/2, $$
(10)

where l ij  ∈ {±1} is the edge or link between nodes i and j, and s i  ∈ {±1}(i = 1, …, N) is the sign of node i. The approach aims to find a signature matrix T F and then minimize the number of negative signs in T F AT F . Here, T F is a change of sign through cut the set of the signed network and A denotes its adjacency matrix. The signed network is balanced when all terms in (10) is simultaneously equal to zero. Similarly, Axelrod and Bennett (1993) have also given us another energy function for signed networks. The energy function E A is defined as

$$ {E}_A={\displaystyle {\sum}_{i,j}{s}_i^N{s}_j^N{p}_{ij}{d}_{ij}}. $$
(11)

s N i in (11) denotes each node’s size and p ij presents its propensity to be close to other nodes j, d ij  = 1 if node i and node j belong to different cliques and d ij  = 0 otherwise. All of these algorithms described above aim to find a minimized energy value and divide the signed network G into two closed-connected subgroups or cliques.

3.3.2 Node-based partitioning algorithms

In node-based partitioning algorithms, the cut passes through the nodes of the graph and each node serves as the exit- and the entry-points of the respective partitions (Kim and Candan 2012). A node-based partitioning algorithm would partition a given signed network into two or more clusters/components by cutting the minimum number of nodes (Black 2004).

Since the node-cut problem is in its general form NP-hard, various approximation algorithms and heuristics have been developed to tackle the problem. Feige et al. (2005) proposed a balance criterion. This criterion can be used to evaluate the goodness of a node-based partitioning algorithm. Biha and Meurs (2011) studied the node separator problem from the polyhedral point of view and provided an exact solution to the node separator problem, by representing the underlying problem in terms of constraints and solving the resulting mixed-integer programming.

Another significant challenge in node-based partitioning is ensuring the balance of the resulting partitions while simultaneously minimizing the number of nodes that are cut. To overcome this problem, Kim and Candan (Kim and Candan 2012) proposed a node-based network partitioning algorithm that leverages these structurally-balancing node-cuts. The algorithm firstly identifies a set of balance nodes and then hierarchically partitioned by recursive application of social-balanced cuts. They showed how to locate and used these balance nodes to obtain a balanced node-cut of a signed network G. In future work, we can focus on finding dominant balance nodes without using eigen decomposition, which can be a bottleneck in running time, and detecting k balance nodes directly rather than generalizing bisection.

4 Empirical studies

Empirical studies based on data coming from observations of real social systems are very important not only for the identification of new phenomena or surprising features, but also for the validation of theoretical hypothesis (Castellano et al. 2009; Morrissette et al. 1966). Although massive papers have provided for us significant insights into understanding of social dynamics in our physical world, the approaches of data collection in these studies are stilled criticized since it is difficult to affirm some specific social relations between two individuals. Those relations based on sentiments, trust or friendship are always influenced by the cultural, political and economic factors around individuals (Costa et al. 2011). These results in a large number of social dynamic studies always remain on the level of theoretical hypothesis.

To solve this problem, researchers then turn to design scientific questionnaires, conduct reasonable field interviews and even compare these surveys manually to obtain more reliable empirical data. However, these approaches need a lot of time and resources to deliver statistically meaningful assertions, and meanwhile may introduce well-known biases (Carrington et al. 2005; Costa et al. 2011). Moreover, regarding data acquisition is essential not only to record the social behavior of individual humans but also the simultaneous state of their surroundings (Szell and Thurner 2010). As such, traditional empirical studies have been limited to examining small, well-bounded populations, involving a small number of snapshots of interaction patterns (Lazer et al. 2009; Zheng et al. 2012).

These limitations presented above might appear in a radically more positive light with the emergence and rapid proliferation of social media. In those Web 2.0 social computing applications, individuals can express freely their feelings and communicate with each other conveniently. The availability of unprecedented huge new datasets has spurred thorough empirical characterization. Virtual social networks in cyberspace can provide a significant statistical sample and possibly unbiased features of the social relations (Costa et al. 2011). Table 3 lists the basic approaches of data collections.

Table 3 Approaches of data collection
Full size table

The following section will focus on describing the existing significant empirical studies on social balance in both physical world and cyberspace. We also in this paper refer to the offline and online social systems as those social systems in physical world and cyberspace respectively. According to the differences of research objects, we classified the existing empirical studies on offline social systems results into three levels, including the individual-level, the group-level and the nation-level. The Individual-level mainly focuses on examining the attitude and perception behavior of single individuals. The group-level generally considers the relations within dyads and groups, and the national level usually studies the dynamics of national relations and political crisis using theory of social balance. For these empirical studies on online social systems, according to the types of relations between two entities of these systems, we further describe existing results from two basic perspectives, which encompass single-dimension and multi-dimension. Table 4 gives the fundamental classification of existing empirical studies. Part A in this section will give existing empirical studies of offline social systems and Part B will present that of online ones.

Table 4 Classification of existing empirical studies
Full size table

4.1 Empirical studies in physical world

The original social balance approach proposed by Heider (1944, 1946) was often applied to analyze the social behavior of single individuals. This approach then was further generalized to analyze the evolution process of relations within dyads and larger groups in our physical world (Heider 1958; Miller and Geller 1972; King 1964). Newcomb (1981) analyzed a population with 17 male students who were recruited as total strangers to one another. This population is consisted of one balanced and one unbalanced subgroups. By empirical analysis on this dataset, he found that previously reported balance within a group may be attributable to a single subgroup and inferred the certain conditions under which the balance of one social group is likely to occur. Newcomb’s efforts illustrate that Heider’s balance theory can be expanded interpersonally in such ways that it can be utilized to explain the balanced states within subgroups of a population. The findings conducted by Taylor (1970) show that small groups such as children in an education setting usually exhibit tendencies towards balance. Auster (1980) and Harary (1966) took tales and drama as cases and found an interesting phenomenon: many plays written by some writers always contain some unbalanced episodes but end in balance. They also obtained that the narratives of these stories can be well predicted by balance theory.

National relationship is another favorite case studied by social balance researchers. Nodes in these studies usually represent nations, states or other administrative regions, and the sign “+” and “−” indicate positive and negative relations respectively. Based on the theory of social balance, several studies have provided for us significant insights into understanding the behavior of different nations during various international crises (Easley and Kleinberg 2010; McDonald and Rosecrance 1985). Moore (1978, 1979) analyzed the conflict over Bangladesh’s separation from Pakistan in 1972. He found that the behavior of the United State, China, India and Pakistan at this period could be deduced from the relations between these nations. Antal et al. (2006) explored that the evolution of the major relations changes between the protagonists of the World War I from 1872 to 1907. This study states the fact that, when social balance is natural outcome, it is not necessarily a good thing. Harary (1961) also described the distinction between states of balance and unbalance in the international relations by a structural analysis of the situation in the Middle East in 1956. These significant empirical studies are depicted in Fig. 5.

Fig. 5
figure 5

Examples of the evolution of alliances in the Middle East in 1956, where nodes E, A, B, F, I, D, U and S stand for Egypt, the other Arab nations except Egypt, the Great Britain, France, Israel, India, USA and USSR respectively (Harary 1961). The initial network as displayed in (a) is consisted of these eight entities and relations between them. This network is balanced since it can be cut into two exclusive clusters. One cluster includes D, I and S and the other encompasses A, B, E, F and U. However, two positive links l SE and l SA were then added due to bartering Czech and Russian armaments for Egyptian cotton. The resulting network as shown in (b) is unbalanced since the cycles ESU and BES are negative. Then the sign of l BE was changed from to negative, and that of l DS was changed from negative to positive. l EF and l UE were then added and l BI and l UI were removed from this network since Egypt nationalized the Suez Canal. This new network as depicted in (c) is balanced and relative stable if no more external stimuli. Yet the subsequent military attacks on E by B, F and I as well as the induced new positive link l BI between B and I led the network evolved into the new one as described in (d). Though it seems balanced in the network, U in this situation is not very pleasant since the other coalition of U finds that A and E, which were controlled by U, now stand together with S, which is the opponent of U. Therefore, American then denunciated the attack on E by B, F, and I. This leads that the signs of cycles FSU and BDU changed from positive to negative. The network in (d) then further evolved into the new network as displayed in (e). As the network changing, the cycle BDU becomes positive while DSU is negative as shown in (f). From the unbalance triangle DSU in (f), we can further infer that, in this situation, Indian would feel tensional and consider to change the sign of the link l DS from positive to negative, which is precisely confirmed by several political events happened in 1957

Full size image

4.2 Empirical studies in cyberspace

The data available from social media websites in cyberspace allow the nature of one-to-one interactions between individuals to be identified. Many significant characteristics of the corresponding signed networks can be deeply studied at a larger scale (Facchetti et al. 2011; Burke and Kraut 2008; Brzozowski et al. 2008; DuBois et al. 2011; Romero et al. 2011; Li et al. 2013). These features can provide much solid evidence for us to validate some classical theories of social balance. Kunegis et al. (2009) collected data from one famous news platform called Slashdot Zoo and constructed a virtual social network. Their analysis was carried out from three different levels, including global level, node level and link level. They found that the social network of Slashdot Zoo displays multiplicative transitivity, which means that the famous theoretical balance property of the enemy of my enemy is my friend can be utilized to explain the user interactive behavior in some social media sites.

Trust and distrust may be one of the existing most challenging problems in traditional social dynamics research. The lack of reliable data about trustful relations in physical world drives the studies to concentrate on virtual trust relations in cyberspace. Researchers recently have attempted to explore the features of trust/distrust networks and develop several significant approaches to solve this problem. DuBois et al. (2011) presented a method for computing both trust and distrust. This work was done by combining an inference algorithm that relies on a probabilistic interpretation of trust based on random graphs with a modified spring-embedding algorithm. The authors approved that their algorithm can correctly classify hidden trust edges as positive or negative with high accuracy. These results may be useful in a wide range of social web applications where trust is important to user behavior and satisfaction. Guha et al. (2004) proposed a framework of trust propagation schemes and evaluate the schemes on a large trust network of Epinions, consisting of 131,829 nodes and 841,372 links, each labeled either trust or distrust. They showed that a small number of expressed trusts/distrust per person allow us to predict trust between any two people in the system with high accuracy. Similar results have also been founded in other researchers (Leskovec et al. 2010b).

Leskovec et al. (2010a) further developed the original research idea of Guha et al. (2004) into a theory of status. In this theory, a positive directed link l + ij originating from i to j represents i considers j has higher status in his/her belief, while a negative directed link l − ij indicates that j has lower status. By constructing three types of networks based on three online datasets: Epinions, Slashdot, and Wikipedia, Leskovec et al. (2010a) found that the networks of Epinions and Slashdot can shed light on the main characteristics of these websites, while the network of Wikipedia is not described well.

These studies presented above put much emphasis on analyzing the characteristics of single-dimensional social networks, however, many multidimensional attributes of real-world social systems have largely been ignored. Based on the dataset of a massive multiplayer online game consisting of about 300,000 users, Szell et al. (2010; Szell and Thurner 2010) recently attempted to construct a multi-relational large social network. They extracted six types of relations between these users. Three of them are positive, including friendship, communication and trade. The other three, encompassing enmity, attack and bounty, are negative. By analyzing the cumulative in-degree and out-degree distributions of this multi-relational network, they found that the topological properties of social networks are correlated with the nature of their links. Ignoring this will cause much useful information lost. These empirical results are depicted in Fig. 6. Szell et al. (2010; Szell and Thurner 2010) in their studies also proved that positive links exhibit higher reciprocity and clustering coefficients than negative ones. A detailed dynamical analysis of their empirical data further demonstrates that the potential driving force of changes happening in the network evolutionary process is the creation of new positive and negative links, not due to switching from existing positive links to negative ones.

Fig. 6
figure 6

Cumulative in-degree and out-degree distributions for six signed social networks (Szell et al. 2010). The nodes of these six signed social networks denote the players of the massive multiplayer online game, while the links of these networks represent six different types of interactions between these online players. These six different types of interactions are: a Friendship, b Communication, c Trade, d Enmity, e Attack, and f Bounty. The cumulative distributions of negative links, listed in the right column ((d), (e) and (f)), follow power laws with cutoffs, while these phenomena are absent for positive ones in left column ((a), (b) and (c))

Full size image

5 Dynamics models

Since empirical studies always involve uncertainty caused by measurement errors, imperfect observation or sampling, it requires us to develop social balance models to explore the underlying mechanisms of social systems (Frank and Harary 1979). Traditional researchers often focused on classifying balanced stable states of networks when relationships are static. The models in these studies proposed by some researchers are originally used to provide logical explanations for the changes of some specific networks to some extent and further reason how the unbalanced triangles of the aimed networks evolve into the balanced ones from one determined snapshot to another one. In this paper, we regard them as static models due to their underlying properties and mechanisms. However, most of real-world social systems is dynamic and evolutionary (Heider 1946; Cartwright and Harary 1956; Zheng et al. 2011a) persistently. Therefore, these existing static models can not work well. This situation has led a large number of researchers naturally to develop dynamics models (Marvel et al. 2011; Istrate 2009), which usually examine the signs of links of the given networks at each time step during the whole process. According to existing studies, we classify existing dynamics models into two basic types: one type of models can be called discrete-time dynamics models and the other are continuous-time dynamics models. Table 5 presents the general framework of existing social balance models. Due to several previous studies (Wasserman and Faust 1994; Heider 1944, 1946; Cartwright and Harary 1956; Frank and Harary 1979; Davis 1963) have describe these static models, the reminder of this section will mainly focus on describing and comparing the fundamental mechanisms of these dynamic models.

Table 5 General framework of existing social balance models
Full size table

5.1 Discrete-time dynamics models

The first exploration of discrete-time dynamics models was conducted by Antal et al. (2005, 2006). These discrete-time dynamics models mainly consider two dynamical update rules: one is called local triad dynamics (LTD) and the other is constrained triad dynamics (CTD).

The basic idea of LTD rules shown in Fig. 7 can be described as three steps. Firstly, we pick up a triad randomly and judge whether the triad is balanced. If the triad contains only one negative link as shown in Fig. 7a, we will change the negative link into a positive link with probability p and change a positive link into a negative link with probability 1 − p. While, if the triad contains three negative links as depicted in Fig. 7b, in the third step, we can change a negative link into a positive link with probability p = 1.

Fig. 7
figure 7

An update step under the rule of local triad dynamics from ref. (Antal et al. 2005, 2006). a Is suitable for the triad containing only one negative link and b for the triad having three negative links respectively

Full size image

In the CTD rules, similar to that of LTD, a signed link is also selected randomly from an imbalanced triad. If the number of imbalanced triads decreases in the whole network, the sign of the selected link will be changed. While the number of imbalanced triads is conserved, the sign of the selected link will be changed with probability 1/2. The basic mechanism of CTD is similar to that of an Ising model with a three-spin interaction between the links of a triad (Glauber 1963; Binder and Young 1986). This mechanism can be utilized to mimic the dynamical process of one person who examines his/her personal social circle before this person decides to change one of his/her social relations. Under the CTD rules, it has been proved that a social network arrives at one balanced state in a time scaling with ln N (Antal et al. 2005, 2006), where N are the whole size of the network.

Based on these studies conducted by Antal et al. (2005, 2006), Marvel et al. (2009) further modeled a fully-connected signed social network on N nodes. In this model, each link is labeled with either a positive or negative sign according to the feelings existing among nodes. Similar to our description in Section 2, the product of the link signs in this model is positive for a balanced triangle and negative for an unbalanced triangle. In their study, they further proposed a quantity U to evaluate the potential energy of a social network. The quantity U is defined as

$$ U=-6\left({\displaystyle \sum {s}_{ij}{s}_{jk}{s}_{ik}}\right)/\left(N\left(N-1\right)\left(N-2\right)\right). $$
(12)

According to the proposed measure, the configuration with all node pairs owning positive signs has the lowest potential energy U = − 1.

As described above, Antal et al. (2005, 2006) and Marvel et al. (2009) mainly focused on the sequential sign change process on a fixed network. Van De Rijt (2011) further considered the best response dynamics and proposed one new model call the best-response model. Following the basic idea of this model, if we denote m > 0 as the maximum number of signs one individual can change in his/her ego-network at any step, then S i  ⊆ X i for which

$$ \left|\left({F}_i\backslash {S}_i\right)\cup \left({S}_i\backslash {F}_i\right)\right|\le m $$
(13)

is a strategy on network G = (N,X,F) for node i, where N = {1,2, …,n} represents the set of nodes, X is the set of existing links between these nodes, F ⊆ X means the subset encompassing positive links. Strategy S ∗ i can be considered as the best response to F if this strategy has the maximum utility value comparing with all other possible strategies S i . The network produced by Van’s model is proved to be stable if F i is a best response to F for all i, while the networks of Antal et al. (2005, 2006) and Marvel et al. (2009) are stable only under the special conditions m = 1 and X = X N, where X N denotes the set of all possible links in the network.

Radicchi et al. (2007) also generalized the models proposed by Antal et al. (2005) and applied their new model to k-cycle dynamics for arbitrary integer k. On the other hand, they also developed the random local algorithm to a p-random local algorithm. By investigating the convergence time of a discrete dynamical system on several classes of networks, Istrate (2008) developed a model for general networks, which aims to provide the connection between the triad dynamics and a generalization of nondeterministic dynamical systems to hyper-graphs. This dynamics model can help us to characterize the recurrent states in general networks where each link belongs to no more than two triangles. Abell and Ludwig (2007, 2009) proposed another type of models. In these models, they firstly assumed that the nodes of a social network are subsequently linked with each other. At each step, one positive or negative link is formed between one pair of unconnected nodes randomly. The probability of assigning the positive or negative signs depends on an index α, which ranges from −1 to 1. The index α can help us better understand the specific evolutionary processes of social network in which node pairs have different propensities. The probability p p of one positive link being created in these models is computed by

$$ {p}_p=\left(1+\alpha \right)/2, $$
(14)

and a negative link p n is given by

$$ {p}_n=\left(1-\alpha \right)/2. $$
(15)

We can further obtain that the likelihood p tb of one completed triangle with balanced state is (1 + α 3)/2 and that p tu of one unbalanced triangle is (1 − α 3)/2.

5.2 Continuous-time dynamics models

Generally, one balanced network is a stable point for these discrete-time dynamics presented above. However, in these models, especially in constrained triad dynamics models, the number of imbalanced triads can not increase in an update event, and the final state can either be balanced or jammed (Marvel et al. 2009; Antal et al. 2005). This problem has driven a number of social balance researchers (Srinivasan 2011; Traag et al. 2013; Marvel et al. 2011; Kulakowski et al. 2005; Altafini 2012; Pelino and Maimone 2012; Summers and Shames 2013; Singh et al. 2013) to develop continuous-time dynamics models to identify and analyze the underlying mechanisms of a simple network evolving from generic initial configurations to a large balanced network.

In our real-world social systems, individuals usually do not count the balanced triads in the whole network. Based on this interesting social phenomenon, Kułakowski et al. (2005) constructed a model by considering variations on the following basic differential equations:

$$ d{x}_{ij}/ dt={\displaystyle \sum_k{x}_{ik}{x}_{kj}}, $$
(16)

where x ij denotes the strength of the positive or negative link between node i and j. In these equations, the same sign of x ik and x kj will drive the value of x ij to the positive direction, and vice versa. The dynamics is local: each link only determined by the state of triads containing node i and j. From this model, we can obtain the evolving process in a simple network with just three nodes. However, it is still an open problem to characterize the structure of a larger social systems which starting from an initial value to a balanced state.

To resolve this problem, Marvel et al. (2011) extended this analytical study to N × N continuous-time dynamics and compared its predictions with empirical social network data. They found that this model can evolve in finite time from a randomly selected initial matrix to a balanced matrix with a probability converging to 1. A closed-form expression for this balanced matrix as a function of the initial conditions can be obtained from this model. This indicates that the initial number of positive links in large social networks can determine whether they will end with conflict or harmony. Srinivasan (2011) further analyzed the properties of this model and uncovered the basic mechanisms that local balancing influenced global structure in social networks. Pelino and Maimone (2012) proposed another dynamics models using the properties of isospectral flows. They considered the strength of links in signed social networks and numerical indices to positive or negative links among nodes. These models can be utilized to simulate realistic evolving conflicts.

In order to demonstrate how social relationships between individuals influence their opinions in signed social networks, Altafini (2012) recently proposed another dynamics model, by using the differential equation

$$ dx/ dt=f(x), $$
(17)

where x ∈ R n is the vector of opinions of n persons and the function f(⋅) describes the forming process of opinions. This model aims to describe the influence of node j over node i by the partial derivative

$$ {F}_{ij}(x)=\frac{\partial {f}_i(x)}{\partial {x}_j}. $$
(18)

From this equation, we can obtain the formal Jacobian matrix of the social system

$$ F(x)={\left[\frac{\partial {f}_i(x)}{\partial {x}_j}\right]}_{i,j=1,\dots, N}. $$
(19)

Under the hypothesis that the opinions of friends exert a positive influence and those of enemies a negative one, Altafini (2012) obtained that monotone dynamical social systems can be utilized to describe the dynamic forming process of opinions in structurally balanced communities.

6 Discussions

With this brief review, we made an attempt to summarize the scientific activities in the interesting field of social balance. Our efforts aim to review what has been done so far in this rapidly evolving area. The fundamental concepts and properties of social balance were firstly introduced in this paper. Then we presented the approaches of balance computing and significant empirical studies as well as dynamics models. These studies can provide for us unquestionable evidences about the importance and dynamics of social balance domain. As we known, the success of one area always depends not only on their theoretical contributions, but also on their potential applications to real-world problems (Costa et al. 2011). The area of social balance research has already constructed a general and powerful theoretical framework and provided for us many significant dynamics models to uncover and mimic the evolutionary mechanisms of real-world social systems well, as we presented above in Section 2, 3, 4 and 5. This holds tremendous potential for future applications.

However, there are still some places which should be further improved in this area: 1) The current social balance measures usually have high computational complexity and hence some of them just stay at the level of theoretical analysis but can not be applicable; 2) As many real-world social networks have directed and weighted links, we should further generalize the existing theory of social balance to directed and weighted signed networks. This method can help us obtain more useful information about social systems and may provide for us important insights into understanding the dynamics of such systems; 3) Most of these existing dynamics models concerning the issue of social balance are only suitable for mimicking the social process of some specific social phenomena under several ideal hypotheses. Few existing models can work well and provide perfect explanations for general real-world social systems. As such, it is still an open problem for us to develop more applicable mathematical models which can be combined with the perspectives in the empirical body of literature (Marvel et al. 2011); 4) More issues concerning social balance should be argued and more significant ideas should be also proposed from other fields besides social psychology. Though those opinions and approaches may be conflict to some extent due to different experiences and perspectives, they can help enrich the theory of social balance.

In the following part of this section, we will mainly focus on discussing three significant issues, including empirical studies on the emerging systems called Cyber-Physical-Social Systems, competitive and cooperative models, and evaluation and computational experiments. We will also present some potential research directions in the future.

6.1 Empirical studies on cyber-physical-social systems

Existing empirical studies have paid more attentions on traditional offline social systems using the data of offline questionnaire and online social systems utilizing the online web log data obtained from social media. However, as we known, some online social behaviors of users may be influenced by their offline social activities. On the other hand, many individuals’ offline actions could also be affected by their online social interactions. If those offline or online social systems are analyzed separately, it is most probable for us to obtain a biased perception of user’s behaviors, especially their interaction behaviors. Furthermore, few existing empirical studies in this field have conducted deeply analysis on dynamical behaviors at a large scale. The potential reason is that, to date, it is difficult for us to obtain this type of data quickly and accurately.

This problem may be solved efficiently as the rapid growth of mobile communication and web-based technologies, especially these recent emerging technologies such as the Internet of things and cloud computing technologies (Eagle et al. 2009; Fang et al. 2013; Jung et al. 2012; Martens and Teuteberg 2012; Mazhelis and Tyrväinen 2012). These technologies have created an overwhelming demand for the rapid development and application of Cyber-Physical-Social Systems (CPSS) (Fei-Yue 2010), which could potentially integrate the cyber-social systems and physical-social systems together. These Cyber-Physical-Social Systems can encompass a holistic treatment of information, and knowledge from the Cyber-Physical-Social spaces and offer massive historical data concerning social interactions of users (Sheth et al. 2013). These CPSS data can provide for us a huge number of significant evidences to gasp and understand human perceptions and individuals’ attitudes more precisely than ever before.

6.2 Competitive and cooperative models

The current approaches proposed by social balance researchers so far mainly focus on representing and modeling very simple interaction behaviors of entities of social systems. Many real existing significant social factors around these entities have been ignored. Many real-world social behaviors involve the interaction of multiple organisms in a population, and the success of any one of these organisms depends on how its behavior interacts with that of others (Easley and Kleinberg 2010; Axelrod et al. 1995). Especially, within an organization, some relations between individuals are competitive while some others are cooperative, or even these two types of relations exist in the same pair of individuals. Actually, we can present these relations using the construction method of signed networks, where positive and negative links have a natural interpretation in the light of cooperation and competition: positive links indicate cooperation and negative links competition (Traag et al. 2013). However, existing dynamics models have not considered the competitive and cooperative behavior yet, which leads that most of existing theoretical models are not applicable. This is then also a natural motivation to develop more reasonable and applicable social balance dynamics models by considering the competitive and cooperative behaviors of entities within an organization and some important international political and economical activities.

Along this direction, we can utilize the famous Game theory (Malekzadeh et al. 2011; Gnyawali and Madhavan 2001; Kakade et al. 2005; Daniel et al. 2008; Jackson and Zenou 2014; Galeotti et al. 2010; Abramson and Kuperman 2001), especially the evolutionary game theory (Hanaki et al. 2007; Smith and Price 1973; Osborne 2003; Jackson 1996, 2008; Szabó and Fáth 2007; Ba et al. 2000), which is designed to address the situations in which individuals’ decisions depend not only on how they choose among options, but also on other actions made by the persons with whom they interact (Easley and Kleinberg 2010), to construct competitive and cooperative models. We can also integrate some fundamental theories of multiple disciplines, such as organizational behavior (McPherson et al. 1992; Kogan and Tagiuri 1958), economics (Easley and Kleinberg 2010; Zenou 2012), sociology (Friedkin 2004; Viktorov 2007), computer science (Tang et al. 2012; Yang et al. 2007) and statistical physics (Castellano et al. 2009), to further conduct significant analytical studies, which can help us obtain more realistic and operational results from the targeted social systems and predict their overall trends.

6.3 Evaluation and computational experiments

Most of existing studies on social balance are often insufficient to discriminate among different modeling schemes and computational measures. Therefore, in the future, more efforts can be made on developing efficient measures and evaluation approaches. Several researchers have attempted to conduct some studies along this direction. Using the simulation approach of Monte Carlo, Wang and Thorngate (2003) and Kulakowski (2007) described two simulations and found that individual decisions can exclusively guide the balancing process. Notsu et al. (2006, 2010) simulate virtual societies under several communication network conditions among agents using multi-agent systems, whose agents are based on cognitive balance, to get clues for understanding the feelings, attitudes and beliefs of modern society. However, these traditional computer simulations may not be valuable and applicable when examining policies dealing with the matters of real-world complex social activities (Wang et al. 2007; Morrissette 1958; Zheng et al. 2011b) since the rules of most of existing computational simulations are simple and predetermined. Therefore, these approaches may not be used to discover more hidden or unobservable key factors of complex social systems well.

Motivated by these considerations presented above, many social computing researchers have further contributed more interesting ideas. Wang et al. (2007; Wang 2004, 2007) recently proposed the approach of computational experiments with artificial systems and more sophisticated simulation techniques, such as the self-emergence technologies based on multi-agent modeling approaches. Zheng et.al. (2011a, b, 2012; Cui et al. 2013b) further gave a general theoretical framework of computational experiments with a feedback mechanism. These approaches can be triggered between the theoretical and the experimental activities in order to make the results robust, well understood and concrete.