Learn R Programming

loe (version 1.1)

GARI: Graph Adjusted Rand Index

Description

Computes the graph adjusted Rand index measuring a recovery rate of ordinal information in an unweighted graph.

Usage

GARI(ADM, EADM)

Arguments

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 ADM.

Value

  • The graph adjusted rand index measuring a recovery rate of ordinal information (a scalar).

Details

GARI is bounded from above by 1, and $\mathrm{GARI}(A_n,\hat{A}_{n})=1\iff A_n=\hat{A}_{n}$. A high GARI score implies that many of the ordinal constraints have been satisfied by the solution.

Examples

Run this code
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)

Run the code above in your browser using DataLab