Example of an Emergent Phenomena : Fireflies

"At the heart of the universe is a steady, insistent beat: the sound of cycles in sync. It pervades nature at every scale from the nucleus to the cosmos. Every night along the tidal rivers of Malaysia, thousands of fireflies congregate in the mangroves and flash in unison, without any leader or cue from the environment. Trillions of electrons march in lockstep in a superconductor, enabling electricity to flow through it with zero resistance. In the solar system, gravitational synchrony can eject huge boulders out of the asteroid belt and toward Earth; the cataclysmic impact of one such meteor is thought to have killed the dinosaurs. Even our bodies are symphonies of rhythm, kept alive by the relentless, coordinated firing of thousands of pacemaker cells in our hearts. In every case, these feats of synchrony occur spontaneously, almost as if nature has an eerie yearning for order."
--- A quote from Sync - The Emerging Science of Spontaneous Order by Steven Strogatz 

One of the most intriguing phenomena within complexity science is that of emergence.  It is a salient feature of complex systems, so much so that definitions of complex systems include the quality of exhibiting emergence.  Many exciting solutions to the world’s bigger problems can be understood through collective dynamics and emergence.

What is Emergence?

Emergence is when behavior at a smaller scale of a system produces global behavior that is not entirely intuitive given the behavior at the smaller scale.  The global behavior is not directly programmed in the behavior at the local level. Something surprising happens at the larger scale.  From simple local interactions, we can arrive at global behavior that is immensely complex, sometimes seemingly random.

Another way to think of emergence involves the notion that the whole is greater than the sum of its parts. The behavior of the system is a result of not only its parts, but their interactions. The actions at the level of the individual do not imply that of the behavior of the system. We need to understand not only the system at the individual level, but at the level of multiple individuals to observer the effect of their interactions.

One of the most exciting examples of emergence involves evolution. At a smaller scale we have natural selection, species in a population surviving or dying over time based on selection pressures from the environment, with possible species variations through reproduction and sexual selection and the random chance of mutation. At a larger scale we have the development of biodiversity, a wide range of organisms from bacteria to whales, and an environment with so many different species able to thrive within different niches. Global biodiversity is not programmed in the local interactions; it is an emergent property. 

Why is it important to study the emergence of a system?

Understanding emergence is essential when working with complex systems. For the most part, complex systems exist because they are grown, i.e. they have evolved to be what they are. They are composed of many parts that interact across scales, from individuals to groups to the whole. When we think of a city, it grows through the interaction of all of the individuals and organizations which comprise the city. The city is not formed by a single individual, it is formed by its population. Emergent behavior can be difficult to understand, since by its very nature it is unintuitive and unpredictable (the very reason why it has received so much attention). In understanding global behaviors of a system, it helps to understand how individual interactions led to the global behaviors. In this way, one can attempt to reproduce the global behaviors through recreating the individual interactions. 

Example of Emergent Behavior: Fireflies

Fireflies can spontaneously synchronize their flashing: this phenomenon is one of the most popular example that illustrates emergent phenomena. The question surrounding the synchronization among fireflies is that when there is no head firefly, who has the ability to communicate with all the rest, so how is it possible that all fireflies flash in synchronization, when no firefly can see all of the rest?

Efforts have been made in the direction of developing a model that introduces a mechanism of simple interactions between the fireflies which operate locally [1]. Through this local interaction, the global behavior is that of synchrony. The key concept with respect to emergence is that the local interactions do not mention anything about synchronizing.

The analysis of this phenomena can be done using the following mathematical model.

Each firefly can be assumed to be an oscillator with time period of T, saying it fires at time T, and resets to zero only to fire again at time T. All of the fireflies have the same period T, but start at different times in their period. At each step, all of the fireflies increment in their period.

Also,, any firefly can see only within a certain detection radius. When one of the neighbors of a firefly flashes, the firefly increments in its period, leading it closer to flashing. The nature of this firing response is important. Say that a firefly is at time t’ in its period. The firing response is defined as follows: the amount of increment increases as t’ increases. So if a firefly is later in its period, the increment will be higher. If its just beginning its period, the increment will be lower. The next is not so important for the concepts, but mathematically it can be more accurately stated as such:

                                               

Here, t” is the new internal time if a firefly experiences a flash at time t’. As defined in the model, f is the firing function and epsilon is a small constant < 1 .
From a simple rule given a neighbour flashing, organization emerges as the fireflies flash as a group. The group is able to act as a whole through local interactions.

The above example of fireflies is useful for synchronising distributed systems like a wireless sensor networks, etc.

How can we go about studying the Emergent Behaviour of a System?

Think about environments that your are in or have seen, and reframe them in the systems perspective. How do the parts combine to form the whole. Is the emergent behavior obvious given local interactions?

What if there is a particular global quality we want to achieve. What are ways in which local interactions can achieve those global qualities? Because the global behavior can be unpredictable, it can become a difficult problem to determine the local interactions. But other times, those interactions can be found through the ingenuity of a group and global behaviors can be achieved. The question then also becomes, how do you create and environment that will promote such creativity? This is a question of emergence, in designing local interactions to promote global creativity.

References:

[1] ‘Synchronization of pulse-coupled biological oscillators’, R. Mirollo and S. Strogatz

[2] http://whichlight.com/article/emergence-fireflies/

Caveman World or Solaris or in between them - the birth of alpha model

The alpha model was one of the primitive attempt to model real-world social network. Before the proposition of small-world model by Watts-Strogatz, this model was one of the first attempt by Watts and Strogatz to really answer the question "What are the most general conditions under which the elements of large, sparsely connected network will be close to each other? " The modeling of the alpha graph makes two basic generalizations:

1) A network is represented purely in terms of connections between its elements i.e., whatever combination of factors makes people more or less likely to associate is
accounted for and represented by the distribution of those associations that actually form. Further, it also assumes all such connections to be symmetric and equally significant.

2) The likelihood of a new connection being created is determined by already existing connection pattern i.e., the current friends of a person determines to some extent the new friends of a person.

But how is new connections being formed? Is it caveman-like or is it solaria or in between them ?

The Caveman World:

"Everybody you know knows everybody else you know but no one else". So, an absence of mutual acquaintances among individuals means they live in different "caves", thus they will probably never meet. But if an individual has even one common friend implies that they live in the same community, move in the same social circle and so are very likely to become acquainted.

The Solaria:

The other extremity is the world of solaria. The name is after the planet "Solaria" from famous Issac Asimov novel where future humans live in isolation and interact across planets through computers and robots. In Solaria, the influence of existing friendship on new friendship links is indistinguishable from random chance i.e., social history of individuals are irrelevant to their future. Even if two people happen to have many friends in common, they are no more or less likely to meet than if they have none.

The real world social networks lie somewhere in between "caveman" and "solaria". To model the real world, one requires the following features in the algorithm for constructing such graphs

a) At one extreme (caveman world), the tendency of two unrelated people to get connected is very small. Once they share just one common friend their tendency to become acquainted becomes immediately very high and stays that way regardless of how many additional mutual friends they have. (see fig 1)

Fig.1 : Two extremes. in the top curve (caveman world) even a single mutual friend implies that A and B are highly likely to meet. In bottom curve (solaria) all interactions are equally likely, regardless of how many friends A and B have in common.

b) At the other extreme (solaris), having a very large number of mutual friends has very little effect on people's tendency to interact. Under almost all circumstances,
they interact randomly. (see fig 1)

c) In between these two extremes, the curves can take any one of an infinite number of intermediate forms by tuning a model parameter alpha where alpha = 0 corresponds to caveman world and alpha = infinite corresponds to solarian world (see fig 2).

Fig2 : Between two extremes, a whole family of interaction is possible , each one specified by tunable parameter alpha. When alpha = 0, it is caveman world and when alpha = infinite, it is solaria

To satisfy such constraints, one need to devise a metric which is the following:
where R i,j is the measure of tendency of vertex i to be connected with vertex j. (0 if already connected)
m i,j is the no. of vertices adjacent to both i and j
k is the average degree and p is the probability of an edge (i,j) being existing

Given n, k and alpha.

The algorithm is as follows:
1) Choose a vertex i uniformly at random.
2) For every other vertex, compute R i,j.
3) Sum the R i,j over all j's and normalize each to get P i,j which is the probability that i will connect to j
4) Generate a random number in [0,1]. If it corresponds to say, j*
5) connect i to j*.

Repeat until n.k/2 number of edges are formed.

The small-world model of Watts  and Strogatz

In order to model the real-world networks, we need to find a way of generating graphs which have both the clustering and small-world properties. As we know, random graphs show the small-world effect, possessing average vertex-to-vertex distances which increase only logarithmically with the total number N of vertices, but they do not show clustering—the property that two neighbors of a vertex will often also be neighbors of one another.

The Watts-Strogatz model is a random graph generation model that produces graphs with small-world properties, including short average path lengths and high clustering. It was proposed by Duncan J. Watts and Steven Strogatz in their joint 1998 Nature paper. The model also became known as the (Watts) beta model after Watts used B  to formulate it in his popular science book Six Degrees.

Though  Erdős–Rényi (ER) graphs, offer a simple and powerful model with many applications. However the ER graphs do not have two important properties observed in many real-world networks:

1.  They do not generate local clustering and triadic closures. Instead because they have a constant, random, and independent probability of two nodes being connected, ER graphs have a low clustering coefficient.

2.  They do not account for the formation of hubs. Formally, the degree distribution of ER graphs converges to a Poisson distribution, rather than a power law observed in many real-world, scale-free networks.

The Watts and Strogatz model was designed as the simplest possible model that addresses the first of the two limitations. It accounts for clustering while retaining the short average path lengths of the ER model. It does so by interpolating between an ER graph and a regular ring lattice. Consequently, the model is able to at least partially explain the "small-world" phenomena in a variety of networks, such as the power grid, neural network of C. elegans, and a network of movie actors.

Algorithm:

Given the desired number of nodes N, the mean degree K (assumed to be an even integer), and a special parameter, satisfying and 

the model constructs an undirected graph with N nodes and NK/2 edges in the following way:

1. Construct a regular ring lattice, a graph with N nodes each connected to K neighbors, K/2 on each side. 
2. For every node  take every edge (ni,nj) with i<j, and rewire it with probability.Rewiring is done by replacing (ni,nj) with (ni,nk)  where K is chosen with uniform probability from all possible values that avoid loops (k!=i) and link duplication (there is no edge (ni,nk') with K'=K at this point in the algorithm).

Average path length:

For a ring lattice the average path length is l(0)= N/2K >> 1 and scales linearly with the system size. In the limiting case of B -->1 the graph converges to a classical random graph with l(1)=ln N/ln K. However, in the intermediate region 0<B<1 the average path length falls very rapidly with increasing B, quickly approaching its limiting value.

Clustering coefficient:

For the ring lattice the clustering coefficient is C(0) = 3/4 which is independent of the system size. In the limiting case of B -->1 the clustering coefficient attains the value for classical random graphs, C(1) = K/N and is thus inversely proportional to the system size. In the intermediate region the clustering coefficient remains quite close to its value for the regular lattice, and only falls at relatively high B. This results in a region where the average path length falls rapidly, but the clustering coefficient does not, explaining the "small-world" phenomenon.

Degree distribution:

The degree distribution in the case of the ring lattice is just a Dirac delta function centered at K. In the limiting case of B-->1 it is Poisson distribution, as with classical graphs. The degree distribution for 0<B<1 can be written as,

where f(k,K) = min(k-K/2,K/2) and the shape of the degree distribution is similar to that of a random graph and has a pronounced peak at k = K and decays exponentially for large |k-K|. The topology of the network is relatively homogeneous, and all nodes have more or less the same degree.

Limitations:

The major limitation of the model is that it produces an unrealistic degree distribution. In contrast, real networks are often scale-free networks inhomogeneous in degree, having hubs and a scale-free degree distribution. Such networks are better described in that respect by the preferential attachment family of models, such as the Barabási–Albert (BA) model.

Pólya's Urn

This is an interesting model named after Hungarian mathematician George Pólya ( wide range of fields where he contributed includes number theory, complex analysis, combinatorics, geometry ect.) which gives us some insight about some statistical distributions. Apart from his contribution to all these fields he is also famous for this books (there are four of them) on  'how to solve it' and his conjecture (Pólya's conjecture) which is proved false in 1958.

The simplest version of the model is like this, given an urn (a container) containing some fixed number (say x) of balls of colour-1 (say red) and some fixed number (say y) of balls of colour-2 (say blue) we perform the following experiment.

1. At each step we draw one ball randomly from the urn, note its colour.
2. Return the ball in the urn along with another ball of the same colour.

A more complex model is the one where we have balls of colour more than one and after each draw we return d number of balls of same colour instead of only one. This model is completely opposite to the model of sampling without replacement where number of balls decrease with time.

Some interesting questions which can arise is
1. Can we estimate the distribution of balls after a fixed number of trial ?
2. Can we determine the probability of choosing a particular sequence of coloured balls  if we know x and y. For example what is the probability that at 12th,13th and 14th trial we will see a red, a blue and a red ball respectively ?
3. If we observe repeatedly n number of red balls with what confidence we can infer that there is no blue ball ?

These kind of questions give rise to well known discrete probability distributions. For example distribution of the number of successful draws is beta-binomial distribution. When there are balls of more than two colours, the first question above gives rise to Dirichlet-multinomial distribution which is also known as multivariate Pólya distribution.

Pólya's Urn model is used to model preferential attachment in networks where nodes having high degree have the high probability of getting an edge when a new node enters into the system.

Preferential Attachment and the Barabasi-Albert model

    A large number of real world networks like the world wide web, citation networks and some social networks are scale free. The origin of the power-law degree distribution observed in real world networks was addressed by Barabasi and Albert in the paper titled Emergence of Scaling in Random Networks published in Science(1999). The scale-free nature of real networks is rooted in two generic mechanisms shared by many real networks - growth and preferential attachment. 

Growth - Real world networks keep growing in size continuously by the addition of new nodes.

Preferential attachment - New nodes tend attach to nodes with a high degree. For example a new web page will add hyperlinks to popular web pages which already have a high degree. Preferential attachment is sometimes also called the Matthew Effect ("the rich get richer and the poor get poorer"), a term derived from the Gospel of Matthew:

       "For unto every one that hath shall be given, and he shall have abundance : but from him that hath not shall be taken even that which he hath."

(Though in the preferential attachment model for networks "the poor get poorer" part is not true).

     A preferential attachment process is one in which some unit of wealth (balls) are added to a set of containers (urns).Balls are added to the system at an overall rate of m new balls for each new urn. In a linear preferential attachment each newly created urn starts out with k0 balls and further balls are added to urns at a rate proportional to the number k that they already have plus a constant a > -k0. A linear preferential process shows a Yule-Simon distribution given by

where B is the beta function

Yule-Simon distribution

Probability Mass function on log-log scale

The probability of an urn containing k balls after a long time is given by

where

  

 For the Barabasi-Albert model k0 = m and a = 0 where urns correspond to nodes and balls to edges. Each vertex enters with a degree m and each of those m edges attach to nodes where the probability of attaching to a node is proportional to its degree. 

Properties of Barabasi Albert Graphs :

• The degree distribution is of the form

• Average path length

• Clustering coefficient

This model however lacks several properties of the world wide web :

• The model is a model of an undirected network, where the real Web is directed.

•One can regard the model as a model of a directed network, but in that case attachment is in proportion to the sum of in and out-degrees of a vertex, which is unrealistic - attachment should be in proportion to in-degree only.

• If we regard the model as producing a directed network, then it generates acyclic graphs which are a poor representation of the Web.

• All vertices in the model belong to a single connected component .In the real Web there are many separate components.

For the world wide web a number of authors have suggested alternate growth models to address the above issues.

References :

[1] The Structure and Function of Complex Networks - M.E.J Newman

Immunization and Epidemic Dynamics in Complex Networks

The study of epidemic spreading is based upon the notion that a disease is conveyed by contact between an infected individual and an uninfected individual who is susceptible to the disease. An endemic stage is reached if a finite fraction of the population is infected. Similarly, this notion may describe the spreading of a computer virus through a network of computers. Recently, it has been shown that in a class of scale free networks an epidemic may spread regardless of how low is its rate of infection. Further discussion is done on static and sparse networks.

SIR MODEL

The SIR model represents the development of a disease in a network of connected individuals. S stands for the susceptible stage, where the individual is healthy. I stands for the infected stage, where the individual is infected with the disease and can infect other individuals in contact with it. R is the removed stage, where the individual is either recovered and has acquired immunization to the disease or otherwise permanently removed from the system.

One of the nicest features of the SIR model is that despite it being a dynamic model it can be mapped into a completely static one. Consider a network where each node transmits the epidemic to each of its neighbors with rate r, and is removed with average recovery time τ.The infection can be, therefore, considered as a Poisson process, with average rτ. Thus, the probability for each neighbor not to be infected is e^−rτ.

A site can be reached by one of its k links, its probability of being reached is kP(k) / (N<k>)  where N is the number of nodes, P(k) is the fraction of nodes having degree  k, and <k> =  Σ _kkP(k) denotes the average degree of nodes in the network.


Since the network is randomly connected, as long as the epidemic is not spread yet, the average number of influenced neighbors is:

                                                        

Immunization

General immunization can be seen as a site percolation problem. Each immunized individual can be regarded as a site which is removed from the network. The goal of the immunization process is to pass (or at least approach) the percolation threshold, leading to minimization of the number of infected individuals. The complete model of SIR and immunization can be considered as a site–bond percolation model, and the immunization is considered successful if the network is below the percolation threshold.

Random Immunization:

Studies of percolation on broad-scale networks show that a large fraction f_c of the nodes need to be removed (immunized) before the integrity of the network is compromised. In particular it is true for scale free networks.With a random immunization strategy almost all of the nodes need to be immunized before an epidemic is arrested (see Fig. 1).

                                       

is the immunization threshold where p_s = 1-f  . The probability of each of its k − 1 outgoing links of infecting its neighbor is p_b. 



Targeted Immunization:

When the most highly connected nodes are targeted first, removal of just a small fraction of the nodes results in the network’s disintegration. This has led to the suggestion of targeted immunization of the HUBs (the most highly connected nodes in the network). The simplest targeted immunization strategy calls for the immunization of the most highly connected individuals. To use this approach, the number of connections of each individual should be known (at least approximately). In this case, the probability that a site is not immunized, when the immunization rate is f, is θ_f (k), where,

 and k* and 0 < c <=1 are determined by the condition 

is the critical immunization threshold.

Fig:1 Critical immunization threshold f_c as a function of γ in scale free networks(with m=1) for the random immunisation(♦) and targeted immunization ( [] ) strategies. Curves represent analytical results while data points represent simulation data.Full symbols are for random and acquaintance immunization of assortatively mixed networks.

Fig. 2. Critical concentration, f_c, for the bimodal distribution (of two Gaussians) as a function of d, the distance between the modes. The first Gaussian is centered at k = 3 and the second one at k = d + 3 with height 5% of the first. Both have variance 2 (solid lines) or 8 (dashed lines). Top 2 lines are for random immunization. The bottom 2 lines are for acquaintance immunization. Note that also for the case d = 0, i.e. a single Gaussian, the value of f_c reduces considerably due to the acquaintance immunization strategy. Thus the strategy gives improved performance even for relatively narrow distributions.

Fig. 3. Critical concentration, f_c, vs. r, the infection rate, for the SIR model with τ = 1. The solid lines are for random (top) and acquaintance immunization (bottom) for scale-free networks with γ = 2.5. The dashed lines are for γ = 3.5 (top – random, bottom – acquaintance immunization). The circles represent simulation results for acquaintance immunization for scale-free networks with γ = 2.5.

Fraction of endemic outbreaks p_e , as a fuction of the fraction of immunized individuals f, for random immunization,acquaintance immunization, and targeted immunization strategies.










Practical  Issues:

Various immunization strategies have been proposed, mainly for the case of an already spread disease, and are based on tracing the chain of infection towards the superspreaders of the disease. This approach is different from our proposed approach, since it is mainly aimed at stopping an epidemic after the outbreak began. It is also applicable for cases where no immunization exists and only treatment for already infected individuals is possible. Our approach, on the other hand, can be used even before the epidemic starts spreading, since it does not require any knowledge of the chain of infection. In practice, any population immunization strategy must take into account issues of attempted manipulation. We would expect the suggested strategy to be less sensitive to manipulations than targeted immunization strategies. This is due to its dependence on acquaintance reports, rather than on self-estimates of number of contacts. Since a node’s reported contacts pose a direct threat to the node (and relations), we anticipate that manipulations would be less frequent. Furthermore, we would suggest adding some randomness to the process: for example, reported acquaintances are not immunized, with some small probability (smaller than the random epidemic threshold), while randomly selected individuals are immunized directly, with some low probability. This will have a small impact on the efficiency, while enhancing privacy and rendering manipulations less practical.

Effects of Levy Flights Mobility Pattern on Epidemic Spreading

Most of the studies on human and animal mobility pattern including experimental data and theoretic analysis found that their mobility pattern follows the Levy flight:

Epidemic spreading processes always follow the mobility of human and animal. In this article, establish a network model with a Levy flight spatial structure to reflect the feature of human and animal mobility pattern and study the effects of Levy flights’ mobility pattern on epidemic spreading from a complex network perspective.

Spatial Network Model

Energy

To establish a Levy flight spatial network , as all the individuals only have limited energy, there must be a cost constraint on the mobility. Hence, we give a restriction on total energy.

The frequency distribution of sum of walk distances in a day for deer and sheep. Both distribution are vary narrow, which represents the energy distribution is homogenous.

Network Model


Based on a uniform cycle, each node denotes a small group of people. Given a restriction on total energy, we get a one-dimensional weighted network with a Levy flight spatial structure. According to levi flight pattern (P(d) ~ d^alpha ), the weight w_ij on the link between node i and j should be proportional to d _ij^alpha, and for a given network size, the sum of all w_ijd_ij should be a constant which denotes the energy constraint. So, we can get an ensemble network model of these spatial weighted networks generated by many times of realization as:

 that solves into
    =>

 Diffusion


On this weighted network, the infected probability is related with the weight. 

A susceptive node i will be infected with a probability :

      where v is the spreading ratio, and I is the set of infected nodes.

Infected nodes become susceptible with rate delta.  The effective spreading rate is defined as :

SI Model

Randomly choose one node as an infected individual, others are susceptible.
Terminate until all the nodes are infected and register the steps have been taken as T .

Epidemic spreading speed with different exponents

The figure alongside is for n = 1000, V = 0.05.


The curve has a lowest point when alpha ~ 2.
This imples that the mobility pattern will drive the epidemic diffusion.

Spread ratio under different alpha and various network size n

The dependence of spread ratio on time under different alpha.
A. Spread ratio under alpha = 0 and alpha = −1, respectively.
B. Spread ration under = −2. We can see that when alpha = −2, the spread ratio grows much faster than other cases.