GARI: Graph Adjusted Rand Index

In loe: Local Ordinal Embedding

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.

Details

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.

Value

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

Author(s)

Yoshikazu Terada

Examples

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)

Example output

Loading required package: MASS

Attaching package: 'igraph'

The following objects are masked from 'package:stats':

    decompose, spectrum

The following object is masked from 'package:base':

    union

initial  value 7.531723 
final  value 3.124988 
converged
[1] 0.5652314

loe documentation built on May 2, 2019, 3:28 a.m.