Link prediction

Topology-based methods broadly make the assumption that nodes with similar network structure are more likely to form a link.

This is a common approach to link prediction that computes the number of common neighbors. Entities with more neighbors in common are more likely to have a link. It is computed as follows:

${\displaystyle CN(A,B)={|A\cap B|}}$

A weakness of this approach is that it does not take into account the relative number of common neighbors.

The Jaccard Measure addresses the problem of Common Neighbors by computing the relative number of neighbors in common:

${\displaystyle J(A,B)={{|A\cap B|} \over {|A\cup B|}}}$

The Adamic–Adar measure [12] is the sum of the log of the intersection of the neighbors of two nodes. This captures a two-hop similarity, which can yield better results than simple one-hop methods. It is computed as follows:

${\displaystyle A(x,y)=\sum _{u\in N(x)\cap N(y)}{\frac {1}{\log |N(u)|}},}$

where ${\displaystyle N(u)}$ is the set of nodes adjacent to ${\displaystyle u}$.

Neighbor based methods can be effective when the number of neighbors is large, but this is not the case in sparse graphs. In these situations it is appropriate to use methods that account for longer walks. The Katz Measure [13] is one metric that captures this. It is computed by searching the graph for paths of length ${\displaystyle t}$ in the graph and adding the counts of each path length weighted by user specified weights.

Let A be the adjacency matrix of a network under consideration. Elements ${\displaystyle (a_{ij})}$ of A are variables that take a value 1 if a node i is connected to node j and 0 otherwise. The powers of A indicate the presence (or absence) of links between two nodes through intermediaries. For instance, in matrix ${\displaystyle A^{3}}$, if element ${\displaystyle (a_{2,12})=1}$, it indicates that node 2 and node 12 are connected through some walk of length 3. If ${\displaystyle C_{\mathrm {Katz} }(i)}$ denotes Katz centrality of a node i, then mathematically:

${\displaystyle C_{\mathrm {Katz} }(i)=\sum _{k=1}^{\infty }\sum _{j=1}^{n}\alpha ^{k}(A^{k})_{ji}}$

Note that the above definition uses the fact that the element at location ${\displaystyle (i,j)}$ of ${\displaystyle A^{k}}$ reflects the total number of ${\displaystyle k}$ degree connections between nodes ${\displaystyle i}$ and ${\displaystyle j}$.

Node-similarity methods predict the existence of a link based on the similarity of the node attributes.

The attribute values are represented as normalized vector and the distance between the vectors used to measure similarity. Small distances indicate higher similarity.

After normalizing the attribute values, computing the cosine between the two vectors is a good measure of similarity, with low values indicating higher similarity.

Mixed methods combine attribute and topology based methods.

Graph embeddings also offer a convenient way to predict links.[8] Graph embedding algorithms, such as Node2vec, learn an embedding space in which neighboring nodes are represented by vectors so that vector similarity measures, such as dot product similarity, or euclidean distance, hold in the embedding space. These similarities are functions of both topological features and attribute-based similarity. One can then use other machine learning techniques to predict edges on the basis of vector similarity.

A probabilistic relational model(PRM) specifies a template for a probability distribution over a databases. The template describes the relational schema for the domain, and the probabilistic dependencies between attributes in the domain. A PRM, together with a particular database of entities and unobserved links, defines a probability distribution over the unobserved links. [5]

Probabilistic soft logic (PSL) is a probabilistic graphical model over hinge-loss Markov random field (HL-MRF). HL-MRFs are created by a set of templated first-order logic-like rules, which are then grounded over the data. PSL can combine attribute, or local, information with topological, or relational, information. While PSL can incorporate local predictors, such as cosine similarity, it also supports relational rules, such as triangle completion in a network.[14]

Markov logic networks (MLNs) are a probabilistic graphical model defined over Markov networks. These networks are defined by templated first-order logic-like rules, which is then grounded over the training data. MLNs are able to incorporate both local and relational rules for the purpose of link prediction.[15]