Distances Between Networks — distances • nevada

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.

Value

A scalar measuring the distance between the two input networks.

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")
#> [1] 0.2894737
dist_frobenius(g1, g2, "adjacency")
#> [1] 10.48809
dist_spectral(g1, g2, "laplacian")
#> [1] 13.79925
dist_root_euclidean(g1, g2, "laplacian")
#> [1] 10.91692