In network theory, link prediction is the problem of predicting the existence of a link between two entities in a network. Examples of link prediction include predicting friendship links among users in a social network, predicting co-authorship links in a citation network, and predicting interactions between genes and proteins in a biological network. Link prediction can also have a temporal aspect, where, given a snapshot of the set of links at time t {\displaystyle t} , the goal is to predict the links at time t + 1 {\displaystyle t+1} . Link prediction is widely applicable. In e-commerce, link prediction is often a subtask for recommending items to users. In the curation of citation databases, it can be used for record deduplication. In bioinformatics, it has been used to predict protein-protein interactions (PPI). It is also used to identify hidden groups of terrorists and criminals in security related applications.
Problem definition Consider a network G = ( V , E ) {\displaystyle G=(V,E)} , where V {\displaystyle V} represents the entity nodes in the network and E ⊆ | V | {\displaystyle E\subseteq |V|} x | V | {\displaystyle |V|} represents the set of "true" links across entities in the network. We are given the set of entities V {\displaystyle V} and a subset of true links which are referred to as observed links. The goal of link prediction is to identify the unobserved true links. In the temporal formulation of link prediction the observed links correspond to true links at a time t {\displaystyle t} , and the goal is to infer the set of true links at time t + 1 {\displaystyle t+1}
Usually, we are also given a subset of unobserved links called potential links E ′ {\displaystyle E'} , and we need to identify true links among these potential links. In the binary classification formulation of the link prediction task the potential links are classified as either true links or false links. Link prediction approaches for this setting learn a classifier M b {\displaystyle M_{b}} that maps links in E ′ {\displaystyle E'} to positive and negative labels i.e. M b : E ′ → { 0 , 1 } {\displaystyle M_{b}:E'\to \{0,1\}} . In the probability estimation formulation, potential links are associated with existence probabilities. Link prediction approaches for this setting learn a model M p {\displaystyle M_{p}} that maps links in E ′ {\displaystyle E'} to a probability i.e. M p : E ′ → [ 0 , 1 ] {\displaystyle M_{p}:E'\to [0,1]} . Single link approaches learn a model that classifies each link independently. Structured prediction approaches capture the correlation between potential links by formulating the task as a collective link prediction task. Collective link prediction approaches learn a model that jointly identify all the true links among the set of potential links. Link prediction task can also be formulated as an instance of missing value estimation task. Here, the graph is represented as an adjacency matrix with missing values. The task is to complete the matrix by identifying the missing values. Matrix factorization based methods commonly use this formulation.
History The task of link prediction has attracted attention from several research communities ranging from statistics and network science to machine learning and data mining. In statistics, generative random graph models such as stochastic block models propose an approach to generate links between nodes in a random graph. For social networks, Liben-Nowell and Kleinberg proposed a link prediction models based on different graph proximity measures. Several statistical models have been proposed for link prediction by the machine learning and data mining community. For example, Popescul et al. proposed a structured logistic regression model that can make use of relational features. Local conditional probability models based on attribute and structural features were proposed by O’Madadhain et al. Several models based on directed graphical models for collective link prediction have been proposed by Getoor. Other approached based on random walks. and matrix factorization have also been proposed With the advent of deep learning, several graph embedding based approaches for link prediction have also been proposed. For more information on link prediction refer to the survey by Getoor et al. and Yu et al.
Approaches and methods Several link predication approaches have been proposed including unsupervised approaches such as similarity measures computed on the entity attributes, random walk and matrix factorization based approaches, and supervised approaches based on graphical models and deep learning. Link prediction approaches can be divided into two broad categories based on the type of the underlying network: (1) link prediction approaches for homogeneous networks (2) link prediction approaches for heterogeneous networks. Based on the type of information used to predict links, approaches can be categorized as topology-based approaches, content-based approaches, and mixed methods.
… excerpt ends here. Continue reading the full article.
