'

*This unparalleled license of expression, coupled with diminished publishing costs, makes the Web the ultimate forum of democracy; everybody’s voice can be heard with equal opportunity. Or so insist constitutional lawyers and glossy business magazines. If the web were a random network, they would be right. But it is not. The most intriguing result of our Web-mapping project was the*' (Barabási,__complete__absence of democracy, fairness, and egalitarian values on the Web. We learned that the topology of the Web prevents us from seeing anything but a mere handful of the billion documents out there*Linked*).
A scale-free
network is one in which a few of the nodes have a much larger number of
connections than others. For regular networks and for random networks the
number of edges per node has an approximately Gaussian distribution, with a
mean value that is a measure of the scale of the network. In a scale-free
network, by contrast, there are a few strongly connected nodes and a large
number of weakly connected ones. Typically, the degree distribution follows a
power law:

*P*(

*k*) ~

*k*

^{-γ}
The exponent

*γ*generally lies between 2 and 3. Most of the complex networks in Nature have a power-law degree distribution (cf. Part 83).
Since the
distribution function P(

*k*) does not show a characteristic peak (unlike the Gaussian peak for random networks and regular networks), the network is described as*scale-free*. For it, the average distance between any two nodes is almost as small as for a random network, and yet its clustering coefficient is practically as large as for a regular network. In other words, scale-free networks exhibit*cliquishness*, like small-world networks (cf. Part 105).__Power-law degree-distribution models for random networks__

Often one can
bring a random-network model closer to reality by introducing a power-law
degree distribution into it. Such a topologically modified network is still
random in the sense that the edges still connect randomly selected nodes. But a
constraint is introduced that the degree distribution function

*P*(*k*) must follow a power law (Albert and Barabási 2002).
Real-life networks
evolve with time. It has been observed in a wide variety of complex networked
systems that their topology evolves to achieve higher and higher degrees of

*robustness*(see below) against attacks and failures (Albert and Barabási 2002; Barabási 2003). How does this happen?*How does the power-law degree distribution arise*? What mechanisms result in the coexistence of large clustering coefficients and small path lengths?
We have seen in
Part 105 that the Watts-Strogatz model captures some of
the important features of many real networks, even though it does not reproduce
the power-law or scale-free feature characteristic of many real networks. The
generalized random-graph model, on the other hand,

*is*able to introduce power-law degree-distribution behaviour.
The ad hoc
ways in which these models are introduced do not shed light on the underlying
mechanisms operative in the evolution of the topology of real networks. What is
needed is that, instead of modelling the network topology, we should try to
model the assembly of the network and its evolution. This was first done by
Barabási and Albert (1999).

__The Barabási-Albert model__

The BA model
captures some essential features of network dynamics, and can reproduce the
scale-free connectivity exhibited by many real networks, by doing away with the
two assumptions made in the models we have discussed so far. We have assumed
that the order

*N*of a network is constant. We have also assumed that the connection probability*p*does not depend on which two nodes are selected for connection. What usually happens in the real world, however, is that, firstly, networks*grow*with time by the addition of new nodes (e.g. the World Wide Web grows exponentially with time by the continuous addition of new web pages); and secondly, there is likelihood of*preferential attachment*to certain nodes (e.g. when a new manuscript is prepared for publication, there is a greater chance that well-known papers will be cited, rather than less frequently cited average-quality papers).
The growth
feature in the BA model is introduced as follows. One starts with a small
number

*m*_{0}of nodes, and at every time step a new node having*m*(≤*m*_{0}) edges is added. Thus there are*N = m*_{0}+*t*nodes after*t*time steps.
And the
preferential attachment of new nodes is carried out as follows: It is assumed
that the probability

*Π*that the new node will be connected to an existing node*i*is linearly related to the degree*k*of the node_{i}*i*:*Π*(

*k*) =

_{i}*k*/ ∑

_{i }

_{i }k_{i}
Thus there are

*mt*edges in the network after*t*time steps.
Numerical
simulations demonstrate that the BA network evolves to be a scale-free network,
with the probability that a node has

*k*edges given by a power law with exponent*γ*= 3._{BA}
The properties
of real networks can differ substantially from what is predicted by the BA
model. For example, the power-law exponent for the actual degree distribution
may lie anywhere between 1 and 3. Even non-power-law features like an
exponential cutoff, or saturation for small

*k*, are observed sometimes. Evolving networks in Nature can develop both power-law and exponential degree distributions. Certain preferential attachments, aging effects, and growth constraints can make a network cross over from power-law to exponential-degree distribution. Various refinements of the BA model have been investigated (cf. Albert and Barabási 2002).__Robustness of networks__

Networked
complex adaptive systems display a remarkable degree of error
tolerance. Naturally, this robustness aspect of networks has been investigated
widely by computer simulation, as well as by analytical studies. The error
tolerance of real networks has a dynamic aspect (Garlaschelli, Capocci and Caldarelli 2007) and a
topological aspect. The topological aspect is easier to simulate on a computer.
One may focus either on edges or on vertices, or on both.

*A network is defined as robust if it contains a giant cluster consisting of most of the nodes even after a fraction of its nodes are removed*.
The
progressive removal of edges randomly is like an inverse edge-percolation
problem (cf. Part 104). The removal
of a node, on the other hand, has a more damaging effect on the network
topology, since all the edges adjacent with that node also get removed.

Simulation
studies have shown a strong correlation between robustness and topology. Scale-free
networks are found to be generally more robust than random networks. However,
if the most connected nodes of a scale-free network are the targets of attack,
then they are much more vulnerable than random networks (Albert, Jeong and Barabási 2000).

## No comments:

## Post a Comment