Preferential Attachment and the Barabasi-Albert model

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

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

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

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

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

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

where B is the beta function

Yule-Simon distribution

Probability Mass function on log-log scale

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

where

  

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

Properties of Barabasi Albert Graphs :

• The degree distribution is of the form

• Average path length

• Clustering coefficient

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

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

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

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

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

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

References :

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