New Research In
Physical Sciences
Social Sciences
Featured Portals
Articles by Topic
Biological Sciences
Featured Portals
Articles by Topic
 Agricultural Sciences
 Anthropology
 Applied Biological Sciences
 Biochemistry
 Biophysics and Computational Biology
 Cell Biology
 Developmental Biology
 Ecology
 Environmental Sciences
 Evolution
 Genetics
 Immunology and Inflammation
 Medical Sciences
 Microbiology
 Neuroscience
 Pharmacology
 Physiology
 Plant Biology
 Population Biology
 Psychological and Cognitive Sciences
 Sustainability Science
 Systems Biology
The rise and fall of a networked society: A formal model

Edited by Kenneth W. Wachter, University of California, Berkeley, CA (received for review September 5, 2003)
Abstract
In a well networked community, there is intense social interaction, and information disseminates briskly and broadly. This is important if the environment is volatile (i.e., keeps changing) and individuals never stop searching for fresh opportunities. Here, we present a simple model that attributes the rise of a dynamic society to the emergence of some key features in its social network. We also explain the apparently paradoxical observation that although such features do not necessarily materialize even under favorable conditions they display a significant resilience to deteriorating conditions. We interpret these findings as a discontinuous phase transition in the network formation process.
There is ample empirical evidence supporting the importance of social networks as the channel through which many socioeconomic phenomena unfold. This idea is particularly apparent, for example, in the way in which economic agents find new opportunities, such as jobs or investments. It has been consistently shown by sociologists and economists alike (1, 2) that personal acquaintances or neighborhood effects play a prominent role in individual search. This, in turn, leads to significant correlations across friends, relatives, or neighbors in a variety of different socioeconomic dimensions. The common thesis proposed to explain this evidence is that, in the presence of economic volatility, the quantity and quality of one's social links, sometimes referred to as social capital (3, 4), is a key basis for search and adaptability to change.
The study of complex networks has attracted much attention (59), but it has been concerned mainly with simple phenomenological models reproducing some stylized facts in either stationary or nonstationary (e.g., growing) contexts. In contrast, sociological (10) and economic literature (11) has traditionally placed emphasis on understanding the main features and implications of stable social structures. Recently, however, much effort has been devoted as well to studying the dynamic forces (essentially, purposeful agent adjustment) that underlie the evolution and formation of networks in stationary social environments (1215). Here, our objective is to integrate these approaches by proposing a simple model of a society that embodies the following three features: agent interaction, search cum adjustment, and volatility (i.e., random link removal). Individuals are involved in bilateral interaction, as reflected by the prevailing network. Through occasional update, the value of some of the existing links deteriorates and is therefore lost. In contrast, the individuals also receive opportunities to search that, when successful, allow the establishment of fresh new links. Over time, this leads to an evolving social network that is always adapting to changing conditions.
The model studied here is a simplification of a more complex model proposed by one of the authors (16) to understand how the network dynamics impinges on strategic behavior. One of the key ingredients of our model is creation of links to friends of friends, a mechanism that was introduced by Vazquez (17) in the context of growing networks. The model is also similar to that proposed in ref. 18 to explain the emergence of the smallworld property (5) in social networks. In our context, we find as well that the smallworld property arises when the social network is dense, but our focus is quite different. Our aim is to understand how a highly connected network may emerge from social interactions and to develop a comprehensive picture of the network's macroscopic statistical properties. In particular, we find quite nontrivial clustering properties that appear to play a key role in the dynamics. In contrast with ref. 18, our model does not reproduce a scalefree topology, which is instead typical of growing networks (8) and static random networks with fitnessdriven attachment rules (19). Rather we find singlescale networks consistent with the empirical evidence of refs. 20 and 21 on several social networks, giving support to their conjecture that linkconstrained dynamics leads to singlescale distribution. Finally, among the vast recent literature on network dynamics, our work also relates to ref. 22 that found a “topological” phase transition in networks and refs. 2325 that discuss robustness of the network with respect to removal of links or nodes and transition from highly connected to diluted networks in various contexts.
The model may be described as follows. There is a population of n agents involved in a set of bilateral interactions, as specified by the prevailing social network. This network is defined, at any given point in time t, by the (undirected) graph Γ(t) = {N,g(t)}, where N = {1, 2,..., n} is the population of nodes (or agents) and g(t) ⊂ N × N represents the set of links. The social interaction taking place across a link ij ∈ g between i and j may be conceived as, say, a collaboration that is profitable for both parties.
In any time interval [t, t + dt) any existing link ij ∈ g(t) vanishes with probability λdt. This is interpreted as a random perturbation of the environment, or volatility for short. In addition, with independent probability ηdt every agent i is given the opportunity of establishing a new link with some other agent j, randomly drawn from the population. Links can also be formed through search via friends: every agent i, with a probability ξdt, asks one of his neighbors j, randomly chosen, to introduce him to one of j's neighbors, say k. If k is not already a neighbor of i the link ik is established. Naturally, nothing occurs if i has no neighbors or j has no other neighbor but i.
At a heuristic level, the link formation process can be decomposed into two complementary components. On the one hand, there is the force of volatility that stamps out the value of some preexisting links and thus, in effect, destroys them. On the other hand, there are fresh new opportunities that arise through either global search or communication with neighbors. This 2fold interpretation of the process makes the role of information clear. The dynamics of network formation can be viewed as a continuous struggle against volatility, with the information arising on new profitable opportunities partially mediated (thus constrained) by the existing network. In the stationary state agents' constant search must compensate volatility, as articulated by the socalled Red Queen Principle (26, 27): “... it takes all of the running you can do, to keep in the same place” (see more on this below).
The three rates (λ, η, and ξ) are the parameters of our model, but one of them can be eliminated by an appropriate time rescaling. We are interested in the properties of the network g(t) in the stationary state as t → ∞. Relevant magnitudes in this respect are the density of the network and its clustering. Network density at any t is measured by the average node degree z(t), where the degree z _{i}(t) of a node i is defined by the number of neighbors it has. On the other hand, network clustering C(t) is obtained by averaging the clustering coefficient C _{i}(t) of all nodes i, which is the fraction of pairs of neighbors of i who are also neighbors among themselves. Although random networks have C _{i} ∼ 1/n, social networks typically have a clustering coefficient (5) bounded above zero.
We carried out extensive numerical simulations by using a discrete time Markov chain to approximate the continuous time process. The results were found to depend very weakly on the specific discretization scheme used (see Fig. 1). For ξ = 0, the dynamics is very simple and the stationary network is a random graph with average degree z = 2η/λ (see below). For η << λ the network is composed of many disconnected parts. Fig. 1 shows what happens in a computer experiment where the local search rate ξ is first increased and then decreased very slowly (see Fig. 1 legend). For small ξ, network growth is limited by the global search process that proceeds at rate η. Clusters of more than two nodes are rare, and when they form local search quickly saturates the possibilities of forming new links. Suddenly, at a critical value ξ_{2}, a giant component connecting a finite fraction of the nodes emerges. The average degree z indeed jumps abruptly at ξ_{2}. The network becomes more and more densely connected as ξ increases further. But when ξ decreases, we observe that the giant component remains stable also beyond the transition point (ξ < ξ_{2}). Only at a second point ξ_{1} does the network lose stability and the population gets back to an unconnected state. There is a whole interval [ξ_{1}, ξ_{2}] where both a densenetwork phase and one with a nearly empty network coexist. The coexistence region [ξ_{1}, ξ_{2}] shrinks as η increases and it disappears for η > 0.03λ. This behavior attains already for moderately small n, even though in this case finite size effects are strong; these effects essentially vanish when n ≥ 1,000 (see Fig. 1). The average clustering coefficient C shows a nontrivial behavior. In the unconnected phase, C increases with ξ as expected. In this phase, C is close to one because the expansion of the network is mostly carried out through global search, and local search quickly saturates all possibilities of new connections. On the other hand, in the densenetwork phase, C takes relatively small values. This makes local search very effective. Remarkably, we find that C decreases with ξ in this phase, which is rather counterintuitive: by increasing the rate ξ at which bonds between neighbors form through local search, the density C of these bonds decreases.
The stability of the dense network phase in the coexistence region confers resilience to the system. It implies that a dense network is robust with respect to deteriorating conditions (higher λ or smaller ξ) and it may resist even under conditions in which a stable dense network would not form. In fact, similar behavior is found, fixing ξ and η, as a function of the volatility rate λ.
The system behavior observed in Fig. 1 is typical of firstorder phase transitions and is remarkably similar to the rise of hysteresis in physics, a phenomenon that has its origins in the ergodicity breakdown. Even if, in principle, the process is ergodic, because all configurations can be reached from any other configuration, when n is large the configuration space gets broken into different ergodic components. Transitions across the boundaries of these components require large deviations that occur only with a probability that is exponentially small in n (they require fluctuations out of equilibrium in a collection of local neighborhoods whose number is of order n; see below). Strictly speaking, transitions between the two components will occur, but one typically has to wait astronomically large times. The occurrence of phase coexistence in our model is also intuitive and has many analogies with that of a real fluid: the local process (ξ) mimics shortrange attractive interaction, whereas the λ and η processes capture the effects of temperature and random collisions. Increasing ξ is analogous to compressing the fluid (reducing the volume), which increases the chances that two molecules enter into the range of mutual interaction. An important difference is that interaction is long ranged in our model, which, as discussed in ref. 28, makes it impossible to have bubbles of one phase into the other: the system is either all in one or in the other phase.
To shed light on these numerical results, we study the dynamics of the distribution of the degrees and clustering coefficients . Specifically, we study a mean field approximation that assumes C _{i} = C for all i = 1,..,n and It is convenient to set λ = 1, by an appropriate time rescaling. Then, the transition rates that enter into the master equation for p are: where θ(x) = 0 for x ≤ 0 and θ(x) = 1 for x > 0. In Eq. 2 , the first term accounts for longdistance search (the factor 2 arises because site i can be either the origin or the destination of the process). The second term arises from local search, and it requires that z _{i} > 1. Here β = ξ(1  C)P{z _{j} > 1ij ∈ g} is proportional to the conditional probability that z _{j} > 1 given that ij ∈ g. Finally, the last term accounts for indirect local search opportunities given to a friend k of a friend j of i. This process is proportional to z _{i} and accounts for the probability that i is not a friend of k and that k selects j.
Both β and γ will be determined selfconsistently. Using the generating function method, the master equation for p(z) in the stationary state can be solved with the result where μ = (2η + β)/γ. Simple algebra shows that where p _{0} and p _{1} are constants. Notice that p(z) ∼ z ^{μ} has a power law behavior for small z and decays exponentially p(z) ∼ e ^{lnγz} for large z, in perfect agreement with the behavior observed in numerical simulations.
Eq. 4 allows us to compute the distribution P{z _{j} = uij ∈ g} = p̃(u) for the degree z _{j} of a neighbor j of i. The larger z _{j} the more likely is j a neighbor of i. Thus, p̃(u) ∞ up(u), which, in terms of the generating function implies ˜π(s) = sπ′(s)/π′ (1). This makes it possible to compute P{z _{j} > 1ij ∈ g} = 1  ˜π′(0) = 1  π′(0)/π′(1) and the factor , which enters the definition of γ, thus leaving us with the selfconsistent equations: As we should, in the limit ξ → 0 we find β, γ → 0, and we recover a pure Poisson distribution with mean 2η. Under ξ > 0, local search makes the degree distribution loose its Poisson character. But with constant C Eqs. 6 and 7 are not able to reproduce the observed behavior. It just predicts a smooth crossover and no phase coexistence. This finding means that, to shed light on the observed behavior, it is essential to allow for C to depend on the parameters of the model.
To derive an equation for C, we focus on a particular site i and analyze the process that governs the number Q _{i} = C _{i} z _{i}(z _{i}  1)/2 of pairs of neighbors of i, which are also neighbors among themselves. Local search contributes to an increase in Q _{i} in two ways. The first is when a local search opportunity is given to site i itself, which has already been discussed above. Its rate is W _{1}(Q _{i} → Q _{i} + 1) = β. The second occurs when a local search opportunity is given to some friend j of i, who then asks i about his other friends k (k ≠ j). This may lead to the formation of the link between j and k, thus increasing Q _{i} by one. The rate of this process is given by . Here, 1/z _{j} is the probability that j picks i from his neighbors and 1  C is the probability that k is not a friend of j. This rate should be multiplied by the number z _{i} of neighbors of i, but is zero unless z _{i} ≥ 2. Finally, we must account for the linkdecay process that, contrary to the former two, decreases Q _{i}. The rate at which this happens is .
If we now take the averages on z _{i} and z _{j} with probability distributions p and p̃, respectively, we can impose stationarity on Q _{i}, i.e., . After some algebra, this condition becomes the desired equation for C: Using Eq. 4 , we arrive at a set of three selfconsistent equations for β, γ, and C.
The solution of Eqs. 6 , 7 , 8 is shown in Fig. 2. We recover the main qualitative features observed in numerical simulations. In particular, our solution correctly reproduces the behavior of C in the two phases: C increases with ξ in the dilute network phase, whereas it decreases with ξ when a giant component forms. Our approach shows that this is not just a byproduct of our analysis but rather an essential ingredient for understanding the network's dynamics. The degree distribution is close to Poissonian in the diluted phase, where β and γ are small, whereas it is markedly nonPoissonian in the dense phase. Fig. 2 also depicts the phase diagram predicted by the mean field. In the shaded region, Eqs. 6 , 7 , 8 have three solutions, two of which are stable and correspond to the two coexisting phases. The third is an unstable state, shown as dashed lines in the plots of z and C of Fig. 2, and it separates the basins of attraction of the two stable states. Within the meanfield theory, if the initial average degree z(0) is below the unstable solution z ^{*}, the dynamics will flow to the diluted network solution, whereas if z(0) > z ^{*} a dense network will form. Likewise, a network in either phase can “flip” to the other phase because of random fluctuations. For this to occur the spontaneous fluctuation δz in the average degree must be large enough to cross the boundary. These fluctuations are extremely rare events that typically occur with a probability that is exponentially small in n, as shown by large deviation theory (29).†† Interestingly, the unstable solution z ^{*} turns out to be very close to the diluted network solution when ξ is close to ξ_{2}. This finding suggests that, in this region, transitions from diluted to dense networks are more probable than transitions in the other direction, as also observed in numerical simulations.
The behavior of the system as a function of λ (with ξ and η fixed) can also be read from the phase diagram. It can be traced, as λ increases, by moving toward the origin on a line with constant slope η/ξ. The coexistence region culminates in a secondorder phase transition point at the critical point η_{c}/λ ≅ 0.226. Beyond this point, the discontinuous transition turns into a smooth crossover. The specific critical values of the parameters are inaccurate, as is often the case in mean field calculations. The coexistence interval [ξ_{1}, ξ_{2}] predicted by the mean field theory is larger than that observed in numerical simulations, as can be seen by comparing Figs. 1 and 2, because mean field theory underestimates fluctuations and neglects correlations. On the other hand, all qualitative features are very well reproduced within the meanfield approximation.
It is straightforward to repeat our derivation for the model of ref. 18. There the network grows by a mixture of local and global search. In addition, volatility affects sites instead of removing bonds, i.e., Eq. 3 is replaced with w(z _{i} → 1) = 1. This changes things considerably, since then stationarity in the master equation implies p(z) = a + z  1/a + b + z p(z  1) for z > 1, with a, b ≥ 0 constants that should be determined selfconsistently. The network then acquires a scalefree behavior p(z) ∼ z ^{b1}, in agreement with what observed in ref. 18. However, the solution of the selfconsistent equations is always unique, confirming that there is no phase transition in the model of ref. 18. This finding illustrates the usefulness of the present approach to the analysis of general network dynamics and its potential for contrasting the implications of different assumptions.
The former derivations clarify, in particular, that the alternative assumptions of nodebased and linkbased volatility have profound effects on the dynamics of network formation. Not only do they affect the nature of the transition but also the kind of degree distribution displayed at stationary states. When volatility affects links, the situation can be regarded as akin to that prevailing in many social networks, i.e., the agents are severely limited in their ability to maintain an ever increasing number of links, because of the impossibility of suitably compensating for their steady unavoidable deterioration. Instead, matters are often quite different in other kinds of networks (biological, technological, or informational) and even in those social networks whose links embody a onceandforall choice (say, collaboration in scientific networks). These considerations have been highlighted in refs. 20 and 21, where empirical evidence is discussed that is consistent with the predictions of our model. It is reported, for example, that while the degree distribution of certain social networks of the first kind display a rather sharp characteristic scale, those of the latter tend to be much broader. In a certain sense, the contrast between both scenarios could be tailored to the main basis (links or nodes) on which volatility operates.
To sum up, we have proposed and studied a simple model of network formation that displays a firstorder transition between a sparsely connected phase and a densely connected one. Close to the transition, it may just take a slight change in the environmental conditions for a virtuous or vicious circle to set in. This is reminiscent of the “miracles” and “antimiracles” that are still an unresolved puzzle for the modern theory of economic development (cf. ref. 30). Within a sizable parameter range, both situations coexist and are metastable, which suggests that external intervention (in the form of a nucleation event) may be needed to trigger the growth of the new phase. The model also underscores the importance of effective search to offset environmental volatility in a highly connected network. This, as explained above, is in line with what is known as the Red Queen Principle in evolutionary biology (27). In our network setup, the effectiveness of search is directly associated to low clustering. This explains that the abrupt transition to the highdense phase must be mirrored (otherwise it would not be stable) by a corresponding shift to a social network with low clustering.
Acknowledgments
This work was supported in part by the EXYSTENCE Network of Excellence of the European Union, Spanish Ministry of Education Grant BEC20010980, the Grant Agency of the Czech Republic (Grant 202/01/1091), and European Union Grant HPRNCT200200319 [STIPCO (Statistical Physics of Information Processing and Combinatorial Optimization)].
Footnotes

↵ ∥ To whom correspondence should be addressed. Email: slanina{at}fzu.cz.

This paper was submitted directly (Track II) to the PNAS office.

↵ †† The predictions of large deviation theory can be worked out by assuming that z _{i} are independently and identically distributed variables with distribution p(z). In parametric form, a deviation δz = yπ′(y)/π(y)  π′(1) from the average connectivity z occurs with a probability ∞ e ^{nS(δz)}, where S(δz) = logπ(y)  y(logy)π′(y)/π(y). Note that S ≤ 0 and S = 0 when δz = 0(y = 1). It is worth noting that, strictly speaking, the derivation of p(z) applies only to equilibrium states, whereas large deviations are outofequilibrium phenomena. Hence the above derivation provides just a crude approximation to the transition probabilities.
 Copyright © 2004, The National Academy of Sciences
References

↵
Granovetter, M. (1995) Getting a Job: A Study of Contacts and Careers (Chicago Univ. Press, Chicago), 2nd Ed.

↵
Topa, G. (2001) Rev. Econ. Studies 68 , 261295.
 ↵

↵
Putnam, R. (1993) Making Democracy Work (Princeton Univ. Press, Princeton).
 ↵

Barabási, A.L. & Albert, R. (1999) Science 286 , 509512. pmid:10521342
 ↵
 ↵

↵
Wasserman, S. & Faust, K. (1994) Social Network Analysis: Methods and Applications (Cambridge Univ. Press, Cambridge, U.K.).
 ↵
 ↵

Suitor, J. J., Wellman, B. & Morgan, D. L. (1997) Social Networks 19 , 17.

Burt, R. (2000) Social Networks 22 , 128.
 ↵

↵
VegaRedondo, F. (2002) Building Up Social Capital in a Changing World, WPAD 200226 (Instituto Valenciano de Investigaciones Económicas, Alicante, Spain).
 ↵
 ↵
 ↵

↵
Amaral, L. A. N., Scala, A., Barthélémy, M. & Stanley, H. E. (2000) Proc. Natl. Acad. Sci. USA 97 , 1114911152. pmid:11005838

↵
Newman, M. E. J., Watts, D. J. & Strogatz, S. H. (2002) Proc. Natl. Acad. Sci. USA 99 , 25662572. pmid:11875211

↵
Palla, G., Derényi, I., Farkas, I. & Vicsek, T. (2003) ePrint archive, http://arxiv.org/abs/condmat/0309556.
 ↵
 ↵

↵
Carroll, L. (1872) Through the Looking Glass and What Alice Found There (Macmillan, London).

↵
Van Valen, L. (1973) Evol. Theory 1 , 130.
 ↵

↵
Ellis, R. S. (1985) Entropy, Large Deviations, and Statistical Mechanics (Springer, New York).
 ↵