A REVIEW OF SOME DYNAMICAL PROCESSES ON SCALE-FREE NETWORKS
Paper Presenter: KHEMANAND MOHEEPUT, Department of Physics
Author: SATISH RAMCHURN, Department of Physics
It is has been observed that natural or man-made systems such as social interacting species, networks of proteins, the structures of the Internet and the World Wide Web consist of a large number of highly interconnected dynamical units and that these systems often organised themselves into a networks. One way of studying the global properties of these systems is to model them as graphs whose nodes represent the dynamical units, and whose links mimic the interactions occurring between pairs of the nodes. Thus the study and application of the science of network have become central during the last fifty years. However in the past two hundred years, there have been three major transition stages in evolution of the science of network.
The very first network model created was a regular network by Jan de Vries in the year 1891. For modelling this type of network a regular graph is constructed, in which each vertex has the same number of neighbours implying that every vertex has the same degree of connectivity. Regular lattice-like networks have strongly peak distribution and a perfectly ordered lattice has a delta-Dirac degree distribution.
In the late 1950s, Paul Erdős and Alféd Renyi introduce the traditional random graph theory, which has been widely used to describe many natural and artificial networks. This was the second stage of evolution in network science. In this approach, a network with N vertices is modelled by just starting with N disconnected vertices (no edges) and connecting each pair of vertices with a line with probability pER. This type of network is known as random network and is highly democratic since most nodes will have approximately the same number of links. In their seminal work Erdős and Renyi showed that in their model a vertex having k edges follows the Poisson distribution. Due to the absence of data on large networks, the predictions of ER theory were rarely tested in the real world and hence have been widely used to describe and study real world networks.
However with the help of computers for data acquisition and high computing power that came into existence during the past few years, scientists have found that most real-world networks lie between the limit of order and randomness. With this observation gave birth to the third stage of network modelling. Many of these networks form “complex networks” where the difficulties in describing them lie partly in their topology. A few examples of complex networks are the nervous system, genetic network and the world-wide web (WWW).
Using the fact that real world network lie in between of locally ordered system and random network, Watts and Strogatz introduced a simple model of network which consists of a one-dimensional regular lattice of N vertices with bonds between the nearest and next-nearest neighbours and a periodic boundary condition. Then one end of each bond is rewired by shifting it to a new vertex chosen at random from the whole network with probability pws with the restriction that no vertex can be bonded to itself and no two vertices can have more than one bond. One problem with this model is that it is built on a low-dimensional regular lattice, and little justification are to be found in empirical studies of social networks for such an underlying structure.
In both models discussed so far, the number of nodes is fixed and each node has approximately the same amount of links. In 1998 Barabási and co-workers embarked on a project to map the connectivity distribution of the World Wide Web. Their result was rather surprising since they found that the probability pk that a webpage in the WWW has k links decays as a power-law instead of the Poisson distribution of the random network.
The same type of degree distribution has been found in many real world networks such as the network of scientific papers, network of movie-actor collaborations, physical structure of the internet, social network.
Power law degree distribution decays much more slowly than a Poisson distribution thus allowing few highly connected nodes known as hub to occur and dominate connectivity in the system. It also indicates that large network self-organised itself into a scale-free state. Hubs are forbidden in random network. A number of real world networks are scale-free and show striking robustness against random breakdowns. In the past few years researchers developed a variety of techniques and models to help us understand or predict the behavior of real world networks.
We review some developments in the field of networks with emphasis on dynamical processes like flow and epidemic propagation on scale-free networks.