Preferential Attachment

Overview

Preferential attachment is a common phenomenon in complex network where nodes with more connections are more likely to establish new connections. When both nodes possess a large number of connections, the probability of them forming a connection is significantly higher. This phenomenon was utilized by A. Barabási and R. Albert in their proposed BA model for generating random scale-free networks in 2002:

• R. Albert, A. Barabási, Statistical mechanics of complex networks (2001)

The Preferential Attachment algorithm gauges the similarity between two nodes by calculating the product of the number of neighbors each node has. It is computed using the following formula:

where N(x) and N(y) are the sets of adjacent nodes to nodes x and y respectively.

Higher Preferential Attachment scores indicate greater similarity between nodes, while a score of 0 indicates no similarity between two nodes.

In this example, PA(D,E) = |N(D)| * |N(E)| = |{B, C, E, F}| * |{B, D, F}| = 4 * 3 = 12.

Considerations

• The Preferential Attachment algorithm ignores the direction of edges but calculates them as undirected edges.

Syntax

• Command: algo(topological_link_prediction)
• Parameters:

Example

The example graph is as follows:

File Writeback

UQL
algo(topological_link_prediction).params({
  uuids: [3],
  uuids2: [1,5,7],
  type: 'Preferential_Attachment'
}).write({
  file:{ 
    filename: 'pa'
  }
})

Results: File pa

File
C,A,3.000000
C,E,6.000000
C,G,3.000000

Direct Return

UQL
algo(topological_link_prediction).params({
  ids: 'C',
  ids2: ['A','C','E','G'],
  type: 'Preferential_Attachment'
}) as pa 
return pa 

Results: pa

Stream Return

UQL
find().nodes() as n
with collect(n._id) as nID
algo(topological_link_prediction).params({
  ids: 'C',
  ids2: nID,
  type: 'Preferential_Attachment'
}).stream() as pa
where pa.num >= 2
return pa

Results: pa