nd.gdd {NetworkDistance}

Graph Diffusion Distance

Description

Graph Diffusion Distance (nd.gdd) quantifies the difference between two weighted graphs of same size. It takes an idea from heat diffusion process on graphs via graph Laplacian exponential kernel matrices. For a given adjacency matrix A, the graph Laplacian is defined as

L := D-A

where D_{ii}=\sum_j A_{ij}. For two adjacency matrices A_1 and A_2, GDD is defined as

d_{gdd}(A_1,A_2) = max_t \sqrt{\| \exp(-tL_1) -\exp(-tL_2) \|_F^2}

where \exp(\cdot) is matrix exponential, \|\cdot\|_F a Frobenius norm, and L_1 and L_2 Laplacian matrices corresponding to A_1 and A_2, respectively.

Usage

nd.gdd(A, out.dist = TRUE, vect = seq(from = 0.1, to = 1, length.out = 10))

Arguments

A

a list of length N containing adjacency matrices.

out.dist

a logical; TRUE for computed distance matrix as a dist object.

vect

a vector of parameters t whose values will be used.

Value

a named list containing

D

an (N\times N) matrix or dist object containing pairwise distance measures.

maxt

an (N\times N) matrix whose entries are maximizer of the cost function.

References

Hammond DK, Gur Y, Johnson CR (2013). “Graph Diffusion Distance: A Difference Measure for Weighted Graphs Based on the Graph Laplacian Exponential Kernel.” In Proceedings of the IEEE global conference on information and signal processing (GlobalSIP'13), 419–422.

Examples

## load data and extract a subset
data(graph20)
gr.small = graph20[c(1:5,11:15)]

## compute distance matrix
output = nd.gdd(gr.small, out.dist=FALSE)

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