Preferential attachment algorithm

Chapter 4 of Six Degrees pp 108-109 has a good introduction to cumulative advantage (known also as "rich get richer" and the "Matthew effect" among other names) and its effect on network dynamics. Read that before you continue.

Preferential attachment is the mathematical model used to represent the force of cumulative advantage in network dynamics. The algorithm below describes the process of repeated preferential attachment. This is equivalent to the algorithm informally described on pp 108-109 of Six Degrees:

Preferential Attachment Algorithm:

Input:

  1. An undirected graph G=(V,E) such that V = {1,2,3,...,k}, k>1, and |E|>0
  2. Integer n, with n>k. Variable n represents the number of nodes in the output graph

Output:

See example below...

Steps:

  1. i = k + 1
  2. Choose a node x based on degree: if deg(x) = 2*deg(y), then x is twice as likely to be picked as y.
  3. Add element i to set V
  4. Add element {i,x} to set E
  5. Add 1 to the value of i
  6. if i > n then we're done
  7. Go to step 2

Example: Suppose the preferential attachment algorithm starts with V={1,2}, E={{1,2}}, and n=20. Therefore k=2 and the input graph can be drawn as

input graph

The table below illustrates the first few iterations of the algorithm.

Iteration 1

Create node 3 and join it to a pre-existing node. Node 1 and node 2 are equally likely.

add 3

 Suppose the algorithm joins node 3 to node 1. Then...

Iteration 2

Create node 4 and join it to a pre-existing node. Node 1 is twice as likely as node 2 or node 3.

add node 4

Suppose the algorithm joins node 4 to node 1. Then...

Iteration 3

Create node 5 and join it to a pre-existing node. Node 1 is 3 times as likely as node 2, 3 or 4.

add node 5

Suppose the algorithm joins node 5 to node 2 (i.e., a lucky break for node 2). Then...

Iteration 4

Create node 6 and join it to a pre-existing node.

add node 6

Suppose the algorithm joins node 6 to node 3 (i.e., a lucky break for node 3). 

Iterations continue...

In the very last iteration, node 20 is joined to node 2

Output graph:

output graph

Notice in the above example that nodes 1 and 2 start out as equals. However, the random choice of node 1 in the first iteration gives node 1 a nudge up in popularity that feeds on itself. In the end, node 1 is the single dominant hub and node 2 is a second-tier mini-hub. A seemingly insignificant event in iteration 1 has caused a very substantial effect because of cumulative advantage. 

< Prev
 
Joomla Templates by Joomlashack