Graph Adjusted Rand Index
Computes the graph adjusted Rand index measuring a recovery rate of ordinal information in an unweighted graph.
GARI(ADM, EADM)
ADM |
The given unweighted adjacency matrix |
EADM |
An recovered unweighted adjacency matrix from an embedding. The size of EADM should be same as that of |
GARI is bounded from above by 1, and GARI(A_n,\hat{A}_n) iff A_n=\hat{A}_{n}. A high GARI score implies that many of the ordinal constraints have been satisfied by the solution.
The graph adjusted rand index measuring a recovery rate of ordinal information (a scalar).
Yoshikazu Terada
library(igraph)
###########
#Based on the distance matrix of an embedding,
#this function provides the recovered adjacency matrix for given number of nearest neighbors.
###########
rec.graph <- function(DM, k, symm =FALSE, weight=FALSE ) {
N <- nrow(DM)
ADM <- matrix(0, N, N)
#Search kNN point
if(weight==TRUE){
for (i in 1:N) {
nid <- order(DM[i,])
ADM[ i, nid[2:(k[i]+1)] ] <- DM[ i, nid[2:(k[i]+1)] ]
}
}else{
for (i in 1:N) {
nid <- order(DM[i,])
ADM[i,nid[2:(k[i]+1)] ] <- 1
}
}
if(symm==TRUE){
SADM <- ADM+t(ADM)
SADM[SADM==2*ADM] <- ADM[SADM==2*ADM]
ADM <- SADM
}
return(ADM)
}
ADM <- as.matrix( get.adjacency(graph.famous("Thomassen")) )
#Apply LOE
result.LOE <- LOE(ADM=ADM,p=2,c=0.1,method="BFGS",report=1000)
#Compute the vector of numbers of nearest neighbors with each verteces
true.nn <- apply(X=ADM,1,sum)
#Reconstracte the adjacency matrix based on the result embedding
EDM <- as.matrix( dist(result.LOE$X) )
EADM <- rec.graph(EDM,k=true.nn )
#Compute GARI between ADM and EADM
GARI(ADM,EADM)Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.