Linear Algebra

Erdos.jl provides the following matrix operations on both directed and undirected graphs:

# Erdos.adjacency_matrix — Function.

adjacency_matrix(g, dir=:out, T::DataType=Int)

Returns a sparse boolean adjacency matrix for a graph, indexed by [u, v] vertices. true values indicate an edge between u and v. Users may specify a direction (:in, :out, or :all are currently supported; :out is default for both directed and undirected graphs) and a data type for the matrix (defaults to Int).

source

# Erdos.incidence_matrix — Function.

incidence_matrix(g::AGraphOrDiGraph, T::DataType=Int; oriented=false)

Returns a sparse node-arc incidence matrix for a graph, indexed by [v, i], where i is in 1:ne(g), indexing an edge e. For directed graphs, a value of -1 indicates that src(e) == v, while a value of 1 indicates that dst(e) == v. Otherwise, the value is 0.

For undirected graphs, both entries are 1 if oriented=false, otherwise [v, i] -> -1 and [u, i] -> 1 if v < u.

source

# Erdos.laplacian_matrix — Function.

laplacian_matrix(g, dir::Symbol=:out, T::DataType=Int)

Returns a sparse Laplacian matrix for a graph g, indexed by [u, v] vertices. dir has to be :in, :out or :all.

source

# Erdos.spectral_distance — Method.

spectral_distance(G₁, G₂ [, k])

Compute the spectral distance between undirected n-vertex graphs G₁ and G₂ using the top k ≤ n greatest eigenvalues. If k is ommitted, uses full spectrum.

For further details, please refer to:

JOVANOVIC, I.; STANIC, Z., 2014. Spectral Distances of Graphs Based on their Different Matrix Representations

source

# Erdos.Nonbacktracking — Type.

mutable struct Nonbacktracking{G, E}
    g::G
    edgeidmap::Dict{E,Int}
    m::Int
end

A compact representation of the nonbacktracking operator

g: the underlying graph
edgeidmap: the association between oriented edges and index into the NBT matrix

The Nonbacktracking operator can be used for community detection. This representation is compact in that it uses only ne(g) additional storage and provides an implicit representation of the matrix B_g defined below.

Given two oriented edges i->j and k->l in g, the non-backtraking matrix B is defined as

B[i->j, k->l] = δ(j,k)* (1 - δ(i,l))

This type is in the style of GraphMatrices.jl and supports the necessary operations for computed eigenvectors and conducting linear solves.

Additionally the contraction!(vertexspace, nbt, edgespace) method takes vectors represented in the domain of B and represents them in the domain of the adjacency matrix of g.

source

# Erdos.nonbacktracking_matrix — Method.

nonbacktracking_matrix(g)

Given two oriented edges i->j and k->l in g, the non-backtraking matrix B is defined as

B[i->j, k->l] = δ(j,k)* (1 - δ(i,l))

Returns a matrix B, and an edgemap storing the oriented edges' positions in B.

source