nd_extremal function

Extremal distance with top-$k$ eigenvalues

Extremal distance (nd.extremal) is a type of spectral distance measures on two graphs' graph Laplacian, [REMOVE_ME]$L := D-A [REMOVE_ME_2]$

where $A$ is an adjacency matrix and $D_{ii}=\sum_j A_{ij}$. It takes top-$k$ eigenvalues from graph Laplacian matrices and take normalized sum of squared differences as metric. Note that it is 1. non-negative, 2. separated, 3. symmetric, and satisfies 4. triangle inequality in that it is indeed a metric.

nd.extremal(A, out.dist = TRUE, k = ceiling(nrow(A)/5))

Arguments

• A: a list of length N containing adjacency matrices.
• out.dist: a logical; TRUE for computed distance matrix as a dist object.
• k: the number of largest eigenvalues to be used.

Returns

a named list containing

• D: an $(N\times N)$ matrix or dist object containing pairwise distance measures.
• spectra: an $(N\times k)$ matrix where each row is top-$k$ Laplacian eigenvalues.

Description

Extremal distance (nd.extremal) is a type of spectral distance measures on two graphs' graph Laplacian,

where $A$ is an adjacency matrix and $D_{ii}=\sum_j A_{ij}$. It takes top-$k$ eigenvalues from graph Laplacian matrices and take normalized sum of squared differences as metric. Note that it is 1. non-negative, 2. separated, 3. symmetric, and satisfies 4. triangle inequality in that it is indeed a metric.

Examples

## load data
data(graph20)

## compute distance matrix
output = nd.extremal(graph20, out.dist=FALSE, k=2)

## visualize
opar = par(no.readonly=TRUE)
par(pty="s")
image(output$D[,20:1], main="two group case", col=gray(0:32/32), axes=FALSE)
par(opar)

References

Rdpack::insert_ref(key="jakobson_extremal_2002",package="NetworkDistance")