Lecture Notes on Complex Network Theory

I. INTRODUCTION

The terminology scale-free network and complex network albeit relatively new they are actually
deeply rooted to the more than two centuries old graph theory. The first work on graph theory
can be traced back to the Konigsberg’s seven bridge problem. This problem involved the question
whether it was possible to make a walk crossing exactly once each of the seven bridges built to
connect the two island and its shores across the river Pregel. In 1735 Leonard Eular solved it by
mapping it as an abstract graph which in general is comprised of a set of nodes or vertices connected
by a set of links or edges where the spatial distance between nodes are totally disregarded. It was
eventually developed as an active subject of discrete mathematics contributed by many famous
mathematicians like Cauchy, Hamilton, Cayley, Kirchhoff and others who dealt with graphs those
were highly ordered and deterministic. However, the graph theory that began with the work of
Euler witnessed a paradigm shift in 1959 with the seminal work of two mathematicians Paul Erdös
and Alfred Rényi who proposed a simple model to generate random graph.
The modern theory of networks has its root also in literature and sociology. Hungarian writer
Frigyes Karinthy is believed to be the first person who conceived the idea that any two person
picked at random in the world can be linked by a chain of six acquaintances on average. This is
highly counter-intuitive and at the same time intriguing as it suggests that despite the enormous
size of the human population in the world we live in, which can be mapped as a graph comprising
six billion nodes, we can navigate through it following social links where any pair of nodes are on
the average only six links away from each other. Later Harvard professor and sociologist Stanley
Milgram performed a bizarre experiment which gave Karinthy’s idea of six degrees of separation
a scientific footings. Though, neither Karinthy nor Milgram were even remotely aware of the
connection of their work to the graph theory in mathematics nor mathematicians were aware of
such development in disciplines so far away from mathematics.
The real breakthrough of the graph theory was, however, made only recently when physicists
started relating the problem for the first time with the empirical data on real-world systems.
Thanks to the increased computational power, large data sets can now easily be stored and in-
vestigated, which has profound impact in the empirical studies on large networks. To this end,
two groups of scientists in a span of two years, 1998-1999, published two seminal papers in two
influential journals one in the Nature by Watts and Strogatz and the other in the Science by Reka
 2

Albert and Lazlo Barabasi. The two works have revolutionized the notion of the graph theory by
adding two new terminologies small-world network and scale-free network which have seen immedi-
ate success. New names and new findings, that many real networks although seemingly disparate
share fascinating features, have attracted physicists, mathematicians and computer scientists all
alike. This resulted in a surge of research activities under the name complex network. The number
of articles published since 1998 will provide a clear testament to this. As a result the complex
network theory developed as almost a full grown subject within a remarkably short space of time.
The modern theory of complex network helped recognizing the fact that the world we live
in is dominated by complex systems much of which can be described as interwoven web of large
networks. For example, cells of all living systems form huge network of molecules linked by chemical
interaction, the Internet is a large network of routers linked by wireless and cable connection,
WWW is an immense network of web documents linked by URL address, power-grid is a network
of substations linked by transmission lines, and individuals in social networks are linked by co-
authorships, scientific collaboration, co-starring the same movie, friendships, and professional ties
etc. The intricate wiring pattern of human brain and how these gives rise to normal and disturbed
brain perhaps can be best understood if brain is regarded as network of neurons linked by axons.
Appreciating the human brain as network has immediate impact in qualifying the worst and the
better brain. For instance, the worst brain is the one in which each neuron is linked to the same
number of a few other neurons. On the other hand, the higher the degree of heterogeneity, the
better the brain functions.
As a physicists, we all are familier with Bravais lattice, honeycomb lattice, Bethe lattice etc.
These lattices play a fundamental role in solid state physics which are taught in one of the core
course of the undergraduate physics curriculum. They are characterized by a set of symmetry
operations such as translational, rotational, mirror reflections etc. The dual of these lattices,
obtained by replacing each unit cell with a node at their centers and common border between cells
with a link or edge between the corresponding nodes, are regular graph or network which share some
common features. There are phenomena like spread of biological and computer viruses, rumors,
opinion, information etc which do not spread through regular graph or network. Prior to 1998,
models for such spreading phenomena could only apply on a regular lattice whose dual is a regular
graph though the real systems are inherently heterogeneous in the sense that each node do not have
the same number of links or edges instead they have great many different number of links or egdes.
Clearly, the topology of network will have great influence on the overall dynamics of spreading in the
network. Breakthrough development of the network theory over the last decade led to appreciate
 3

FIG. 1: A mineature of network is shown to give a flavour of what network is!

the fact that many social, biological and communication systems not only heterogeneaous or scale-
free to be more precise but also possess small-world properties. Besides, network which have nodes
spatially embedded can be a better candidate to mimic systems through which spreading occurs.
There is thus exist a strong demand for planar lattice whose dual is a scale-free network and at
the same time possesses small-world properties.

II. WHAT IS NETWORK

In general network in the present context is a simple or intricate wiring of a set of nodes or
vertices by links or edges. Recently, much of the activities on network theory focusing primarily
on complex network. So we first need to know what do we mean complex system. Complex
systems typically comprise of a large number of components, building blocks or agent which are
capable of interacting with each other that results in a self-organization into a state which have an
emergent behaviour. In addition to this complex network also have non-trivial topological features
in the sense that the wiring patterns resulted from the connection between their constituents are
neither regular nor random in character. Nodes in the complex network may represent neurons of
brain, molecules of cells of living animals, individuals of society, computer or router of Internet,
web-documents of WWW, power-stations of power-grid etc and corresponding links or edges may
represent axons, chemical reactions, friendships or professional ties, cable or wireless connections,
URL addresses, transmission lines etc. In the language of network spatial distance between nodes
are disregarded as their distances measured in units of the minimum number of links or edges
 4

needed to connect the two nodes. To illustrate the idea a mineature of a network is given in Fig.
().
Typically, in network theory each and every node in the network is treated as identical entity
although they may be different in terms of the number of other nodes they are connected or
linked with. There are different types of network. For instance, there are directed or undirected
network, weighted or unweighted network, static or evolving network etc. In directed network edges
have direction or arrow and in such a cases the resulting network is known as directed network.
The direction of the link is crucial in many cases especially in the spread of information or in
synchronization. In this chapter we, however, will consider only the undirected network without loss
of generality. The capacity or importance of the relationship between nodes may be heterogeneaous
and in such cases networks are known as weighted network. Again, the weight or the extent of
importance of links plays significant role in spreading of information and in synchronization for
instance. On the other hand network with two kind of nodes where links exist only between nodes
of unlike kind are called bipartite network. Also there are static in the sense that their structure
do not change while there are which may not be static rather evolve with time. In this chapter we
will discuss the importance of the later case and treat such kind at length.

III. OBSERVABLE

A. Tree network and Complete graph

The first thing to know about the network is whether all the nodes are connected or not. The
dual of the regular lattice obtained by replacing each site with a node at its center and common
border between sites with an edge joining the two corresponding nodes emerges as a regular graph
or network where all the nodes are connected and every node is linked exactly to the same number
other nodes. For a network comprising N nodes requires at least N − 1 edges to construct a
connected graph where no three edges forms a triangle or loop. The network corresponding to the
Bethe lattice is one such example and typically network of this kind are called tree network also
known as sparse graph. On the other hand, a graph comprising N nodes if connected by maximum
N (N − 1)/2 edges without duplication between any pair of nodes and without using edge to self
connection then the resulting network is called complete graph where every node is linked to the
rest of the other nodes in the network.
 5

B. Degree k and degree distribution P (k)

In general, nodes in the network or graph theory are regarded as topologically identical though
they may differ in terms of their importance in the network. The parameter that quantify this
importance is known as the degree k and it is defined for a given node by the number of edges
attached to this node. A node with degree means that it is connected to k other existing nodes
regardless of their spatial positions. The average degree < k > of a network with N nodes linked
by e edges is < k >= 2e/N . A network with N nodes and e edges means that the sum of degrees of
PN
all the nodes i kj = 2e since each edge contribute to two degrees. For dual of the regular lattice
all nodes have the same degree which is not the kind of network we are interested. Instead, we
want to know about networks where nodes have wider variety of degrees distributed statistically.
Such networks are best described by the degree distribution P (k) which is obtained by finding the
fraction of the nodes which have degree k. Thus if there are Nk nodes in a network comprising N
then P (k) = Nk /N . In the case of network which have nodes with great many different number of
degrees then one tunes the value of k and obtain a data of P (k) as a function of k. Then plotting
this frequency histogram gives the degree distribution. It also describes the probability that a
node picked at random with equal a priori have degree k Since nodes in the network theory are
considered topologically identical. The nature of degree distribution is one of the major ways of
analyzing networks into different classes.

C. Clustering co-efficient C

Many networks have strong local recurrent connection leading to loops and clusters. Assume
that you have only four good friends which in network language can be said that a node is linked
to four other nodes by four edges. If all the four friends are also friends of each other then it
requires six addition edges. Instead it may happen that a couple of your friends may not be friends
of each other in such case the real count will less than six - let’s say four as depicted in figure.
Then according to Watts and Strogatz your clustering coefficient is 4/6 obtained by taking the
ratio of the number of links that really exist to the potentially maximum number of links that
could exist. It is a normalized measure of loops of length 3. In general, to find the clustering
co-efficient of a node i one first find its nearest neighbpurs which are only a link apart from the
node i which is actually its degree ki . We then find the number of edges ei present among the
ki neighbours of the node i. Note that the maximum value that ei can assume is ki (k− 1)/2 if we
 6

FIG. 2: The red node has four neighbors which are linked among themselves by four edges. If the four
neighbours of the red node were linked by six edges, which is the maximum number of possible edges by
which they could be linked among themselves without self-connection and duplication, then each neighbours
of te red node would also be neighbours of each other other. The clustering coefficient of the red node
therefore is 4/6 = 0.333.

C=0 C=0.5 C=1.0

FIG. 3: Further examples of how clustering coefficients are calculated.

ei
exclude multiple connections and self-connection. The ratio of the two ki (ki −1)/2 therefore can be
regarded as a measure of how closely the neighbours of the node i are connected which is defined
as the clustering coefficient Ci of the node i.
To obtain the clustering co-efficient C of the network of N nodes one need to calculate the
clustering coefficient of each node and then C is obtained by averaging over all the nodes in the
network
N
1 X
C= Ci . (1)
N i

It describes the average fraction of pairs of neighbors of a node that are also neighbors of each
 7

other. In the context of social network facebook it can be articulated as a quantity that quantifies
how likely that friends of a friend are also friends of each other. It has been found in many real-
life networks, especially in social and technological networks, that neighbpours of a node are also
neighbours of each other. There are regular lattices which have non-zero, sometimes even quite
high, clustering coefficient. For instance, the clustering coefficient of the regular 2d triangular
lattice C = 6/15 = 0.4 which clearly reflecting its close knit local neighbourhood structure. In the
case of social network clustering is also known as transitivity that describes how likely that two
friends of a given individual are also friends of one another. Clustering co-efficient is an important
parrameter that helps classifying networks into
Another closely related measure of clustering sometimes also used in the liturature which is
based on the global properties unlike the previous definition which is based on local properties in
the first place then averaged over to obtain the global measure. The clustering coefficient based
on global measure is defined as

3 × number of triangles
C= , (2)
number of connectedtriples

where a conneted triple is a subgraph consisting of three nodes with at least two links between
them. For a complete graph C = 1 and for trees C = 0 because of the absence of links among
neighbours of any node in the network. Both the definitions gives almost the same velues for real
networks and hence one can choose either of the two although we will use only the former definition.
In general, any fully connected subgraph is known as a clique. A clique is a set of nodes for which
(a) every node is connected by an edge to every other member of the clique and (b) no node outside
the clique is connected to all members of the clique. In social network context a clique is a group
of friends where everybody knows everybody else.

D. Mean geodesic (shortest) distance l

Yet another quantity of interest is the average shortest path length or the mean geodesic distance
l that describes the extent at which two nodes communicate with each other. It is defined as follows.
In general the di,j between two nodes labeled as i and j is the minimum number of edges that
connects this two nodes along the shortest path. The average shortest path length of the network
is then is the average of the shortest distance between all pairs of the network

1 1 X
l= dij , (3)
2 N (N − 1)/2 i6=j
 8

where the factor 1/2 is included to avoid the double counting. Astonishingly large networks can
have surprisingly small separation. Another related idea is the diameter D of the network defined
as the largest distance between any two pairs in the network. The mean geodesic path length l is
generally closely related to the diameter D since the length of the shortest path between the most
distanced nodes of a network is the diameter D; it has the same scaling behaviour with N as l.

E. Hubs

The role of every node in the network is not the same. The nodes which are connected to
unusually large number of other nodes compared to extremely large majority of nodes are called
hubs. If you upload a web document it is immediately available to hundreds of millions of people
to view and read. However, do all the web document enjoys the equal chance of viewing? It is the
topological architecture of the web document ultimately who has the better chance than others!

IV. RANDOM NETWORK: ERDOS-RENYI MODEL

The first breakthrough on the graph theory was made by Paul Erdös and Alfred Rényi in 1959.
They for the first time realized that the real-life network must follow non-deterministic rule and
have some degree of disorder. The question they addressed is the following. How nature decides
to establish links between pairs of nodes? It was perhaps the job of physicists to find an answer to
this question. However, there was no physicists working on such problem then. Erdös and Rényi
rather looked at the problem from the mathematicians perspective. Since they did not know how
links are established between pairs of nodes they instead considered the simplest case whereby they
assumed that pairs of nodes are picked at random and links are established with some probability
p. Their model therefore is based on probabilistic approach and it has been proved to be potentially
useful in descrbing real life networks.
In their seminal paper Erdos and Renyi assumed that the model starts with fixed N number
of labeled nodes. Then e number of edges out of N (N − 1)/2 maximum possible edges are added
between pairs of nodes chosen at random avoiding self connection and duplication. It is equivalent
2e
to adding edges with probability p = N (N−1) between pairs of nodes picked at random mentioned

 N (N − 1)/2 
earlier. In total there are   graphs with N nodes linked by e edges which forms a
e
probability space where every realization is equally likely to occur. For graph theory, this means
that, instead of asking for detailed properties of all the possible netwrok in the ensemble we are
 9

asking for average properties or the probability that a network from an ensemble has the probability
Q. Such probabilistic approach is certainly not new when Erdos used it to discrete mathematics.
In fact, by the ned of the 19th century Boltzman, Gibbs and thers had already used in statistical
mechanics to get macroscopic properties from microscopic behavours. There exist an alternative
way to construct random graph which is known as binomial model. In this model every pair of
nodes is connected with an ad-hoc probability p. Consequently, the total number of edges for a
network with a fixed number of nodes N is not fixed rather fluctuate around an expactation value
E(e) = p N (N2−1) which also means that the average degree < k > is a random variable with an
2e
expected value at pN since < k >= N = p(N − 1) ∼ pN for large N .
One question we might ask is: What is the probability that a node picked at random
 will
 have
N −1
degree k? In a random graph where links are added with probability p there are   ways
k
that a given node can choose k other nodes to establish from total of N − 1 other nodes and
 links 
N −1 k
pk is the probability that they will have edges. Thus   p is the probability that the node
k
in question is attached exactly to k other nodes and at the same time there must be no links with
the rest of the N − 1 − k other nodes which occurs with probability (1 − p)N −1−k . Thus the degree
distribution of the random graph is
 
N −1 k N −1−k
P (k) =   p (1 − p) , (4)
k

which for large N it becomes a Poisson distribution

e−<k> < k >k
P (k) ∼ , (5)
k!
with < k >∼ pN . The tails of this distribution falls off slightly faster than an exponential since
roughly P (k) ∼ e−k ln k . Such fast fall of means that it is alsmot impossible to find nodes which
have significantly gigher or ferwer degree than the average.
Random graph within the ER model tend to have small average path length provided p is
greater than 1/N . With such large probability the number of nodes at a distance l is not much
less than < k >l nodes. Equating this < k >l = N we can immediately get as estimate mean path
length
ln N
l∼ . (6)
ln < k >
On the other hand, if consider clustering of nodel in a random network and its first neighbors,
the probability that two of these neighbors are connected is equal with the probability that two
 10

randomly selected nodes are connected by an edge. Consequently the clustering coefficient of the
random graph is

<k>
C = p ∼= , (7)
N

and hence the clustering coefficient decays like

1
C∼ . (8)
N

So, how do a regular lattice and a random graph comprising the same number of nodes and edges
compare? Riughly speaking the size of a d-dimensional lattice will grow with number of site N as
l ∼ N 1/d where the size of the ER network grows much slower than this since we find l ∼ ln N .
However, the clustering coefficient of the regular lattice is independent of size while it is in the ER
network decays as C ∼ 1/N .

V. SMALL-WORLD NETWORK

At least priror to 1929 netowrk theory under the name graph theory have been studied only by
mathematician. However, in 1929 the Hungarian writer Frigyes Karinthy conceived a remarkable
idea which became an integral part in the development of the small-world phenomena. He wrote in
his book ”Chain” that any two persons among Earth’s all the inhabitant can be linked by a chain of
six acquaintances whom they know personally. It is perhaps quite safe to say that Karinthy had no
idea of what mathematecians were doing in the name of graph theory. Neither Stanley Milgram,
a Harvard professor of sociology who did a bizzare experiment to find out that indeed any two
person are on average only six links from each other, had any idea of graph theory. Karithy’s idea
and Milgram’s experiment led to conclude that the world we live in is topologically small though
it large both in terms of population and spatial size. We often travel to distant places where we
hardly expect to meet someone we know. Yet in rare occassions we may meet a friend, neighbour
or someone who we know by first name in quite a remote place and we exclaim: ”This is a small
world”! Things are even interesting when we meet a stranger in the Sundarbon (home of royal
Bengal tiger) and after a little chat we discover that we have a common friend and we exclaim:
”What a small world”! Two scientists who met for the first time in a conference may find upon
little chat they both worked with another scientists with whom they co-authored articles.
Perhaps such small-world phenomena can be better illustrated by Erdos or Bacon numbers.
Kevin Bacon, one of the most famous actor in the Holywood, played in many movies with great
 11

many different actors. All these actors who appeared in the same film as Kavin Bacon can be
characterized Bacon number one, Bacon number two if an actor appeared in the same film with
Bacon number one etc. So, the Bacon number of an actor or actress is the number of degrees of
separation they have from the actor Kevin Bacon. If actors are regarded as node and appearing
in the same film as an actor or actress is regarded as a link then the higher the Bacon number
the further away the actor is from Kevin Bacon. The Bacon game with the Holywood actor
network shows that avera paths langth l between actors are surprisingly short. A similar kind
of process in scientific arena is associated with the legendary mathematician Paul Erdos who
published more than 1500 scientific papers with 458 collaborators The nodes are mathematicians
and all the 458 collaborators have Erdos number one as they co-authored a paper with Erdos and
4500 mathematicians have Erdos number two if they coauthored with Erdos number one and so
on. Interestingly, it turns out that majority of scientists who published research articles in the last
65 years or so have surprisingly small Erdos numbers.
It is well known the psyshologist Milgram carried out a bizzare experiment for the first time in
an attempt to find the distance between two randomly chosen American citizens which is defined
as the number of acquaintances needed to connect the two individuals. To this end, Milgram in
1967 asked people in Omaha, Nebraska and Wichita, Kansas to send packets to one of two people
in Cambridge, Massachusetts specified by name, profession and rough location only. However,
instruction was that packets were to be passed only between people who know each other by first
name. In this way he hoped to map the social network of friends. The result was quite counter
intuitive in the sense that most of packets arrived at correct person after passing through about
five intermediaries. This is much smaller than one would expect considering the physical distance
between the original sender and the final destination who did not know each other in any social
sense. In fact, this led to the idea fo small world in the sense that any two pweron in the world is no
more than a few acquanitances away. In terms of networks, nodes are people and edges represents
links between people who knows each other by first name terms.
The underlying idea behind all these examples are that social network has small distance be-
tween any pair of nodes on the average and have lot of local structure in the sense that neighbours
of a node are likely to be linked as well which is quantified by the clustering coefficient. However,
for a network corresponding to dual of the regular lattice l and C are both large, while for a ER
network they are both smaller than required. This poses a question: Is there a network model for
some given number of nodes N and edges e has the local structure of lattice (high clustering coef-
ficient C) and the mean path length as small as predicted by the ER network? This is significant
 12

especially in the context of social network since friend of my friends are also likely to be friend
of each other. So, neither the regular lattice nor the random network have both the properties,
small path length and large clustering coefficient, in common. This is where the work of Watts
and Strogatz through their seminal paper of 1998 (published in influential journal Nature) comes
in.

A. Watts and Strogatz model

D. J. Watts and H. J. Strogatz in 1998 introduced a new type of graph which is intermediate
between regular and random graph. Though the definition of the model is trivially simple yet its
results have far reaching consequence. The starting point of their model is a regular ring lattice,
for mimicing the fact people in society like to live in circle, where each of the total N sites is linked
to four neighbours (i.e., in addition to two nearest neighbours, inherent next nearest neighbours
are also linked by an edge) which requires altogether e = 2N edges. They then rewired each of
the e = 2N edges with probability p between randomly chosen pair of sites in turn. Thus at p = 0
we have original regular lattice in one end and in other end at p = 1 we have random graph.
For intermediate values 0 < p < 1, we migh expect a hybrid of these features with clustering
coefficient and mean path length drop together as we increase p. To our surprise, the drop of
l ∼ N to l ∼ ln N is due to shortcuts made by reqiring of 2pN edges on the average bring together
previously distant sites. However, the high value of clustering coefficient is hardly affected by the
rewiring. Thus the model essentially makes emergence of both the properties of social networks in
the sense that already for small values of p the graph exhibits small mean path length l ∼ ln N
as in random graph and constant clustering coefficient similar to regular graph. The logic behind
these are easy to understand qualitatively. For instance, after a first few rewirings the average of
C will be reduced in proportion to 2pN , however, rewiring an edge of an original regular lattice is
likely to create a shortcut which drastically reduce the mean path length. The WS model layed
the scientific foundation behind the small-world phenomena which caused a surge of activities.
Watts and Strogatz through their simple model showed that randomly rewiring of even a tiny
fraction of total edges of a regular network with high clustering coefficient C cause a drastic reduc-
tion in the geodesic distance l while it is still being highly clustered. It embodoes the intuitative
idea of small-world phenomena. The six degree of separation has become an integral part of the
small-world phenomena for historical reason though it does not mean that network of different na-
ture will also have the same number to call it a small-world. It is the small-ness in geodesic distance
 13

l albeit large network size and high clustering coefficient counts in defining small-world network. In
support of their simple model Watts and Strogatz showed using empirical data of neural network,
collaboration network and power-grid systems of western united states that these are small-world
in charater. Their results convinced them to suggest that similar small-world properties probably
would turn out to be true for many large real-world and man-made networks. This prediction has
subsequently been confirmed in a very wide variety of networks studied in a great many different
disciplines. Furthermore, the revival of small-world theory commenced with Watts and Strogatz
model resulted in an avalanche of research not only into small-world networks but also into under-
lying topological and dynamical principles of complex networks in general. Mathematically, the
smallness is characterized by the logarithmic or slower gorwth of l with network size N and hence
a network that obeys l ∼ ln N and have high and size independent clustering coefficient is called
small-world.

VI. SCALE-FREE COMPLEX NETWORK

The advent in recent years of inexpensive computer power has raised our ability to store and
investigate large scale database. It has profound impact in the empirical studies of nontraditional,
seemingly unrelated real-life networks that span wide specturm of dicispline. As we have already
mentioned that there are three measures used in classifying networks and these are mean geodesic
distance, clustering coefficient and degree distribution. It has been found that the majority of the
real-life networks have three striking characteristic features in common.

(i) High and size independent clustering coefficient C.

(ii) Small mean geodesic distance l albeit huge size and grow logarithmically slower than the
power-law with the network size N .

(iii) Power-law degree distribution P (k) sharing with exponent more or less the same.

There are many examples though below we cite only a few.

A. The World Wide Web (WWW)

The interest in the network aspect of WWW has boomed soon after it has been discovered
that the degree distribution of web pages follow power-law over several orders of magnitude with
 14

exponent between two and three. Here web pages are regarded as nodes and hyperlinks that point
from one document to another as edges.

B. The Internet

Internet is the network of physical links between computers and routers and the edges are phys-
ical or wireless links between them. Again, there were several empirical studies shows emergence
of power-law degree distribution. Besides clustering co-efficients are found finite and independent
of networks size.

C. Movie actor collaboration network

The movie collaboration network actors are regarded as nodes and the two nodes have a common
edge if the corresponding actors or actress have played in the same film together. The average path
length is close to a random graph with the same size though clustering coefficient is quite high like
in the regular lattice. On the other hand, the degree distribution are found to exhibits power-law
with exponent around 2.3.

D. Scientific collaboration network

In this case the nodes are the scientists and two nodes are linked if the two scientists have written
an article together. There are several studies spanning physics, biomedical research, high-energy
physics and computer science. All these networks show small astonishingly small mean geodesic
distance but high clustering coefficient. The degree distribution on other other hand are found to
exhibits power-law type.
We have seen that the WS model can describe two of the three characteristic features of the
real-world networks, namely, the small average path length and high clustering coefficient. These
two properties are also known as the benchmark of the small-world phenomena as they embody
the highly counter-intuitive idea that we are all only six links of acquaintance away from everyone
else on the planet which was proved experimentally by S. Milgram. On the other hand the ER
model can provide explanations for the small l as it scales logarithmically with the network size N
however it can neither capture the high clustering coefficient nor the power-law degree distribution.
The missing key point that neither the ER model nor the WS model could capture is the existence
of hubs in the sense that there are some nodes in these network which are linked to surprisingly
 15

high number of other nodes. They are special as they dominate in determining the nature of the
network making it behave like small world.
Dominance of a few over massively many is one of the common feature found in many network.
Indeed, nodes with unusually large number of links helps reducing geodesic distance between any
pair of nodes in the system. If it is about spreading of biological or computer viruse they can be
regarded as the super spreader. Think of nobel laureate professor Muhammad Yunus, the father
of micro-credit, who plays a dominant role in determining the fate of a millions of poor people
of Bangladesh. In the context of social network the geodesic distance between a person picked at
random in a remote area of Bangladesh and the president of the United States of America can
often be found within four or five links at most owing to the role of Professor Mohammad Younus
as hub. from each other which is very small in number thanks to the yahoo or google dot com
as they can be reached from most web documents in two to three clicks. The question is: What
mechanism is responsible for generating the hubs in the network?

VII. BARABASI-ALBERT MODEL

More often than not there is a story behind every successful model and Barabasi-Albert model
is no difference. Berabasi himself described it in one of his book ”Linked”. I have been teaching
this model for the last couple of years and each time I tell to my student how it came into being it
seems they like it very much. The first pillar was laid when Barabasi and his group wrote an article
about the role of power-laws on the network of web document. Soon after they finished writing
the manuscript Barabasi left for Porto to attend a workshop on non-equilibrium and dynamical
systems. While attending talks he could not help but thinking on two unresolved questions: Is
there any underlying mechanism behind the emergence of a few hubs in the network of billion of
web documents? Why do the network of web documents exhibit power-law? It was interesting to
note that web was the only network then which was found to exhibit power-law. The second piller
they laid by realizing the fact that they need to learn more about the structure of other real-life or
man-made networks. To this end, Barabasi contacted Duncan Watts and a few other who supplied
him of database of the power-grid of the western United States and the Holywood Movie actors.
Upon receiving those data he passed them to his graduate student Reka Albert to analyze them.
A few days after Barabasi received a long mail with a short note from Reka Albert to tell him that
she found power-law degree distribution at least near the tail in all the systems she was given data
to analyze. With this mail it became amply clear to him that network of web document was by
 16

Preferentially Chosen Vertices

New Vertex

FIG. 4: Schematic descrition of the Barabasi-Albert model.

no means special rather it was merely one of many. After receiving this mail Barabasi attended
talks but paying no attention to what they were talking about since he was overwhelmed with the
thought of the implication this finding might have.
Barabasi realized that if two networks as disparate as the web and the Movie actors of Hollywood
yet both display power-law degree distribution then there must eixist some underlying common
mechansims. In a desparate attempt he decided to withdraw from the crowed of the workshop
in search of a quiet place. He took a walk back to the place where they were housed and while
wlaking back to the room he found a potential explanation for the findings. However, he was at
the same time skeptical whether the idea, which was born during the fifteen-minute walk back to
the room, would work since he thought the idea was far too simple and straghtforward. He realized
that the real-life networks are not static rather they grow with time by addition of new nodes. He
also realized the fact that new nodes establish links with the existing nodes by picking them with
probability proportional to the number of links they already have with other nodes. That is nodes
which are rich in degree are more likely to gain more by establishing links with the new nodes
which is now well known as the preferential attachment (PA) rule. He then asked Reka to verify
his idea by simulating it in the computer. A few hours later Reka replied back to tell him that the
idea of growing network along with rich get richer phenomenon work which can indeed be spotted
in many network.
Indeed real networks are open and they are formed by continuous addition of new nodes which
is in sharp contrast to the then existing models. For instance, random network model by Erdos and
Renyi and the small-world network model by Watts and Strogatz both assumed number of nodes
 17

1 4

3 5
1 1 7 9
0 5 2 10 10 1

FIG. 5: Schematic description of how preferential attachement rule works. A random number R within [0, 1]
is generated and if R is within [0, 1/5] then node 1 is picked, if on the other hand R ∈ [1/5, 1/2] then node
2, if R ∈ [1/2, 7/10] node 3, if R ∈ [7/10, 9/10] pick node 4 else node 5.

in the system remain fixed throughout the network generation process. Secondly, both random
and small-world graph assumes unform probabilities as far as establishing new links are concerned
which is not realistic either. Intuitively, a new document is more likely to have a link with popular
wab pages which already have many links to make the former more visible over others, a new
article is more likely to cite an already well-known article to make the former more popular and
accessible than the other, potential new actor would very much like to appear in a film with already
famous and well-established actors in an attempt to get more offers to act in new movies. One
can immediately recognize the presence of the rich get richer phenomenon in all the examples
mentioned above. It is this that has not been taken care of by neither models we discussed so far.
Incorporating both the ingredients, growth and PA rule, Barabási and Albert (BA) then proposed
a simple analytical model and showed that this new class of networks self-organizes into a power-
law degree distribution P (k) ∼ k −γ with γ = 3 which has become one of the leading paradigm in
science. It has become one of the leading paradigm in science thanks to its ability to represent
real-world networks occurring in a wide range of disparate systems.
According to the BA model the growth of the network starts with a small number of nodes m0
as seeds which are already linked. Then, at each time step a new node with m < m0 edges is added
to the existing network. Edges of each new node are attached with m different existing nodes by
picking them preferentially with respect to their degree k. For better understanding a schematic
description of the algorithm to pick existing node following preferential attachment rule is given
 18

in figure (). Perhaps the algorithm can provide a better definition of the model than millions of
words. The model starts with an initially undirected graph comprising of a few m0 nodes as seed
and label them as 1, 2, ..., m. The jth step of the algorithm can be stated as follows:

(i) Subdivide an interval of size [0, 1] into (m0 + j − 1) subintervals of size [0, k1 /(m0 + j − 1)],
Pm0 +j−2
[k1 /(m0 + j − 1), (k1 + k2 )/(m0 + j − 1)], ..., [ i=1 ki /(m0 + j − 1), 1] so that they
represent exisiting nodes labelled as 1, 2, ..., (m0 +j −1) which have degree k1 , k2 , ..., Km0 +j−1
respectively.

(ii) Add a new node with m < m0 edges and level it as m0 + j.

(iii) Generate a random number R within the interval [0, 1] and find which of the (m0 + j − 1)
sub-interval contains this R. The corresponding node that it represents, say the pth node,
is picked to mimic the preferential attachment rule. Repeat it m times to pick m distinct
nodes.

(iv) Connect m edges of the new node with m different existing nodes picked in step (iii).

(v) Increase the time by one unit.

(vi) Repeat the steps (i)-(v) over and over again.

That is, the probability that a new node will be connected to an already existing node i is
proportional to its degree ki and hence the degree ki of the node i changes following the dynamical
equation

∂ki ki
= m PN −1 . (9)
∂t j kj

This equation does everything being described by the algorith (i)-(vi) of the BA model. Note that
every time a node is added to the system it adds m edges contributing to the increase of 2m degrees
PN −1
and hence j kj = 2m(t − 1). Solving Eq. (9) in the long time limit and using the fact that
node i is born at time ti with degree m, i.e. ki (ti ) = m, we immediately find that
 t β 1
ki (t) = m with β= . (10)
ti 2

It implies that the degree of a node i depends not only on the progressing time t but also on the
birth time ti .
 19

It is a basic theorem that the cumulative distribution function P (ki (t) ≥ k) is related to the
degree distribution function P (k) via

dP (ki (t) ≥ k)
P (k) = − . (11)
dk

For convenience, istead of considering P (ki (t) ≥ k) we look into

P (ki (t) < k) = 1 − P (ki (t) ≥ k), (12)

in which we can substitute Eq. (10) to get

s
t t
P (ki (t) < k) = P (m < k) = P (ti > m2 2 ), (13)
ti k
t
= 1 − P (ti ≤ m2 2 ).
k

The quantity ti in the above equation is not a random variable since it is the birth time of the ith
node. Note that nodes are added in the network at equal interval of time. It implies that if we
1
want to know the probability that ti ≤ 100 then this is simply 100 × P (ti ) where P (ti ) = m0 +t

which however in the long time limit is P (ti ) ∼ 1t . Using this argument in Eq. (13) we immediately
find that

t 1
P (ki (t) < k) = 1 − m2 . (14)
k2 t

Substituting it in

dP (ki (t) < k)

P (k) = , (15)
dk

gives

P (k) ∼ k −γ , (16)

with γ = 3. The BA model thus successfully reproduces the power-law degree distribution with
exponent very close to those obtained from imperical data. An interesting aspect about the expo-
nent is that it is independent of the m value. That is, the BA network self-organize into a scale-free
state of same kind regardless whether the new nodes join the exsiting network with one, two or
more links. This highly counter intuitive.
Thus the message we learnt from the BA model is that growth and preferential attachment
are the main mechanisms behind the emergence of power-law degree distribution. The evolution
equation for the degree ki given by Eq. (9) and subsequent solution for the degree distribution
 20

2 3
N = 25 × 10
0 N = 50 × 1033
N = 75 × 103
-2 N = 100 × 10

-4
ln(P(k´ ≥k))

-6

-8

-10

-12

-14

-16

-18
0 1 2 3 4 5 6 7 8
ln(k)

FIG. 6: Plots of the cumulative degree distributions CD(k) ≡ P (k 0 ≥ k) is shown for the BA model with
m = 1. The data points are averaged over 500 independent realizations.

is more of a heuristic justification than a rigorous proof. Only the numerical simulation can
be the hard proof of whether the algorithm of the BA model is really the language that the
equation speaks. It is interesting to note that the degree distribution P (k) typically has a long tail
with relatively scarce data points which turns into a fat-tail when we plot P (k) in log-log scale.
This complicates the process of identifying the range over which the power-law holds and hence
estimating the exponent γ. One way of reducing the noise at the tail-end is to plot cumulative
distribution P (k 0 ≥ k) instead of the degree distribution P (k). Note that if P (k) exhibits power-
law so is the cumulative distribution P (k 0 ≥ k) but with exponent exponent one less due to the Eq.
(11). Figure 1 shows that ln(P (k 0 ≥ k)) decays linearly against ln(k) with slope equal to γ − 1 = 2
which is exactly what is being predicted by Eq. (16) except at the tail-end due to finite-size effect.
Furthermore, it shows that the extent of linearity increases as network size N increases revealing
that the sudden fall off near the tail-end is indeed due to finite-size effect.

VIII. MEDIATION-DRIVEN ATTACHMENT MODEL

Needless to mention that the BA model and its findings has resulted in a paradigm shift albeit
it also has a couple of drawbacks. Firstly, the PA rule of the Barabási-Albert (BA) model is too
direct in the sense that it requires each new node to know the degree of every node in the entire
 21

0.07 3
N = 25 × 10
N = 50 × 1033
0.06 N = 100 × 10

0.05

0.04
F(q,t)

0.03

0.02

0.01

0
0 100 200 300 400 500 600 700 800
q

FIG. 7: Generalized degree distributions F (q, t) for m = 1 are shown against q for three different network
size N . In each case data in the graph represent averaged over 500 independent realizations.

network. Networks of scientific interest are often large, hence it is unreasonable to expect that
new nodes join the network with such global knowledge. Secondly, the exponent of the degree
distribution assumes a constant value γ = 3 independent of m while most natural and man-made
networks have exponents 2 ≤ γ ≤ 3. In order to avoid this drawback and to provide models that
describe complex systems in more detail, a few variants of the BA model and other models were
proposed. Examples feature mechanisms like rewiring, aging, ranking, redirection, vertex copying,
duplication etc.
In this section, we present a model in which an incoming node randomly chooses an already
connected node, and then connects itself not with that one but with m neighbors of the chosen node
at random. This idea is reminiscent of the growth of the weighted planar stochastic lattice (WPSL)
in whose dual, existing nodes gain links only if one of its neighbor is picked. Seeing that the dual
of WPSL emerges as a network with power-law degree distribution, we became curious as to what
happens if a graph is grown following a similar rule. We call it the mediation-driven attachment
(MDA) rule since the node that has been picked at random from all the already connected nodes
acts as a mediator for connection between its neighbor and the new node. Such a rule can embody
the preferential attachment process since an already well-connected node has more mediators and
through the mediated attachment process, it can gain even more neighbors. Finding out the extent
 22

of preference in comparison to the PA rule of the BA model forms an important proposition of

this work. There exists a host of networks where the presence of the MDA rule is too obvious. For
instance, while uploading a document to a website or writing a paper, we usually find documents to
link with or papers to cite through mediators. In social networks such as friendships, co-authorship,
Facebook, and movie actor networks, people get to know each other through a mediator or through
a common neighbor. Thus the MDA model can be a good candidate for describing social networks.
The growth of a network starts from a seed which is defined as a minature network consisting
of m0 nodes already connected in an arbitrary fashion. Below we give an exact algorithm of the
model because we think an algorithm can provide a better description of the model than the mere
definition. It goes as follows:

i Choose an already connected node at random with uniform probability and regard it as the
mediator.

ii Pick m of its neighbors also at random with uniform probability.

iii Connect the m edges of the new node with the m neighbors of the mediator.

iv Increase time by one unit.

v Repeat steps (i)-(iv) till the desired network size is achieved.

To illustrate the MDA rule, we consider a seed of m0 = 6 nodes labeled i = 1, 2, ..., 6 (FIG. 7). Now
the question is, what is the probability Π(i) that an already connected node i is finally picked and
the new node connects with it? Say, the node i has degree ki and its ki neighbors, labeled 1, 2, , ki ,
have degrees k1 , k2 , ..., kki respectively. We can reach the node i from each of these ki nodes with
probabilities inverse of their respective degrees, and each of the ki nodes can be picked at random
with probability 1/N . We can therefore write
Pki 1
1h1 1 1 i j=1 kj
Π(i) = + ++ = . (17)
N k1 k2 kki N

Numerical simulation suggests that the probabilities Π(i) are always normalized, i.e.
PN Pki 1
i=1 j=1 kj = N.
The basic idea of the MDA rule is not completely new as either this or models similar to this can
be found in a few earlier works, albeit their approach, ensuing analysis and their results are different
from ours. For instance, Saramäki and Kaski presented a random-walk based model where a walker
first lands on an already connected node at random and then takes a random walk. The new node
 23

then connects itself to the node where the walker finally reaches after l steps. Our model will
look exactly the same as the Saramäki-Kaski (SK) model only if the new node arrives with m = 1
edge and the walker takes l = 1 random step. However, they proved that the expression for the
attachment probability of their model is exactly the same as that of the BA model independently
of the value of m and l. Our exact expression for the attachment probability given by Eq. (17)
suggests that it does not coincide with the BA model at all, especially for m = 1 case. On the other
hand, the model proposed by Boccaletti et al. may appear similar to ours, but it markedly differs
on closer look. The incoming nodes in their model has the option of connecting to the mediator
along with its neighbors. Nevertheless, in has been shown by Saramäki and Kaski and Boccaletti
et al. that the exponent γ = 3 independent of the value of m, which is again far from what this
MDA model entails.
As far as the definition of the MDA model is concerned, it is exactly the same as the one recently
studied by Yang et al.. They too gave a form for Π(i) and resorted to mean-field approximation
[? ]. However, the nature of their expressions are significantly different from ours, and we have
justified our version of the mean-field approximation on a deeper level by drawing conclusions from
our study of the inverse of the harmonic mean of degrees of the neighbors of each and every node
in our simulated networks. We shall see below that their results, both by mean-field approximation
and numerical simulation, do not agree with our findings. Yet another closely related model is the
Growing Network with Redirection (GNR) model presented by Gabel, Krapivsky and Redner where
at each time step a new node either attaches to a randomly chosen target node with probability
1−r, or to the parent of the target with probability r [? ]. The GNR model with r = 1 may appear
similar to our model. However, it should be noted that unlike the GNR model, the MDA model
is for undirected networks, and that the new link can connect with any neighbor of the mediator-
parent or not. One more difference is that, in our model new node may join the existing network
with m edges and they considered m = 1 case only. We shall show that the role of m in this model
is crucial.

A. Mean-field approximation

The rate at which an arbitrary node i gains links is given by

∂ki
= m Π(i) (18)
∂t
 24

The factor m takes care of the fact that any of the m links of the newcomer may connect with the
node i. Solving Eq. eq:2 when Π(i) is given by Eq. eq:1 seems quite a formidable task unless we
can simplify it. To this end, we find it convenient to re-write Eq. eq:1 as
Pki 1
ki j=1 kj
Π(i) = . (19)
N ki
Pki 1
j=1 kj
The factor ki is the inverse of the harmonic mean (IHM) of degrees of the ki neighbors
of a node i. We performed extensive numerical simulation to find out the nature of the IHM
value of each node. We find that for small m (roughly m < 14), their values fluctuate so wildly
that the mean of the IHM values over the entire network bears no meaning. It can be seen from
the frequency distributions of the IHM values shown in FIG. 12. However, as m increases beyond
m = 14 the frequency distributions gradually become more symmetric and the fluctuations occur at
increasingly lesser extents, and hence the meaning of the mean IHM seems to be more meaningful.
Also interesting is the fact that for a given m we find that the mean IHM value in the large N
limit becomes constant which is demonstrated in FIG. 13.
The two factors that the mean of the IHM is meaningful and it is independent of N implies
that we can apply the mean-field approximation (MFA). That is, within this approximation we
can replace the true IHM value of each node by their mean. In this way, all the information on
correlations in the fluctuations is lost. The good thing is that it makes the problem analytically
tractable. One immediate consequence of it is that the MDA rule with m > 14, like the BA model,
is preferential in character since we get Π(i) ∝ ki . It implies that the higher the links (degree) a
node has, the higher its chance of gaining more links since they can be reached in a larger number of
ways through mediators which essentially embodies the intuitive idea of rich get richer mechanism.
Therefore, the MDA network can be seen to follow the PA rule but in disguise. Moreover, for small
m the MFA is no longer valid. We shall see below that for small m the attachment probability is
in fact superpreferential in character.

B. Degree and Rank-Size Distribution

It is noteworthy that the size N of the network is an indicative of time t since we assume that
only one node joins the network at each time step. Thus, for N >> m0 we can write N ∼ t. Using
this, Eq. eq:npi, and MFA in Eq. eq:2, we find the rate equation in a form that is easy to solve,
which is
∂ki β(m)
= ki . (20)
∂t t
 25

Here we assumed that the mean IHM is equal to β(m)/m for large m where the factor m in the
denominator is introduced for future convenience. Solving the above rate equation subject to the
initial condition that the ith node is born at time t = ti with ki (ti ) = m gives,
 t β(m)
ki (t) = m . (21)
ti

As the FIG. (8) shows, the numerical results are in good agreement with this growth law for ki (t).
Note that the solution for ki (t) is exactly the same as that of the BA model except the fact that
the numerical value of the exponent β(m) is different and depends on m. We, therefore, can
immediately write the solution for the degree distribution

1
P (k) ∼ k −γ(m) , where γ(m) = + 1. (22)
β(m)

The most immediate difference of this result from that of the BA model is that the exponent γ
depends on m.

i=1
14 i=4
i = 10
i = 11
i = 13

12

10
ln(ki)

8
1

0.9

6 0.8
β

0.7

0.6
4
0.5
0 100 200 300 400 500
m
2
5 6 7 8 9 10 11 12 13 14 15
ln(t)

FIG. 8: Plots of ln(ki ) versus ln(t) for 5 nodes added at five different times for m = 2. In the inset, we show
variation of the slope β with m.

To verify Eq. (22) we plot ln(P (k)) vs. ln(k) in FIG. (9) using data extracted from numerical
simulation. In all cases, we find straight lines with characteristic fat-tail which confirms that
our analytical solution is in agreement with the numerical solution. It is important to note that,
for small m, especially for m = 1 and 2, there is one point in each of the ln(P (k)) vs. ln(k)
 26

0
3

-2 2.8
2.6

-4 2.4

γ
2.2
-6 2
1.8
ln(P(k))

-8 1.6
0 20 40 60 80 100
m
-10

-12

-14

-16 m=1
m = 15
m = 100
0 2 4 6 8 10 12
ln(k)

FIG. 9: Plots of ln(P (k)) vs ln(k) for m = 1, m = 15 and m = 100 revealing that the MDA rule gives rise
to power-law degree distribution. In the inset we show the variation in the exponent γ as a function of m.

plots that stands out alone. These special points correspond to P (k = 1) ≈ 99.5% for m = 1,
and P (k = 2) ≈ 95.4% for m = 2. This implies that almost 99.5% and 95.4% of all already
connected nodes are held together by a few hubs and super-hubs for m = 1 and 2 respectively.
This huge percentage of nodes are minimally connected and this embodies the intuitive idea of
WTA phenomenon. We find that as m increases, this percentage decreases and roughly at about
m = 14, all the data points follow the same smooth trend revealing a transition from the WTA
effect to the WTS effect. This happens when the IHM has less noise and the mean of IHM becomes
increasingly more meaningful. The IHM value can thus be regarded as a measure of the extent up
to which the degree distribution follows power-law. In their GNR model with enhanced redirection
mechanisms, Gabel, Krapivsky and Redner also noticed such highly dispersed networks which tend
to be dominated by one or a few high-degree nodes.
It is interesting to note that the exponent γ of the degree distribution increases with increasing
m. We used gnuplot to fit the function g(x) = P (1 − Qe−Rx ) to the γ versus m data and find that
the data satisfies the relation γ(m) ≈ 2.97457(1 − 0.449478e−0.110688m ) quite well. The asymptotic
standard errors in the values of P , Q, and R are ±0.01757, ±0.01407, and ±0.007378 respectively.
This result stands in sharp contrast with that of Yang et al. who found the exponent γ to vary in
the range from 1.90 to 2.61. Also, for m = 1, which is the case closest to m = 1 and l = 1 of the SK
 27

[] []
11 9
MDA , m = 2 MDA , m = 100
10 BA , m = 2 8.5 BA , m = 100
9
8
8
7 7.5

ln ( Sr )

ln ( Sr )
6 7
5 6.5
4 6
3
5.5
2
1 5
0 4.5
0 2 4 6 8 10 12 0 2 4 6 8 10 12
ln ( r ) ln ( r )

FIG. 10: (a) To be able to appreciate the contrast between the MDA and BA network we plot the rank-size
distribution ln(Sr ) vs ln(r) for (a) m = 2 (b) m = 100.

model, we found that γ = 1.65480 and not 3. On the other hand, in the large m limit we find γ → 3.
It hints at a possible similarity with the BA model where γ = 3. To find the extent of similarity or
dissimilarity of our model with the BA model, we tuned the values of m and looked at the rank-size
distribution. The rank-size distribution can be found to describe remarkable regularity in many
phenomena including the distribution of city sizes, the sizes of businesses, the frequencies of word
usage, and wealth among individuals. These are all real-world observations where the rank-size
distributions follow power-laws. In our case, we measured the size of each node by its degree, and
the nodes which have the largest degree are given rank 1, the nodes which have the second-largest
degree rank 2, and so on. Assuming Sr to be the size of the nodes having rank r we plotted log(Sr )
vs log(r) in FIG. 10. It clearly reveals that the size distribution of nodes decays with rank following
the Pareto law. Note that, the power-law distribution pattern for the rank-size is often found to
be true only when very small sizes are excluded from the sample. However, our main focus is on
the difference between the BA and the MDA model. Clearly, for small m, the size of the hubs of
an MDA (Sr with small r) network is far more rich than that of a BA network. However, for large
m, the rank distributions of the two networks become almost identical and this is consistent with
the fact that the exponent γ(m) of the MDA network in the large m limit coincides with that of
the BA network.

C. Leadership Persistence

In the growing network not all nodes are equally important. The extent of their importance is
measured by the value of their degree k. Nodes which are linked to an unusually large number of
other nodes, i.e. nodes with exceptionally high k value, are known as hubs. They are special because
their existence make the mean distance, measured in units of the number of links, between nodes
 28

incredibly small thereby playing the key role in spreading rumors, opinions, diseases, computer
viruses etc. [? ]. It is, therefore, important to know the properties of the largest hub, which we
regard as the leader. Like in society, the leadership in a growing network is not permanent. That
is, once a node becomes the leader, it does not mean that it remains the leader ad infinitum. An
interesting question is: how long does the leader retain this leadership property as the network
evolves? To find an answer to this question, we define the leadership persistence probability F (τ )
that a leader retains its leadership for at least up to time τ . Persistence probability has been of
interest in many different systems ranging from coarsening dynamics to fluctuating interfaces or
polymer chains [? ].

(a) (b)
0.0 0.0
m=1 m=1
m = 100 m=100
-3.0 -3.0
ln(P(τ))

ln(P(τ))

-6.0 -6.0

-9.0 -9.0

3 4 5 6 7 8 9 10 11 12 2 4 6 8 10 12
ln(τ) ln(τ)
(c) (d)
2.0

1.5

1.5
θ

1.4

θ =1.530571 - 0.227189 e-0.190926 m θ =1.512599

1.3 1.0
0 20 40 60 80 100 0 20 40 60 80 100
m m

FIG. 11: The two plots at the top reveal the power-law behaviour of the leadership persistence probability.
To appreciate the role of m we give leadership persistence probability for two values (m = 1 and m = 100) in
the same plot: (a) BA networks and (b) MDA networks. The two plots at the bottom are for the persistence
exponent θ as a function of m in (c) BA networks and (d) MDA networks.

We find it worthwhile to look into the leadership persistence probability F (τ ) first in MDA
networks and then in BA networks to see their difference. We perform M = 500 independent
realizations under the same condition and take records of the duration time τ in which leadership
has not changed. The leadership persistence probability F (τ ) is then obtained by finding the
relative frequency of leadership change out of M independent realizations within time τ . The plots
in (a) and (b) of FIG. (11), show log(F (τ )) as a function of log(τ ) for BA and MDA networks
 29

respectively. In each case, we have shown plots for m = 1 and m = 100 to be able to appreciate
the role of m in determining the persistence exponent θ(m). These plots for different m result in
straight lines revealing that persistence probability decays as

F (τ ) ∼ τ −θ(m) . (23)

One of the characteristic features of F (τ ) is that like P (k), it too has a long tail with scarce data
points that results in a ”fat” or ”messy” tail when we plot it in the log-log scale. The persistence
exponent θ carries interesting and useful information about the full history of the dynamics of the
system. Therefore, its prediction is of particular importance. We find that the exponent θ for
MDA networks is almost equal to 1.51 independently of m. On the other hand, in the case of BA
networks, it rises to 1.53 exponentially with m i.e., it depends on m. This is just the opposite
of what happens to the exponent γ of the degree distribution. In many natural and man-made
networks, the leadership is a stochastic variable as it varies with time. For instance, the leader
in the World Wide Web is not static, and hence it would be interesting to see the leadership
persistence properties there. One could also look at such persistence properties in other growing
networks.
1 m=10
m=1 m=14
20000 0.8 m=20
m=50
0.6 m=100
<1/ki>

0.4

15000 0.2

0
0 50000 100000
frequency

node index, i
0.01
m = 100
10000 0.008

0.006
<1/ki>

0.004

5000 0.002

0
0 50000 100000
node index, i

0
0 0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1
<1/ki>

FIG. 12: The distribution of IHM for different m values. The fluctuations of IHM of individual nodes is
shown in the inset (top left for m = 1 and bottom right for m = 100).

IX. DYNAMIC SCALING AND UNIVERSILITY

By definition, the BA model describes a time developing phenomenon and hence, besides its
scale-free property, one could also look for its dynamic scaling property. This aspect of the BA
model, however, has never been examined. To this end, we argue that it is not enough to charac-
terize each node in the BA network by their degree k only since their k depends on the time of
 30

-6.5
0.4918

-7

ln(β(m,N) - β(m,∞))
0.4916
-7.5

-8
0.4914

-8.5
β(m,N)

0.4912 -9
11 11.5 12 12.5 13 13.5 14
ln(N)

0.491

0.4908

0.4906
0 200000 400000 600000 800000 1e+06 1.2e+06
N

D E
1
FIG. 13: Plot of m ki ≡ β(m, N ) vs. N for m = 70, and inset showing that β(m, N ) saturates to
β(m, ∞) = 0.490513 algebraically as N −0.62516 .

birth according to Eq. (10). A complete characterization of the nodes in the BA network can be
made by specifying their degree k as well as their respective birth time. We, however, find it highly
instructive to combine the two into a single variable using Eq. (??). That is, the node i at time
t can be characterized by the generalized degree qi (t) = ki tβi . The advantage of using q is that it
depends only on time t since according to Eq. (10) we have

qi (t) ∼ tβ with β = 1/2. (24)

Once nodes are characterized by the generalized degree q then we define the generalized degree
distribution F (q, t) as the probability that a node picked at random has generalized degree q. In
Fig. 2 we have drawn F (q, t) vs q for three different network sizes N and clearly it shows some
remarkable features. For instance, we find that the value of F (q, t) initially increases quite sharply
and then register a sudden and sharp fall to a non-zero value at qc from which it rises again to
a secondary maximum followed by a smooth decrease with a long tail. The value qc , where the
first minimum occurs, increases with the network size N and at the same time both primary and
secondary heights systematically decreases as N increases.
We shall now invoke the idea of the dimensional analysis to show that F (q, t) in the long-time
large-size limit self-organizes into a state where it assumes dynamic scaling form

F (q, t) ∼ tθ φ(q/tz ), (25)

where exponents θ and z are fixed by the dimensional relations [tθ ] = [F ] and [tz ] = [q] respectively,
while φ(ξ) is known as the scaling function. Clearly, there are two governing parameters q and
t and a governed parameter F (q, t) in the problem at hand. However, according to Eq. (??)
 31

12
N = 25 × 103
N = 50 × 103
10 N = 100 × 103

8
2
F(q,t)t /
1

0
0 1 2 3 4 5
q
/t /
1
2

FIG. 14: The same data of Fig. 2 for m = 1 is shown in the self-similar coordinates t1/2 F (q, t) and q/t1/2
and we find that all the three curves of Fig 2 collapsed onto a single universal curve.

the governing parameter q can be expressed in terms of time t alone and hence we can define a
dimensionless governing parameter

q
ξ= , (26)
t1/2

and hence z = 1/2. It means we can express F (q, t) too in terms of time t alone since time t is
chosen to be an independent parameter. Applying the power-monomial law of the dimensional
function of a physical quantity we can write a dimensional relation F (q, t) ∼ tθ where the exponent
θ assumes a value that makes tθ bear the dimension of F (q, t). We can therefore define yet another
dimensionless governed parameter φ as follows

F (q, t)
φ= . (27)
tθ

Now, within a given class one can pass from one unit of measurements to another by changing t,
for instance, by an arbitrary factor leaving the other factor q unchanged. Upon such transition
within the given class the numerical value of the quantity on the right hand side of Eq. (??) must
remain unchanged since the left hand side is a dimensionless quantity.
F (q,t)
We thus find that the quantity tα vis-a-vis φ can at best be a function of another dimen-
sionless quantity ξ given by Eq. (??) since this is the only dimensionless governing parameter. We
 32

14
m=1
m=2
12 m=3

10

8
F(q,t)t1/2

0
0 0.5 1 1.5 2 2.5
q
/t1/2

FIG. 15: The value of F (q, t) for m = 1, 2 and 3 are plotted in the self-similar coordinates. It clearly shows
that universal curve for m = 1 do not collapse with those for m > 1 and hence belong to two different
classes.

can express Eq. (??) as

F (q, t) ∼ tθ φ(q/t1/2 ), (28)

R∞
where the exponent θ is obtained by applying the normalization condition 0 F (q, t)dq = 1 to give
θ = −1/2. We thus finally find that the generalized degree distribution assumes exactly the same
dynamical scaling form as Eq. (26). An interesting aspect of the structure of the dynamic scaling
form given by Eq. (??) is that the distribution function F (q, t) at various moments of time can be
obtained from one another by a similarity transformation

q −→ λ1/2 q, t −→ λt, F −→ λ−1/2 F, (29)

revealing the self-similar nature of the function F (q, t).

The question is: How do we verify Eq. (28) using the data extracted from numerical simulation?
The best way of verifying it is to invoke the idea of data-collapse. Note that according to Eqs.
(26) and (??) the quantities t1/2 F (q, t) and φ(q/t1/2 ) are both dimensionless and hence the data of
F (q, t) for various network size N should collapse on a single universal curve if we plot t1/2 F (q, t)
against q/t1/2 which are known as the self-similar coordinates. In Fig. 3 we have drawn the scaled
generalized degree distribution t1/2 F (q, t) as a function of scaled generalized degree q/t1/2 for three
 33

4
m=1
m=2
2 m=3

-2
ln(F(q,t)t1/2)

-4

-6

-8

-10

-12
-5 -4 -3 -2 -1 0 1 2 3
q
ln( /t1/2)

FIG. 16: Plots of ln(t1/2 F (q, t) vs ln(q/t1/2 ) for m = 1 and m > 1. It shows that the scaling functions φ(ξ)
in both cases grow obeying power-law until q/t1/2 < 1 but with exponent 2 and 2.9 for m = 1 and m > 1
respectively.

different network sizes N considering m = 1 in each case and find that all the distinct curves of
Fig. 2 merge superbly onto a single curve as expected. It clearly well confirms the validity of the
dynamic scaling. The first discontinuity in Fig. 3 occurs at q/t1/2 = 1 and the second discontinuity
at q/t1/2 = 2 and both are quite sharp. A careful observation also reveals that there exists a third
discontinuity at q/t1/2 = 3 which seems quite weak and hard to notice. Now the question is: What
if nodes arrive in the BA network with more than one edges (m > 1)? Below, we attempt to give
an answer to this question.
According to our dimensional analysis it is expected that the data points for the BA network
that grow by sequential addition of a node with multiple edges (m > 1) should also lie on the
same curve as the ones for single edge (m = 1) unless they are fundamentally different in some
subtle way which the ordinary degree distribution P (k) fail to differentiate. Surprisingly, we find
that the data points of t1/2 F (q, t) for m = 2, 3, 4 etc. do collapse on a single curve if plotted
against q/t1/2 but do not coincide with the one for m = 1 (see Fig. 4). Although the two distinct
universal curves, one for m = 1 and the other for m > 1, behave qualitatively almost in the similar
fashion they are however quantitatively different. For instance, one noteworthy difference is that
although the first discontinuity occurs at the same point as for m = 1, the second one, however,
 34

4
m=1
m=2
2 m=3

-2
ln(F(q,t)t1/2)

-4

-6

-8

-10

-12
0 2 4 6 8 10 12
q
/t1/2

FIG. 17: Plots of ln(t1/2 F (q, t) as a function of ξ = q/t1/2 for m = 1 and m > 1 which clearly show that
the scaling function φ(ξ) beyond q/t1/2 = 2 and q/t1/2 = 1.5 respectively decay exponentially but with two
different decay constant.

occurs at q/t1/2 = 1.5 for m > 1 while at q/t1/2 = 2 for m = 1. These differences can be even
better appreciated if we plot t1/2 F (q, t) vs q/t1/2 either in the log-log scale or in the log-linear scale
as shown in figures 5 and 6 respectively. Using these figures, we can write the solutions for the
universal scaling function φ(ξ) both for m = 1

 ξ2

if ξ<1
φ(ξ) ∼ , (30)
 e−aξ

if ξ>2

and for m > 1


 ξ 2.9

if ξ<1
φ(ξ) ∼ , (31)
 e−bξ

if ξ > 1.5

where a ≈ 1.4 and b ≈ 2.5.

Beside proving the existence of self-similarity by data-collapse, we have also found that there
are two distinct classes of networks resulting from the BA model. (i) The network that grows
by sequential addition of one node with single edge (m = 1) and (ii) the network that grows by
sequential addition of one node with multiple edges (m > 1). There must be some reasons behind
such behaviour. One apparent difference between the two classes of networks is that the clustering
coefficient CN = 0 if m = 1 and CN 6= 0 rather decays like CN ∼ N −0.75 if m > 1 for network of size
 35

N . Regardless of the value m, the universal scaling function φ(ξ) always suffers two discontinuities
which divide the nodes in the network always into three different classes. For instance, nodes
which have generalized degree q < t1/2 fall into one class, those which have generalized degree
within t1/2 < q < 2t1/2 for m = 1 and t1/2 < q < 1.5t1/2 for m > 1 into another class and finally
those which lie beyond these limits.

X. STOCHASTIC PLANAR LATTICE

Physicists in general love fourteen Bravais lattice and a couple of non-Bravais lattices such as
honeycomb lattice and Bethe lattice. The later two may not be Bravais lattice but have some
degree of symmetry and higly ordered. One thing common to all these lattices is that their dual is
a regular graph as we find that that every node have exactly the same number of links or degree,
constant clustering coefficient C and power-law growth of mean geodesik distance l ∼ N 1/d . They
are so useful that their structural properties are taught to every physics student often in their third
year or sometimes may be in the second year of undergraduate curriculum. The importance of most
of these lattice structures can hardly be exaggerated as we find that lifeless atoms spontaneously
assemble themselves in one of these ordered or less symmetric structure from the disordered or more
gaseous phase as temperature of the system j is lowered. This happens because assembling in such
an ordered state minimizes entropy vis-a-vis the energy of the system. To this end, there are many
models in solid state physics aimed at calculating energy of the system by applying those models
to the above mentioned lattice whose dual is a regular graph. There are, however, numerous
cases where constituents do not ensemble themselves in such an ordered structure where every
constituent interact with exactly the same number of other constituents that makes the systems.
The importance of the systems of this kind can also be hardly exaggerated. The following few
examples will provide a clear testament to this.

• The spread of contagious or infectious disease in a population has been the subject of ex-
tensive studies since it is an important field of investigation that allow us to plan a better
strategy for intervention in order to reduce the burden of an epidemic. This is, of course,
an important issue with regard to the health of the populations of humans and other live
species.

• Rumours are an important form of social communications, and their spreading plays an
amply significant role in a variety of different human affairs. It is so important that it can
 36

shape the public opinion in a country, it can have great impact in financial markets and it
can cause panic in a society during wars and epidemics outbreaks.

• Besides biological viruses there are computer viruses as well which spread through Internet
and can cause serious damage. These are serious issues and attracting much of our attention
these days as the number of internet users increasing at an enormous pace together with
which degree of complexity is as well.

• Forest fire is yet another example which also spread but do not spread through regular and
order systems. This is also an issue scientists are trying to understand and to this end there
are already some models studied extensively.

• Spread of fluids through porous media is an issue physics want to study. To this end,
physicists devised a model called percolation that have been studied extensively due to its
application in various field of natural science.

One thing is common to all these spreading phenomena and that is in real-life systems they
do not spread through regular lattice. The heterogeneous pattern is an inherent property to the
systems through which spreading occur. Indeed, systems through which viruses, information or
rumors spread are inherently heterogeneous in the sense that each node do not have the same
number of links or edges instead they may have great many different number of links or edges.
Clearly, the topology of network will have great influence on the overall dynamics of the epidemic
spreading in the network. Breakthrough development of the network theory over the last decade
led to appreciate the fact that many social, biological and communication systems not only het-
erogeneous or scale-free to be more precise but also possess small-world properties. Besides, nodes
especially in social and technological networks, are spatially embedded and interactions among
nodes usually depends on their spatial distance and location. There is thus exist a strong demand
for a planar lattice whose dual is a scale-free network and at the same time possesses small-world
properties. Our starting point is the square lattice, which is one of most popular and the symplest
higher dimensional lattice, and look in to its kinetic and stochastic counterpart.

A. Kinetic square lattice

The square lattice is, perhaps, one of the simplest and popular planar lattice. Due to its apparent
simplicity physicists and mathematician often apply their favourite model on it. Its construction
 37

may starts with an initiator, say a square of unit area, and a generator that divides it into four
equal parts by drawing two mutually perpendicular lines passing through the centre of the initiator.
In the next step and steps thereafter the generator is applied to all the available squares which
eventually generates a square lattice. The dual of the square lattice, which is obtained by replacing
each square or block with a node at its center and common border between squares with an edge
joining the two vertices, is a network with degree distribution P (k) = δ(k − 4). It can be easily
seen that two neighbours of a given cell or block are never neighbour of each other revealing the
fact that the clustering coefficient C = 0. Moreover, the mean geodesic path length grows with
network size N like l ∼ N 1/2 which is too fast if one compares it with logarithmically slower growth
l ∼ ln N . The dual of the square lattice is, therefore, a regular graph. In general, a network is
called regular graph (i) if every node have exactly the same degree n so that the degree distribution
P (k) = δ(k − n), (ii) if its mean path length grow like l ∼ N 1/d and (iii) if its clustering coefficient
is either zero or remain constant regardless of the size N of the network.
Now the question is: What if the generator that divides the initiator into four equal blocks
is applied to only one block at each step instead of applying it to all the available blocks? The
question that follows next is: How do we choose that one block when there are blocks with different
size? The generic and the most reasonable case would be the one whereby a block is picked at each
step preferentially with respect to areas of all the available squares and apply the generator onto
it only. We term the resulting lattice generated by such sequential application of the generator as
kinetic square lattice and find through extensive numerical simulation that its various structural
properties are quite different from that of the square lattice. For instance, we find that the blocks
of the resulting lattice which although are of square in shape but have various different areas.
Moreover, blocks may have four or more than four neighbours with whom they share coomon
borders hence its degree distribution will be anything but P (k) = δ(k − 4). Its difference from the
square lattice becomes even more apparent if one looks into the nature of the path length and the
clustering co-efficient. The dual of the kinetic square lattice obtained by replacing each block with
a node at its center and common border between blocks with an edge joining the two corresponding
vertices emerges as a network whose path length that grow following power-law l ∼ N α like square
lattice but with exponent α < 1/d. However, the unlike the square lattice which have clustering
co-efficient C = 0 the kinetic square lattice have clustering co-efficient C = 0.23 regardless of the
size of the lattice.
 38

FIG. 18: A snapshot of the weighted stochastic lattice.

B. Weighted planar stochastic lattice by two cracks (WPSL2)

The next natural question would be: What if the generator divides the initiator randomly into
four blocks instead of dividing it into four equal squares as done in the kinetic square lattice?
This process of lattice generation can also be described as follows. Consider that the substrate is a
square of unit area and at each time step a seed is nucleated from which two orthogonal partitioning
lines parallel to the sides of the substrate are grown until intercepted by existing lines. It results
in partitioning the square into ever smaller mutually exclusive rectangular blocks. Note that the
higher the area of a block, the higher is the probability that the seed will be nucleated in it to
divide that into four smaller blocks since seeds are sown at random on the substrate. It justifies
why a block is picked at each step preferentially with respect to areas of the available blocks. The
resulting lattice, which we call weighted planar stochastic lattice or in short WPSL2, have much
richer properties than the square or kinetic square lattice. The factor 2 in WPSL2 refers to the
fact that two mutually perpendicular partitioning lines are used to divide blocks randomly into
four smaller blocks. A snapshot of the lattice at late stage (figure 1) provides an awe-inspiring
perspective of intriguing and rich pattern of blocks which have different sizes and have great many
different number of neighbours with whom they share common border. Such seemingly disordered
lattice will have no place in physics unless there is some order and emergent bahaviours from the
statistical mechanics perspective.
 39

C. Algorithm of the model

Perhaps an exact algorithm can provide a better description of the model than the mere defini-
tion. In step one, the generator divides the initiator, say a square of unit area, randomly into four
smaller blocks. We then label the four newly created blocks by their respective areas a1 , a2 , a3 and
a4 in a clockwise fashion starting from the upper left block (see figure 2). In each step thereafter
only one block is picked preferentially with respect to their respective area (which we also refer as
the fitness parameter) and then it is divided randomly into four blocks. In general, the jth step of
the algorithm can be described as follows.

(i) Subdivide the interval [0, 1] into (3j − 2) subintervals of size [0, a1 ], [a1 , a1 + a2 ], ...,
P3j−3
[ i=1 ai , 1] each of which represents the blocks labelled by their areas a1 , a2 , ..., a(3j−2)
respectively.

(ii) Generate a random number R from the interval [0, 1] and find which of the (3i − 2) sub-
interval contains this R. The corresponding block it represents, say the pth block of area ap ,
is picked.

(iii) Calculate the length xp and the width yp of this block and keep note of the coordinate of
the lower-left corner of the pth block, say it is (xlow , ylow ).

(iv) Generate two random numbers xR and yR from [0, xp ] and [0, yp ] respectively and hence the
point (xR + xlow , yR + ylow ) mimics a random point chosen in the block p.

(v) Draw two perpendicular lines through the point (xR + xlow , yR + ylow ) parallel to the sides
of the pth block in order to divide it into four smaller blocks. The label ap is now redundant
and hence it can be reused.

(vi) Label the four newly created blocks according to their areas ap , a(3j−1) , a3j and a(3j+1)
respectively in a clockwise fashion starting from the upper left corner.

(vii) Increase time by one unit.

viii Repeat the steps (i) - (vii) ad infinitum.

 40

D. Topological properties of WPSL2

We first focus our analysis on the blocks of the WPSL and their coordination numbers. Note
that for square lattice, the deterministic counterpart of the WPSL, the coordination number is a
constant equal to 4. However, the coordination number in the WPSL is not a constant rather the
coordination number that each block assumes in the WPSL2 is random and evolves with time As
a result, the coordination number disorder in the WPSL2 can be regarded as of annealed type.
Defining each step of the algorithm as one time unit and imposing periodic boundary condition in
the simulation, we find that the number of blocks Nk (t) which have contact with k other blocks
which share common border continue to grow linearly with time Nk (t) = mk t (see figure 3). On
P
the other hand, the number of total blocks N (t) = k Nk (t) at time t in the lattice also grow
linearly with time N (t) = 1 + 3t which we can write N (t) ∼ 3t in the asymptotic regime. The ratio
of the two quantities ρk (t) = Nk (t)/N (t) that describes the fraction of the total blocks which have
contact with k other blocks is ρk (t) = mk /3. It implies that ρk (t) becomes a global property since
it is independent of time and size of the lattice. We now take WPSL2 of fixed size or time and look
into its topological properties . For instance, we want to find out what fraction of the total blocks
of the WPSL2 of a given size has coordination number k. The plot of a histogram of ρt (k), the
fraction of the total blocks which have coordination number k, describes the coordination number
distribution function ρt (k) for lattice with fixed size or time t. Interestingly, the same WPSL2
can be interpreted as a network if the blocks of the lattice are regarded as nodes and the common
borders between blocks as their links which is topologically identical to the dual of the WPSL2
(DWPSL2) (the idea is illustrated in figure ).
In fact, the data for the degree distribution P (k) of the DWPSL2 network is exactly the same
as the coordination number distribution function ρt (k) of the WPSL2 i.e., ρt (k) ≡ P (k). The
plot of ln P (k) vs ln(k) in figure 4 using data obtained after taking average over 50 independent
realizations clearly suggests that fitting a straight line to data is possible. This implies that the
degree distribution decays obeying power-law

P (k) ∼ k −γ . (32)

However, note that figure 4 has heavy or fat-tail, a benchmark of the scale-free network, which
represents highly connected hub nodes. The presence of messy tail-end complicates the process of
fitting the data into power-law forms, estimating its exponent γ, and identifying the range over
which power-law holds. One way of reducing the noise at the tail-end of the degree distribution
 41

1 2 1 2 8

10 11 9

13 12

4 3 4 14 3 5
16 15
7 6

STEP 1 STEP 5 & 6 (dotted lines)

FIG. 19: Schematic illustration of the first few steps of the algorithm.

1
16 2
17

3
15

14 4

18

13 5

12 6
19

11 7

10 8
9

FIG. 20: Nodes in the circle and their links with other nodes illustrate the network topology at step 5 of
Fig. 2. New nodes (17, 18 and 19) and links to be added and links to be removed (broken lines) in step 6
again of Fig. 2 are also shown to illustrate the dynamics.

is to plot cumulative distribution P (k 0 > k). We therefore plot ln(P (k 0 > k)) vs ln(k) in figure 5
using the same data of figure 4 and find that the heavy tail smooths out naturally where no data
is obscured. The straight line fit of figure 5 has a slope γ − 1 = 4.66 which indicates that the
degree distribution (figure 4) decays following power-law with exponent γ = 5.66. The weakest
 42

FIG. 21: Degree distribution P (k) for the DWPSL network where data points represent average of 50
independent realizations. The line have slope exactly equal to 5.66 revealing power-law degree distribution
with exponent γ = 5.66.

FIG. 22: Cumulative degree distribution P (k 0 > k) is shown using using the same data as of figure 4. The
dotted line with slope equal to γ − 1 = 4.66 is drawn to guide our eyes.

point about this WPSL2 perhaps is the fact that the exponent γ = 5.66 is significantly higher than
usually found in most real-life network which is typically around γ = 3.

E. The role of group in the growth of BA netwotk

We now consider a natural extension of the BA model to understand the role of group in the
growth of network. Note that in the original BA model it is assumed that only one node with m
edges arrive at each time step, tacitly presuming that, regardless of how many nodes are added
per unit time, the resulting network always self-organizes into a scale-invariant state characterized
by the exponent γ = 3. However, what happens when nodes arrive sequentially in group has never
been under serious scrutiny. In fact, if a group contain n aribitrary nnumber of isolated nodes
arrive sequentially then the resulting network always self-organize into a scale-free state with the
same exponent γ = 3 regardless of the value of n. By group of size n we, however, mean that all of
the n nodes are already linked by n − 1 edges so that none of the n nodes are completely isolated
from the rest. There are numerous examples, other than WPSL2, especially in social systems
where networks grow not just by the addition of a single node but by addition of a group of nodes
at a time. For instance, in networks of co-authorships, scientific collaboration and friendshipd in
Facebook and Linkedin, it is more likely that two or more members who are already friends may
join the existing network exactly at the same time. More realistic theories require inclusion of such
cases. We therefore intend to investigate the case where a dayad, consisting of two nodes already
linked by an edge that represents the simplest group, arrive in the system per unit time. Note that
the two nodes of the incoming dyad can join the exiting network in two different ways

CASE A) Each new node of the dyad establish links with only one of the existing node picked by
following the PA rule.

CASE B) At each time step two independent attempts following the same PA rule are made which
 43

FIG. 23: The degree distributions ln(P (k)) versus ln(k) (a) two nodes of the incoming dyad are attached
to one single existing node picked following PA rule (red line has slope equal to 4) and (b) at each time
step two independent attempts are made following the same PA rule to pick existing nodes with whom the
incoming dyad are attached (red line has slope equal to 4.33). In each case 100 independent realizations are
superimposed.

FIG. 24: Cumulative degree distributions P (k 0 ≥ k) are drawn for both the cases. The inset shows the parts
of these graph which have slope equal four. It clearly reveals that the degree distribution exibits the same
power-law regardless of whether both the nodes of the dyad are attached to one or two nodes by picking
them from the existing network following the PA rule.

may pick the same or two different existing nodes. Each new nodes of the dyad are then
attached with one or two exisiting node depending whether the two independent attempts
picks the same or different nodes.

Naturally one has to start the process with an initiator consisting of a few nodes which are
already linked. For CASE A, we find that the most suitable initiator is a group of m0 ≥ 3 nodes in
a ring linked by m0 edges. For CASE B, however, we find that one may choose the same initiator
as for CASE A or a complete graph containing m0 > 2 nodes. The exact algorithm of the model
for CASE A is in principle the same as described for the BA model except the fact that at each
time a dyad is added and the two free ends of the two edges are attached to the same exiting node
picked by following PA rule. However, for the CASE B the step (iii) of the alogorithm for the
BA model has to be revised. In this case, at each time step two random numbers R1 and R1 are
generated instead of one. Then one has to check if R1 and R2 refer to the same or different exiting
node. If they refer to the same node then the free end of the two edges of the incoming dyad are
attached to that. Else the two free ends get attached to two distinct exisiting nodes.
In both the caes the degree ki (t) of the node i at time t can change at most by a factor of 2 at
each time step and hence ki satisfies the following kinetic equation

∂ki ki
= 2 PN −1 , (33)
∂t j kj

which is true for Case A and B both. Note that every time a dyad is added to the system it adds 3
PN −1
edges contributing addition of 3 × 2 = 6 degrees and hence j kj = 6(t − 1). We can therefore
 44

FIG. 25: Plot shows in the limit N → ∞ the path length l for WPSL1 grows linearly with ln(N )/ ln(ln(N ))
as the lattice size N increases.

write Eq. (??) as

∂ki ki
= . (34)
∂t 3t

Solving this equation subject to the condition ki (ti ) = 2 (each new node is added with degree of
2) gives
 t β
ki = 2 , (35)
ti

where β = 1/3 instead of 1/2 found in the case of monad.

We can find the degree distribution function P (k) using the relation

P (k)dk = −P (ti )dti , (36)

where the minus sign is introduced for the fact that the smaller the birth time ti the larger the
time it enjoys to gain links and hence the degree ki . Finding derivative of ti with respect to ki
from Eq. (35) and using it in Eq. (36) we immediately obtain that

P (k) ∼ k −γ with γ = 4. (37)

To verify the results we simulated the model for dyad in the computer and collected data P (k)
against k for case A and B both. The degree distribution P (k) is in fact equivalent to finding
the fraction of the total nodes which have degree k and topologically it describes the probability
that a node being picked at random has exactly k links. In Fig. 1 we have drawn ln P (k) versus
ln(k) revealing that the degree distribution in both the cases, CASE A in (a) and CASE B in (b),
exhibit fat-tailed power-law with exponent exactly equal 4 as predicted by Eq. (37). For better
extraction of the exponent γ and to see the contrast we have drawn cumulative degree distribution
in the same graph (see Fig. 2) which clearly show that although they do not fall onto each other
but have the same slope. We thus see that group in the growth of network affects significantly in
fixing the exponent γ of the power-law degree distribution as we found γ = 4 for dyad and γ = 3
for monad. We will now check if such onclusion holds for a planar lattice that grows by sequential
addition of monad instead triad.
 45

FIG. 26: Plot shows that like in the previous case the path length l for WPSL1 too grwos linearly with
ln(N )/ ln(ln(N )) in the limit N → ∞ as size of the lattice quantified by N increases. the path length grows
logarithmically with lattice size N .

F. Weighted planar stochastic lattice by a single crack: WPSL1

The exponent γ of the power-law degree distribution of the BA model for monad and dyad
clearly justifies why γ is exceptionally high for the WPSL2. At the same time it implies that if we
can generate a stochastic planar lattice that grow by sequential addition monad instead of a triad
then the exponent γ should be much lower than γ = 5.66. To this end, we choose a generator that
divides the initiator into two blocks either horizontally or vertically with equal a priori probability
instead of four blocks? It describes a process whereby a seed is nucleated randomly at each time
step on the initiator and upon nucleation a single line grows either horzontally or vertically with
equal probability until intercepted by another already existing lines. We always think that an
exact algorithm can provide a better description of the model than the mere definition. In step
one, the generator divides the initiator, say a square of unit area, randomly into two smaller blocks
either horizontally or vertically. We then label the top or left block by a1 if divided horizontally
or vertically respectively and the other block as a2 (see figure 2). In each step thereafter only one
block is picked preferentially with respect to their respective area (which we also refer as the fitness
parameter) and then it is divided randomly either horizontally or vertically into two blocks. In
general, the jth step of the algorithm can be described as follows.

Pj−1
(i) Subdivide the interval [0, 1] into j subintervals of size [0, a1 ], [a1 , a1 + a2 ], ..., [ i=1 ai , 1]
each of which represents the blocks labelled by their areas a1 , a2 , ..., aj respectively.

(ii) Generate a random number R from the interval [0, 1] and find which of the i sub-interval
contains this R. The corresponding block it represents, say the ith block whose area is ai ,
is picked.

(iii) Calculate the length xi and the width yi of this block and take note of the coordinate of the
lower-left corner of the kth block, say it is (xlow , ylow ).

(iv) Generate two random numbers xR and yR from [0, xi ] and [0, yi ] respectively and hence the
point (xR + xlow , yR + ylow ) mimics a random point chosen in the kth block.
 46

FIG. 27: Degree distribution P (k) for dual of the DWPSL1. It clearly reveals that the degree distribution
have power-law fat-tail and find that the exponent γ = 3.33 which is much lower than that of the WPSL2.
It implies that as the group size decreases the exponent γ value of the degree distribution decreases as well.

(v) Generate a random number p within [0, 1]. (vi) If p < 0.5 then draw a vertical line else
a horizontal line through the point (xR + xlow , yR + ylow ) to divide the ith block into two
smaller rectangular blocks. The label i is now redundant and hence it can be reused.

(vi) Label the left or top of the two newly created blocks as i depending whether a vertical or
horizontal line is drawn respectively and the remaining block is then labeled as aj+1 .

(vii) Increase time by one unit.

(viii) Repeat the steps (i) - (vii) ad infinitum.

A snapshot of this lattice too provides an awe-inspiring perspective of intriguing and rich pattern
of blocks and its blocks also have different sizes. Moreover, like WPSL2 the blocks of this lattice
too have great many different number of neighbours with whom they share common border. The
number of blocks N (t) in WPSL1 grow linearly N (t) = 1 + αt as in WPSL2 though with different
slopes α = 1 for WPSL1 and α = 3 for WPSL2. In other words, α = 1 implies that the dual of
the WPSL1 grow by sequential addition of a monad or a single node while α = 3 means that the
dual of the WPSL2 grow by sequesntial addition of triad or a group of three nodes. We even find
that the number of blocks Nk (t) which have contact with k other blocks through common border
also grow linearly with time. This means in the long-time limit the fraction of the total blocks
which have k neighbours is a conserved quantity in the sense it is independent of how many blocks
are there in the lattice like we found in WPSL2. The BA model for monad and dyad suggest that
the exponent γ of the degree distriution should be much less than that of WPSL2. To check this
we plot the degree distribution for WPSL1 in Fig. () and find that it too exhibits power-law near
the tail. More importantly we find that indeed the exponet γ = 3.33 is much less than that of
the WPSL2. It also means that the extent of heterogeneity is higher in the network that grow
sequential addition of monad than the one that grow by a sequential addition of a group and the
higher the group size the lesser the heterogeneity.
Can the two fundamental mechanisms, the growth and the preferential attachment rule, under-
lined by the minimal BA model also be found responsible for the self-organization of the planar
 47

lattice (WPSL2 and WPSL1) into a power-law degree distribution? Indeed, we find both the ingre-
dients are present in these lattice though not explicitly. In fact, while the presence of the growth
mechanism is pretty obvious, the presence of the preferential attachment rule is not. For instance,
at each time step a triad (three nodes linked by two edges) joins the existing network and hence
it is not static rather grow by sequestial addition of a triad. It is interesting to note the fact that
unlike the BA model the node or the block which is picked preferentially with respect to area, is
not in fact the one to gain links rather its neighbours are the ones to gain links. Nonetheless, it
still embodies the intuitative idea of the preferential attachment rule since the higher the number
of links (neighbours) a given node (block) has, the higher is the chance that one of its neighbour
will be picked and hence it will gain links with the incoming nodes (blocks). The major difference
in the growth mechanism between the minimal BA model and the growth of the WPSL2 lies in
the fact that the later grow by sequential addition of a group of nodes which are already linked
and then join the existing network. One may wonder this may the reason why the exponent of the
degree distribution is far too much compared to what we find in the BA model. We therefore find
it worthwhile to check the role of group in the growth of BA network.
Now the question is: How likely is that two blocks which are neighbours of a third bolck are
also likely to be neighours of each other? To find an answer to this question we calculated the
clustering coefficients Ci of all the blocks N = 1 + 3t. Then using periodic boundary condition
and applying Eq. (??) we find that C = 0.35 revealing that two blocks which have a common
neighbour are also neighbours of each other with probability 0.35 irrespective of how many blocks
N are there in the lattice provided the lattice size N is suffieciently large. In addition, the the mean
geodesic distance in the WPSL2 grows logarithmically l ∼ ln N/ ln(ln N ) revealing that it grows
much slowly than in the square and the kinetic square lattice where it grows following power-law
with N . These are the two typical properties of small-world system. We thus see that the netowrk
corresponding to the dual of the WPSL2 is scale-free in one hand and have small-world features
on the other hand. Such properties alone makes it an excellent candidate where one can apply
various model of non-equilibrium phenomena like various spreading phenomena, random walk and
diffusion processes, percolation etc.
.
In this section we intend to know the role of group in the growth of BA networks. Note that
traditionally it is assumed in the BA model that only one node with m edges arrive at each time
step, tacitly presuming that, regardless of how many nodes are added per unit time, the resulting
network always exhibits power-law degree distribution with the same exponent γ = 3. This is,
 48

however, true if new nodes arrive sequentially in group but isolated. By group we actually mean
that all the nodes in the group are already linked. There are numerous examples in natural and
especially in social systems where networks grow by the sequential addition of groups of nodes.
For instance, in the WWW, a site is made of a few pages which are already linked together before
being uploaded to join the existing network by establishing link to a page of one or more of the
existing sites. Also, in social networks such as co-authorships, scientific collaboration, friendship
in Facebook and Linkedin, it is more likely that two or more members who are already friends
may join these groups to become members of the larger network instead of joining alone and make
friends thereafter through the network.