nd_gdd function

Graph Diffusion Distance

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 [REMOVE_ME]$L := D-A [REMOVE_ME_2]$

where $D_{ii}=\sum_j A_{ij}$. For two adjacency matrices $A_1$ and $A_2$, GDD is defined as [REMOVE_ME]$d_{gdd}(A_1,A_2) = max_t \sqrt{\| \exp(-tL_1) -\exp(-tL_2) \|_F^2} [REMOVE_ME_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.

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.

Returns

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.

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

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

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.

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)

References

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