Using Similarity for Link Prediction

What’s link prediction?

Link prediction is a type of inference task we can make in complex networks. It starts with the assumption that the network is going to grow over time. It also considers that there’s a logic behind the new edges that are going to be created in the future, meaning that they aren’t completely random.

The task is to estimate which edges will be created and which not. One way of doing such type of inference is by using similarity measures.

Validating link prediction methods

When doing inference, it’s required that we know how to evaluate the method we are applying so we can find out which method is best. With link prediction tasks, two usual evaluation metrics are precision and recall.

Our objective is to output a set of edges that do not exist in the current state of the network but we believe will appear in the future.

For each prediction our method makes, it can either be right or wrong. Also, it can be wrong on the other side: it can say that an edge won’t be created when, in fact, it will.

These possibilities generate what we call a confusion matrix: