Phase Transition In Dynamic Networks
In signed networks with simultaneous friendly/hostile interactions, there is a general tendencyto a global balance. Although, balance represents a state of the network with lack of contentioussituations, real networks have always tensions. Contrary to the impression, networks transition fromunbalanced and tension state to a steady state is not smooth, it is involved abrupt change. In thiswork, we generalize the balance dynamics in non zero temperatures for updating links in imbalancedtriads. We present an analytic mean-field solution which is a suitable approximation in the limitof large network size. Also, we introduce a new link-based model for the evolution of network as afunction of temperature. Our analyses show fully connected network undergoes a first order phasetransition from an unbalanced state to stability with a critical temperature Tc. Where in the caseof T > Tc there is no chance to reach to the balance state.
Introduction
Signed social networks are those with both positive and negative edge weights used to capture the valence as wellas the strength of dyadic relationships, such as friendship/ally and animosity/enemy. By far the dominant method toanalyze such networks is balance theory (also called structural balance theory). Originally proposed by Heider [1] asan explanation for attitude change, and formally generalized for graphs by Cartwright and Harary [2], balance theoryhas been refined and applied to a variety of social, economic, ecologic and political scenarios [310]. Balance theoryprovides a means to capture a system of such relationships and measure the degree to which it is balanced/stable orfrustrated/unstable. Here we provide a further expansion of balance theory utilizing methods from Boltzmann-Gibbsstatistical physics to show that after assigning energy levels to unique configurations of triads in signed graphs, wecan extract the characteristic strength parameters of their interactions.
The original formulation was concerned only with whether graphs were balanced or not, where balanced meantthat all cycles among all nodes contained only an even number of negative edges [2]. Later work [11] argued thatonly triads of nodes (i. e. , connected triples, 3-cycles) were relevant for most social science applications of balancetheory, and also showed that the proportion of unbalanced n-cycles and 3-cycles increase monotonically with eachother. Thus the triadic version has become dominant (although see [12] and [13] for alternate measures of balance). Balanced configurations are still those with an even number of negative edges; specifically we capture the ideas ofThe enemy of my enemy is my friend [+ ] and The friend of my friend is also my friend [+ + +] as balanced/stablesituations. The two other types of signed triadic configurations ([+ + ] and [ ]) are considered unstable and give riseto frustration in the network. Because this was developed as a theory of attitude change, the frustrated triads areconsidered to be posed to change to increase systemic balance.
As a further refinement, social scientists since [14] have observed that the two types of balanced triads are notequally balanced, and the two types of frustration are not equally frustrated. If we consider the classic version abovethe strict rule for balance, the loose rule for balance rates [+ + +] as more strongly balanced than [+ ], and [+ + ]is more strongly frustrated than [ ]. This breakdown reflects the observation that while triple negative triads are notstable, they do not actually inject much frustration into the system. Likewise, although [+ ] is balanced, a systemcontaining entirely triple positive triads is more stable. Heiders original hypothesis was that a network of signed relations would tend to evolve towards a more balancedsituation, eventually having solely triple positive balanced triadic relationships (often referred to as utopia). Severalsimulation models explore the formal conditions for this outcome [2, 1518], but empirical studies reveal significantdeviations. The validity of SBT has been tested on a variety of social and political relationships, such as politicalrelations between countries [3, 6, 7]. Pioneering work in applying physics-based models inspired by the Ising model to signed networks can be foundin [Newman] and [21]. In these works, the mean field approximation is used as accurate solution. We develop analternate approach based on balance theory.
Model and Material
In this section, we provide a statistical physics framework for the study of structural balance theory. Most of theprevious works were devoted to analyzing dynamics of networks with focus on changing the link values or structure tounderstand tendencies towards or away from balance. Antal et al. [15] proposed a model in which randomly selectedlinks change with the aim of balancing unbalanced triads. In this model, dubbed local triad dynamics, they foundthat a finite network relaxes into an equilibrium state with balanced triads. Abell and Ludwig explore the trade offbetween increasing the number of positive links and the nodes tolerance to imbalance. Variations in these parametersprovided evidence for three behavioral phases, including features resembling self-organized criticality [16]. Gawronskiet al. use continuous link values to reformulate balance theory in terms of dynamical equations. They show that,given certain constraints, in a fully connected network the system converges to Heiders balanced state (or utopia)after a finite number of interactions [17].
A formulation of balance theory in terms of energy levels using only the strong rule was proposed by Redner [8],but its focus was on explaining why the systems do not necessarily evolve to lower frustration. They did this byinvestigating the landscape of possible networks and found so-called jammed states that impede the total relaxationof the system. Although balance theory includes a tendency toward reduced frustration, we are also interested invarious systems tolerance levels of systemic frustration. We propose a framework with modify the energy of systemby adding temperature ”T” term which gives the Balance theory an approximate thermodynamic structure; This canbe seen through fluctuations in quantities such as the average number of triads of a particular kind around the mean. Now,we apply quantitative methods, based on statistical physics, to study the integration of social networks,focusing on the triadic relations. Let’s first specify the variables involved in the system(model). A social network,is represented by a graph (N, g), which consists of a set of nodes and edges between them. the Hamiltonian of thisnetwork on Balance theory is: H =∑i,j,kSi,jSj,kSk,i. (1)Each of these edges must have values Sij ∈ {+1,−1} which show the relation between them as a friendship orenemy.
As we are in Balance Theory, our unit of analysis is two types of triads (Balanced, Unbalanced), presented inFig. 1. Figure 1: the four different types of structural balance triadsA micro state of such a network is uniquely specified by the complete set of sij values (together with any relevantnode attributes). We must first estimate the probabilities of each type of triad: {pA, pB, pc, pD}. Because these typesconstitute a partition of triadic micro-states, we can divide the number of each type mi by the total number of triadic3relations in the network M to produce proportions. We make the simplifying assumption that the probabilities canbe estimated accurately by these observed proportions: Pi∈{A,B,C,D} =miM. (2)Unlike the case of the network in which each unique configuration of the edges counted as a distinct micro-state,for the triads we are considering a micro-state as defined by the proportion of each type of triad. This means thatthe micro-states are uniquely determined by the variables {pA, pB, pc, pD}.
In this procedure, we aggregate both thegeometrical degeneracy within each type as well as which particular triads are in which particular configuration. Wedo this because we are interested in the total average energy and entropy of the system, and such macro-variablesare determined by a weighted sum over all possible micro-states. We assign an energy Ei to each type of triads. Thecorresponding degeneracy g(Ei) is defined as the total number of different ways of creating a triad of type i. Apartfrom the geo-metrical degeneracy (see Fig. 1), there can be other sources contributing to g(Ei). The triadic entropyST generated by the probabilities {pA, pB, pc, pD} of the energy levels of each type of triad can be calculated as: ST = −K∑i∈{A,B,C,D}pi(ln pi − ln(g(Ei)), (3)where K is a constant that connects the units of entropy and energy. This constant is the Boltzmanns constant (κβ)in statistical physics. We now derive an expression for the probabilities Pi∈{A,B,C,D}. If we assume that each typeof triad can be connected to a specific energy, the principle of maximum entropy applied to the entropy ST underconstraints of normalization of the probabilities and a finite average energy leads to the Boltzmann distribution [22].
Thereby, each energy level i ∈ {A,B,C,D} has a probability of occupation Pi given by: Pi∈{A,B,C,D} =g(Ei) exp(− EiKT )Z, (4)where the partition functionZ =∑{i∈A,B,C,D}g(Ei) exp(−EiKT), (5)acts as a normalization constant to ensure the total probability Σi∈[A,B,C,D]Pi = 1. besides, (KT ) has the units ofenergy and is the Lagrange multiplier associated with the constraint that the system has an average total energy. Inthe remainder of this work, we also use the notation β = 1/KT. From this formulation we create a model in which,for a high temperature (defined as KT + ), the triads will be stochastically occupied according to theirdegeneracy g(Ei), because exp(Ei/KT ) ≈ exp(Ej/KT )∀i, j. For small temperatures (defined as KT - )all triads will be in the lowest possible energy state Eg, because exp(Eg)/KT + exp(Ej/KT ).
In the parlance ofbalance theory, this specific small-temperature situation corresponds with utopia, a network of exclusively [+ + +]triads. It means that in high temperature our state would be close to unbalance state and in contrary in the low temperaturewe are more close to minimum energy and stable state called as balanced. The expression of Eq (3) connects theoccupation probability of a certain triadic state to the ratio of its energy and the temperature (so it is invariant undertranslations of the energy scale). Our methodology determines the triadic energies from the occupation probabilities;so although it is fundamentally impossible to determine the temperature, without any loss of generality we can setKT as the unit of energy. In the next subsection, we present the Hamiltonian formulation with the description of mean-field approach, whichwe believe to be exact for all parameter values in the limit of large system size. Using this solution, we show thatthe model possess a classic first-order phase transition between a high-symmetry regime and a symmetry-broken one,with a line of first-order transitions between 2 states of high and low temperature in the symmetry-broken regime.
Discussion
As pointed out in the previous section and summarized in, the four types of triadic relationships can be characterizedby a degeneracy and an energy. The lower the energy the more stable the triadic relationship is perceived. In theundirected network formulation of BT, the degeneracy is purely geometric. Now, as a mathematical solution for thisHamiltonian, we use mean field method. 4A. Hamiltonian and Mean-Field solutionWe can analytically solve the BT in Eq. (1) by using a method similar to that of Refs 1-2 [Newman]. In the presentstudy, we focus on the case of fully connected networks, which usually are relatively easier to deal with in theoreticaltreatment when mean-field methods are employed. Let Sij = {+1,−1} encode the relationship (friend or enemy)between nodes i and j. Then, Hij be the sum of all terms in the Hamiltonian due to sij, Eq. (1), that involve Hijand let H′be the remaining terms related to other edges, so that the Hamiltonian can be written as follows: H = Hij +H′, (6)Hij = −Sij∑k 6=ijSjkSki. (7)The mean-field approximation involves replacing the variables with their ensemble averages. We have the meanvalue of Sij as: 〈Sij〉 = P (Sij = 1) ∗ (1) + P (Sij = −1) ∗ (−1) =exp(−βHij(Sij=1)−βH′)− exp (−βHij(Sij = 1)− βH′)Z, (8)where Z =∑exp(−βH) =∑exp(−β(Hij +H′)) is the partition function, which we rewrite it here. Now, we have: 〈Sij〉 =exp(−βHij(Sij=1)−βH′)− exp(−βHij(Sij=1)−βH′)exp(−βHij(Sij=1)−βH′ ) + exp(−βHij(Sij==1)−βH′ )=exp(−βHij(Sij=1))− exp(−βHij(Sij=1))exp(−βHij(Sij=1)) + exp(−βHij(Sij=1)), (9)=exp(β∑k 6=ij SjkSki)1− exp(−β∑k 6=ij SjkSki)exp(β∑k 6=ij SjkSki) + exp(−β∑k 6=ij SjkSki)= tanh(β∑k 6=ijSjkSki). (10)According to mean-field theory and we mention above, we can have two stars as: 〈SikSkj〉 = P (Sik = 1, Skj == 1) ∗ (1) + P (Sik = −1, Skj = 1) ∗ (−1)+P (Sik = 1, Skj = −1) ∗ (−1) + P (Sik = −1, Skj = −1) ∗ (1). (11)where Z =∑exp(−βH) =∑exp(−β(Hjk 6=i+Hki 6=j +Hij 6=k+H′)) is the partition function. The two-body termin the Hamiltonian can be interpreted as a force term that attempts to homogenize the relations in the triad. Now,wesimple this by using mean-field: 〈SikSkj〉 =exp(−βHij(Sij=1,Sij=1))− exp(−βHij(Sij=1,Sij=−1))− exp(−βHij(Sij=−1,Sij=1)) + exp(−βHij(Sij=−1,Sij=−1))Z=exp(−βHij(Sij=1,Sij=1))− exp(−βHij(Sij=1,Sij=−1))− exp(−βHij(Sij=−1,Sij=1)) + exp(−βHij(Sij=−1,Sij=−1))exp(−βHij(Sij=1,Sij=1)) + exp(−βHij(Sij=1,Sij=−1)) + exp(−βHij(Sij=−1,Sij=1)) + exp(−βHij(Sij=−1,Sij=−1)). (12)So, we have two equations in two unknowns which can be solved by substituting (12) into (13) to give a self-consistency condition on q: 〈SikSkj〉 =exp(−βHij(Sij=1,Sij=1))− exp(−βHij(Sij=1,Sij=−1))− exp(−βHij(Sij=−1,Sij=1)) + exp(−βHij(Sij=−1,Sij=−1))exp(−βHij(Sij=1,Sij=1)) + exp(−βHij(Sij=1,Sij=−1)) + exp(−βHij(Sij=−1,Sij=1)) + exp(−βHij(Sij=−1,Sij=−1))= F (〈SikSkj〉). (13)In fig (7) we show a plot of the forms 〈SikSkj〉 and F (〈SikSkj〉) as functions of 〈SikSkj〉.
The intersections of thetwo curves give the solutions of Eq. (13). As we can see, depending on the values of temperature, the curves canintersect at either one or three points in the allowed domain −1 < 〈SikSkj〉 < 1 which two of them 0,−1 are theextreme state of balance theory. In other hands, our system will have two local minimum with all balance triads andequal unbalanced and balanced triads. The solution between 0 and −1 shows the meta stability of system which is astate with both type of these triads and just change one edge in a triad can move it toward two other stable points. Thus, the system displays the classic first-order phase transition, with a critical point. Finally, we calculate mean-field equation for E ≡ 〈SijSjkSki〉 which gives the number of triangle and sense ofstability in the network: 〈SikSkjSji〉 = P (Sik = 1, Skj == 1, Sji == 1) ∗ (1) + P (Sik = −1, Skj = 1, Sji == 1) ∗ (−1)+ P (Sik = 1, Skj = −1, Sji == 1) ∗ (−1) + P (Sik = 1, Skj = 1, Sji == −1) ∗ (−1)+ P (Sik = −1, Skj = −1, Sji == 1) ∗ (1) + P (Sik = −1, Skj = 1, Sji == −1) ∗ (1)+ P (Sik = 1, Skj = −1, Sji == −1) ∗ (1) + P (Sik = −1, Skj = −1, Sji == −1) ∗ (−1),(14)at least, we have: 〈SikSkjSji〉 =,[exp(−βHij(Sik,Skj,Sji=1))− exp(−βHij(Sik=−1,Skj,Sji=1))− exp(−βHij(Sik=1,Skj=−1,Sji=1)) + exp(−βHij(Sik=1,Skj=1,Sji=1))exp(−βHij(Sik=1,Skj=1,Sji=1))−3 exp(−βHij(Sik=1,Skj=−1,Sji=1)) + exp(−βHij(Sik=1,Skj,Sji=−1)) + exp(−βHij(Sik,Skj,Sji=−1))]. (15)If we plot the hysteresis loop of energy as a function of Temperature by Eq. 15, we can see that near critical point,due to thermal fluctuations in this theory which are not strong enough to drive the system over the transition barrierso that the phase transition occurs only as the balance is reached,just as in the mean-field model. Below the criticalpoint, there is a branch corresponding to the coexisting phases where Energy is not zero and
To describe how networks is affected by the temperature and obtain results demonstrating our main point, Westart out with a fully connected network with N nodes and a random configuration and converge to the Balance state. According to the analogy with Structural Balance theory, such local minimum have to exist and other cannot bereached without rearranging the edges considerably. The procedure we follow is much like a Monte Carlo simulation. In each step a randomly selected edge is flipped. The sign of the new edge, Sij is chosen according to bellow conditions. First, we select a link randomly. Then, using equation (1) the energy difference ∆E between that belonging to theprior and the new configurations is calculated. The new network is accepted if ∆E < 0 and is also accepted if ∆E > 0with a probability equal to exp(β∆E). If none of the two conditions related to ∆E are satisfied, we drop this trialand choose a new alternative edge during the process.
We see thatafter a specific temperature system does not reach to the balance state and traps in its unbalanced state. It refers7that temperature effect on convergence. So, We concentrated our efforts to obtain results demonstrating our mainpoint, i. e. , that the transition from balanced to unbalanced.
In other words,if our initial state be balanced then we will be closed to fix point -1 (local minimal) and so the system convergefaster than the other states by step Monte Carlo. In reality, we have lots of these examples. like what happen in asociety when most of people are reluctant of government. in this case, society can be referred as a network with hightemperature and most related to unbalanced one. 8C. Proposed algorithmIn this paper, we propose a new algorithm to deal with ever-increasing volumes of data, which provides a gen-eral framework for updating links like Monte Carlo but more faster than it. The proposed algorithm significantlyreduces the run-time scheduling overheads, while maintaining theoretical optimality. It consists of a sequence generalsteps: (The following features are considered in our algorithm: )1) Select a random link. 2) Compute energy of system by Eq. 13. 3) Flip all links and Update state. 4) Repeat until convergence. As we use just one step for updating the system, the evolution would be faster.
Conclusion
In this paper we have given a mean-field solution of Structural Balance model of a network with effect of temperature. Because of the intrinsically high-dimensional nature of networks, we believe this solution to be exact in the limit of largesystem size, which is the main case one is normally interested in. We have also performed Monte Carlo simulationsof the model that confirm our solution to high accuracy. Our solution indicates that temperature have significantimpact on behavior of network. A potential advantage of the consideration of the walk balance index as an equilibriumconstant is that we can study the effects of the inverse temperature over the index. This represents a way to tunethe degree of balance of a network without changing its topology. The inverse temperature plays the role here of anoverall importance given to the opinions in a social network, i. e. , high importance corresponds to β → ∞(T → 0),while low importance implies β → 0(T →∞).
