Link prediction feature

As explained in Graph Algorithms for Data Science

A link prediction feature is an input variable that represents similarity, distance, or structural evidence for a prospective relationship between two nodes.

A link prediction feature encodes evidence that a relationship may form between two nodes. It can represent similarity, network distance, or overlap between their local or global neighborhoods. section 10.6

Common ways to construct link prediction features include:

• Aggregating properties of the two nodes. section 10.6
• Encoding network distance, where closer nodes are treated as more likely to connect. section 10.6
• Measuring neighborhood overlap with common-neighbor counts, Jaccard similarity, or Adamic-Adar. section 10.1 section 10.6

After calculating features for node pairs, rank the highest-scoring pairs or train a classification model. A model can learn that some metrics or metric combinations matter more than others. Keep feature, training, and test relationships separate to avoid leakage, and subsample negative examples to reduce class imbalance. section 10.1 section 10.6

Recommending Twitch channels

For channel recommendations, shared audiences provide relationship evidence between channels. Neighborhood and other link prediction features can then support ranking recommendations or training a model to forecast future channel connections. section 10.1

Figure 10.4 Link prediction flow

Use the link prediction flow to connect pair encoding, feature calculation, prediction, and evaluation. section 10.1

How Graph Algorithms for Data Science covers it

How deep it goes

Defines feature categories, ranking and classification workflows, leakage controls, and class balancing, but does not develop exhaustive metrics.

Examples

Uses common friends, Jaccard similarity, Adamic-Adar, and shared audiences between Twitch channels.

What you can do after

Build link-prediction features, rank candidate links, or train and evaluate a classifier while limiting leakage and imbalance.

How it connects

Connects link prediction with network distance, neighborhood overlap, node embeddings, classification models, recommender systems, and feature leakage.

liveBookmanning.com

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

Related concepts

• classifierused by · A classifier is a predictive computational model that assigns inputs to one or more discrete classes or categories.
• 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.
• shortest pathused by · A shortest path is a path between two nodes or locations that minimizes total distance, length, or cost under a specified measure.
• common neighbor countused by · Common neighbor count is the number of nodes directly connected to both members of a node pair, often used as a link-prediction score.

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.