Preferential attachment model

As explained in Graph Algorithms for Data Science

The preferential attachment model is a network-growth model in which nodes with more existing connections are more likely to receive new connections.

Preferential attachment describes network growth in which highly connected nodes are more likely to receive new connections. In social networks, people with many friends may encounter more opportunities through events and introductions. The same principle helps explain why some networks develop a few large hubs alongside many small nodes. section 5.0

For link prediction, apply the principle as a score for a pair of nodes:

• Measure each node's degree, counting both incoming and outgoing FEATURE_REL relationships. section 10.3.2
• Multiply the two degrees to obtain the preferential attachment metric. section 10.3.2
• Interpret a higher product as greater likelihood that the pair will form a future connection. section 10.3.2
• Calculate the metric for node pairs in train and test samples, then store it as preferentialAttachment on the relevant relationships. section 10.3.2

Streams with large audiences

Two Stream nodes already share audiences with many other streams, giving both relatively large degrees. Their degree product is therefore high, so preferential attachment predicts a greater chance of a future connection or shared audience overlap. section 10.3.2

Figure 10.9 Nodes with higher degrees are more likely to form new connections.

Use the figure to compare node degree and the likelihood of forming new connections. section 10.3.2

How Graph Algorithms for Data Science covers it

How deep it goes

Defines the organizing principle, gives the degree-product calculation, and specifies relationship filtering, samples, and feature storage.

Examples

Uses people with many friends, high-degree Stream nodes, and train-test node pairs as concrete examples.

What it assumes

Assumes node degree, graph relationships, and train-test link-prediction samples as working concepts.

What you can do after

Apply it by calculating degree products for candidate pairs and storing the resulting feature for link-prediction analysis.

How it connects

Connects network growth with node degree, link prediction, scale-free networks, power-law distributions, and future-link classification.

liveBookmanning.com

Read Graph Algorithms for Data Science on liveBook Get the book at manning.com

Related concepts

• link predictionused by · Link prediction is a graph-learning task that estimates whether a connection exists or may occur between nodes, often by scoring candidate links.
• scale-free networkproduces · A scale-free network is a network whose highly uneven degree distribution is characterized by a small number of high-degree hubs and many low-degree nodes.
• shortest pathproduces · A shortest path is a path between two nodes or locations that minimizes total distance, length, or cost under a specified measure.

This explainer was generated by Manning's knowledge graph from the text of Graph Algorithms for Data Science. The section links point to the parts of the book it draws on.