distances {nevada}

Distances Between Networks

Description

This is a collection of functions computing the distance between two networks.

Usage

dist_hamming(x, y, representation = "laplacian")

dist_frobenius(
  x,
  y,
  representation = "laplacian",
  matching_iterations = 0,
  target_matrix = NULL
)

dist_spectral(x, y, representation = "laplacian")

dist_root_euclidean(x, y, representation = "laplacian")

Arguments

x

An igraph::igraph object or a matrix representing an underlying network.

y

An igraph::igraph object or a matrix representing an underlying network. Should have the same number of vertices as x.

representation

A string specifying the desired type of representation, among: "adjacency", "laplacian", "modularity" or "graphon". Default is "laplacian".

matching_iterations

An integer value specifying the maximum number of runs when looking for the optimal permutation for graph matching. Defaults to 0L in which case no matching is done.

target_matrix

A square numeric matrix of size n equal to the order of the graphs specifying a target matrix towards which the initial doubly stochastic matrix is shrunk each time the graph matching algorithm fails to provide a good minimum. Defaults to NULL in which case the target matrix is automatically chosen between the identity matrix or the uniform matrix on the n-simplex.

Details

Let X be the matrix representation of network x and Y be the matrix representation of network y. The Hamming distance between x and y is given by

\frac{1}{N(N-1)} \sum_{i,j} |X_{ij} - Y_{ij}|,

where N is the number of vertices in networks x and y. The Frobenius distance between x and y is given by

\sqrt{\sum_{i,j} (X_{ij} - Y_{ij})^2}.

The spectral distance between x and y is given by

\sqrt{\sum_i (a_i - b_i)^2},

where a and b of the eigenvalues of X and Y, respectively. This distance gives rise to classes of equivalence. Consider the spectral decomposition of X and Y:

X=VAV^{-1}

and

Y = UBU^{-1},

where V and U are the matrices whose columns are the eigenvectors of X and Y, respectively and A and B are the diagonal matrices with elements the eigenvalues of X and Y, respectively. The root-Euclidean distance between x and y is given by

\sqrt{\sum_i (V \sqrt{A} V^{-1} - U \sqrt{B} U^{-1})^2}.

Root-Euclidean distance can used only with the laplacian matrix representation.

Value

A scalar measuring the distance between the two input networks.

Examples

g1 <- igraph::sample_gnp(20, 0.1)
g2 <- igraph::sample_gnp(20, 0.2)
dist_hamming(g1, g2, "adjacency")
dist_frobenius(g1, g2, "adjacency")
dist_spectral(g1, g2, "laplacian")
dist_root_euclidean(g1, g2, "laplacian")