Preferential attachment

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged into BA model. (Discuss)

Preferential attachment is a mechanism or algorithm for growing scale-free networks, i.e. a complex network where the distribution of degrees (number of links per node) follows a power law. Scale-free networks are very common, and can be found e.g. in social networks, the world-wide web, or networks of proteins reacting with each other in the cell.

[edit] Mechanism

In preferential attachment, new nodes are added to the network one by one. Each new node attaches itself (creates a link) to one of the existing nodes with a certain probability. This probability is biased, however, in the sense that it is proportional to the number of links that the existing node already has. Therefore, heavily linked nodes ("hubs") tend to quickly accumulate even more links, while nodes with only a few links are unlikely to be chosen as the destination for a new link. It is as if the new nodes have a "preference" to attach themselves to the already heavily linked nodes.

Intuitively, this can be understood if we think in terms of social networks connecting people. Here a link from A to B means that person A "knows" or "is acquainted with" person B. Heavily linked nodes represent well-known people with lots of relations. When a newcomer enters the community, s/he is more like to become acquainted with one of those more visible people rather than with a relative unknown. Similarly, on the web new pages link preferentially to hubs, i.e. very well-known sites such as Google or Wikipedia, rather than to pages that hardly anyone knows. If someone select a new page to link to by randomly choosing an existing link, the probability to get to a particular page would be equal to its degree. This explains the preferential attachment probability rule.

Preferential attachment is an example of a positive feedback cycle where initially random variations (one node initially having more links or having started accumulating links earlier than another) are automatically reinforced, thus greatly magnifying differences. This is also sometimes called the Matthew effect, "the rich get richer", and in chemistry autocatalysis.

[edit] History

The first proposal for a preferential attachment mechanism to explain power law distributions appears to have been made by Herbert Simon in 1955. It was rediscovered independently by Derek de Solla Price in 1965, who used it to explain networks of citations between scientific papers. The name "preferential attachment" and the present popularity of scale-free network models is due to the work of Albert-László Barabási and his student Réka Albert analysing degree distributions on the web in 1999.