A large
number of real world networks like the world wide web, citation networks and
some social networks are scale free. The origin of the power-law degree
distribution observed in real world networks was addressed by Barabasi and Albert in
the paper titled

*Emergence of Scaling in Random Networks*published in*Science*(1999). The scale-free nature of real networks is rooted in two generic mechanisms shared by many real networks - growth and preferential attachment.__Growth__- Real world networks keep growing in size continuously by the addition of new nodes.

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

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

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

*A preferential attachment process is one in which some unit of wealth (balls) are added to a set of containers (urns).Balls are added to the system at an overall rate of*

*m*new balls for each new urn. In a linear preferential attachment each newly created urn starts out with k0 balls and further balls are added to urns at a rate proportional to the number k that they already have plus a constant a > -k0. A linear preferential process shows a Yule-Simon distribution given by

where B is the beta function

Yule-Simon distribution

Probability Mass function on log-log scale

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

where

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

Properties of Barabasi Albert Graphs :

- The degree distribution is of the form

- Average path length

- Clustering coefficient

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

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

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

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

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

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

References :

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

## No comments:

## Post a Comment