Predicting links with traditional methods
The link prediction problem has been around for a long time, which is why numerous techniques have been proposed to solve it. First, this section will describe popular heuristics based on local and global neighborhoods. Then, we will introduce matrix factorization and its connection to DeepWalk and Node2Vec.
Heuristic techniques
Heuristic techniques are a simple and practical way to predict links between nodes. They are easy to implement and offer strong baselines for this task. We can classify them based on the number of hops they perform (see Figure 10.1). Some of them only require 1-hop neighbors that are adjacent to the target nodes. More complex techniques also consider 2-hop neighbors or an entire graph. In this section, we will divide them into two categories – local (1-hop and 2-hop) and global heuristics.
Figure 10.1 – Graph with 1-hop, 2-hop, and 3-hop neighbors
