Link prediction scores: common neighbours, Adamic-Adar, resource allocation

Neighbourhood scores for a node pair (u, v). With Gamma(x) the neighbour set of x (nonzero entries of row x, self excluded): common neighbours \(CN = |\Gamma(u) \cap \Gamma(v)|\); Adamic-Adar \(AA = \sum_z 1/\log|\Gamma(z)|\); resource allocation \(RA = \sum_z 1/|\Gamma(z)|\), the sums over the common neighbours z. The graph is treated as unweighted and undirected.

Usage

Linkpr(G, u, v, method = "all")

link_prediction(G, u, v, method = "all")

Arguments

G

Adjacency matrix, n by n.

u, v

Node indices (1-based).

method

One of cn, aa, ra, all.

Value

List with the requested scores, common_neighbours (1-based), estimate, u, v, n.

References

Liben-Nowell, D. and Kleinberg, J. (2007). The link-prediction problem for social networks. Journal of the American Society for Information Science and Technology, 58(7), 1019-1031, Sec. 2.

Zhou, T., Lu, L. and Zhang, Y.-C. (2009). Predicting missing links via local information. European Physical Journal B, 71, 623-630, eq. (2).

Examples

A <- matrix(0, 4, 4); A[1, 2] <- A[2, 1] <- 1
A[1, 3] <- A[3, 1] <- 1; A[2, 4] <- A[4, 2] <- 1; A[3, 4] <- A[4, 3] <- 1
Linkpr(A, 1, 4)
#> $common_neighbours
#> [1] 2 3
#> 
#> $u
#> [1] 1
#> 
#> $v
#> [1] 4
#> 
#> $n
#> [1] 4
#> 
#> $method
#> [1] "Liben-Nowell-Kleinberg CN/AA + Zhou RA link prediction"
#> 
#> $cn
#> [1] 2
#> 
#> $aa
#> [1] 2.88539
#> 
#> $ra
#> [1] 1
#> 
#> $estimate
#> [1] 2
#>