nevada (version 0.2.0)

distances: 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")

Value

A scalar measuring the distance between the two input networks.

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.

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")