Preferential Attachment

Preferential Attachment is a measure used to compute the closeness of nodes, based on their shared neighbors.

This feature is in the alpha tier. For more information on feature tiers, see API Tiers.

History and explanation

Preferential attachment means that the more connected a node is, the more likely it is to receive new links. This algorithm was popularised by Albert-László Barabási and Réka Albert through their work on scale-free networks. It is computed using the following formula:

preferential attachment

where N(u) is the set of nodes adjacent to u.

A value of 0 indicates that two nodes are not close, while higher values indicate that nodes are closer.

The library contains a function to calculate closeness between two nodes.

Syntax

The following will run the algorithm and return the result:
RETURN gds.alpha.linkprediction.preferentialAttachment(node1:Node, node2:Node, {
    relationshipQuery:String,
    direction:String
})
Table 1. Parameters
Name Type Default Optional Description

node1

Node

null

no

A node

node2

Node

null

no

Another node

relationshipQuery

String

null

yes

The relationship type used to compute similarity between node1 and node2

direction

String

BOTH

yes

The relationship direction used to compute similarity between node1 and node2. Possible values are OUTGOING, INCOMING and BOTH.

Preferential Attachment algorithm sample

The following will create a sample graph:
CREATE
 (zhen:Person {name: 'Zhen'}),
 (praveena:Person {name: 'Praveena'}),
 (michael:Person {name: 'Michael'}),
 (arya:Person {name: 'Arya'}),
 (karin:Person {name: 'Karin'}),

 (zhen)-[:FRIENDS]->(arya),
 (zhen)-[:FRIENDS]->(praveena),
 (praveena)-[:WORKS_WITH]->(karin),
 (praveena)-[:FRIENDS]->(michael),
 (michael)-[:WORKS_WITH]->(karin),
 (arya)-[:FRIENDS]->(karin)
The following will return the Preferential Attachment score for Michael and Karin:
 MATCH (p1:Person {name: 'Michael'})
 MATCH (p2:Person {name: 'Karin'})
 RETURN gds.alpha.linkprediction.preferentialAttachment(p1, p2) AS score
Table 2. Results
score

6.0

We can also compute the score of a pair of nodes based on a specific relationship type.

The following will return the Preferential Attachment score for Michael and Karin based only on the FRIENDS relationship:
 MATCH (p1:Person {name: 'Michael'})
 MATCH (p2:Person {name: 'Karin'})
 RETURN gds.alpha.linkprediction.preferentialAttachment(p1, p2, {relationshipQuery: "FRIENDS"}) AS score
Table 3. Results
score

1.0