Linear algebra
Graphs.jl provides numerous matrix operations on both directed and undirected graphs, as part of the LinAlg
submodule.
Index
Graphs.LinAlg
Graphs.LinAlg.Adjacency
Graphs.LinAlg.AveragingAdjacency
Graphs.LinAlg.AveragingLaplacian
Graphs.LinAlg.CombinatorialAdjacency
Graphs.LinAlg.GraphMatrix
Graphs.LinAlg.Nonbacktracking
Graphs.LinAlg.Noop
Graphs.LinAlg.NormalizedAdjacency
Graphs.LinAlg.NormalizedLaplacian
Graphs.LinAlg.StochasticAdjacency
Graphs.LinAlg.StochasticLaplacian
Graphs.LinAlg.adjacency_matrix
Graphs.LinAlg.adjacency_spectrum
Graphs.LinAlg.contract
Graphs.LinAlg.contract!
Graphs.LinAlg.degrees
Graphs.LinAlg.degrees
Graphs.LinAlg.incidence_matrix
Graphs.LinAlg.laplacian_matrix
Graphs.LinAlg.laplacian_spectrum
Graphs.LinAlg.non_backtracking_matrix
Graphs.LinAlg.spectral_distance
Graphs.LinAlg.symmetrize
Graphs.LinAlg.symmetrize
Full docs
Graphs.LinAlg
— ModuleLinAlg
A package for using the type system to check types of graph matrices.
Graphs.LinAlg.Adjacency
— TypeAdjacency{T}
The core Adjacency matrix structure. Keeps the vertex degrees around. Subtypes are used to represent the different normalizations of the adjacency matrix. Laplacian and its subtypes are used for the different Laplacian matrices.
Adjacency(lapl::Laplacian) provides a generic function for getting the adjacency matrix of a Laplacian matrix. If your subtype of Laplacian does not provide a field A for the Adjacency instance, then attach another method to this function to provide an Adjacency{T} representation of the Laplacian. The Adjacency matrix here is the final subtype that corresponds to this type of Laplacian.
Graphs.LinAlg.AveragingAdjacency
— TypeAveragingAdjacency{T}
The matrix whose action is to average over each neighborhood.
Graphs.LinAlg.AveragingLaplacian
— TypeAveragingLaplacian{T}
Laplacian version of the AveragingAdjacency matrix.
Graphs.LinAlg.CombinatorialAdjacency
— TypeCombinatorialAdjacency{T,S,V}
The standard adjacency matrix.
Graphs.LinAlg.GraphMatrix
— TypeGraphMatrix{T}
An abstract type to allow operations on any type of graph matrix
Graphs.LinAlg.Noop
— TypeNoop
A type that represents no action.
Implementation Notes
- The purpose of
Noop
is to help write more general code for the
different scaled GraphMatrix types.
Graphs.LinAlg.NormalizedAdjacency
— TypeNormalizedAdjacency{T}
The normalized adjacency matrix is $\hat{A} = D^{-1/2} A D^{-1/2}$. If A is symmetric, then the normalized adjacency is also symmetric with real eigenvalues bounded by [-1, 1].
Graphs.LinAlg.NormalizedLaplacian
— TypeNormalizedLaplacian{T}
The normalized Laplacian is $\hat{L} = I - D^{-1/2} A D^{-1/2}$. If A is symmetric, then the normalized Laplacian is also symmetric with positive eigenvalues bounded by 2.
Graphs.LinAlg.StochasticAdjacency
— TypeStochasticAdjacency{T}
A transition matrix for the random walk.
Graphs.LinAlg.StochasticLaplacian
— TypeStochasticLaplacian{T}
Laplacian version of the StochasticAdjacency matrix.
Graphs.LinAlg.degrees
— Methoddegrees(adjmat)
Return the degrees of a graph represented by the CombinatorialAdjacency
adjmat
.
Graphs.LinAlg.degrees
— Methoddegrees(graphmx)
Return the degrees of a graph represented by the graph matrix graphmx
.
Graphs.LinAlg.symmetrize
— Functionsymmetrize(adjmat, which=:or)
Return a symmetric version of graph (represented by CombinatorialAdjacency
adjmat
) as a CombinatorialAdjacency
. which
may be one of :triu
, :tril
, :sum
, or :or
. Use :sum
for weighted graphs.
Implementation Notes
Only works on Adjacency
because the normalizations don't commute with symmetrization.
Graphs.LinAlg.symmetrize
— Functionsymmetrize(A::SparseMatrix, which=:or)
Return a symmetric version of graph (represented by sparse matrix A
) as a sparse matrix. which
may be one of :triu
, :tril
, :sum
, or :or
. Use :sum
for weighted graphs.
Graphs.LinAlg.Nonbacktracking
— TypeNonbacktracking{G}
A compact representation of the nonbacktracking operator.
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 arcs $A_{i j}` and `A_{k l}` in `g`, the non-backtraking matrix$B`` is defined as
$B_{A_{i j}, A_{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 contract!(vertexspace, nbt, edgespace)
method takes vectors represented in the domain of $B$ and represents them in the domain of the adjacency matrix of g
.
Graphs.LinAlg.contract!
— Methodcontract!(vertexspace, nbt, edgespace)
The mutating version of contract(nbt, edgespace)
. Modifies vertexspace
.
Graphs.LinAlg.contract
— Methodcontract(nbt, edgespace)
Integrate out the edges by summing over the edges incident to each vertex.
Graphs.LinAlg.non_backtracking_matrix
— Methodnon_backtracking_matrix(g)
Return a non-backtracking matrix B
and an edgemap storing the oriented edges' positions in B
.
Given two arcs $A_{i j}` and `A_{k l}` in `g`, the non-backtracking matrix$B`` is defined as
$B_{A_{i j}, A_{k l}} = δ_{j k} * (1 - δ_{i l})$
Graphs.LinAlg.adjacency_matrix
— Functionadjacency_matrix(g[, T=Int; dir=:out])
Return a sparse adjacency matrix for a graph, indexed by [u, v]
vertices. Non-zero values indicate an edge from u
to v
. Users may override the default data type (Int
) and specify an optional direction.
Optional Arguments
dir=:out
: :in
, :out
, or :both
are currently supported.
Implementation Notes
This function is optimized for speed and directly manipulates CSC sparse matrix fields.
Graphs.LinAlg.adjacency_spectrum
— Functionadjacency_spectrum(g[, T=Int; dir=:unspec])
Return the eigenvalues of the adjacency matrix for a graph g
, indexed by vertex. Default values for T
are the same as those in adjacency_matrix
.
Optional Arguments
dir=:unspec
: Options for dir
are the same as those in laplacian_matrix
.
Performance
Converts the matrix to dense with $nv^2$ memory usage.
Implementation Notes
Use eigvals(Matrix(adjacency_matrix(g, args...)))
to compute some of the eigenvalues/eigenvectors.
Graphs.LinAlg.incidence_matrix
— Functionincidence_matrix(g[, T=Int; oriented=false])
Return 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
by default (this behavior can be overridden by the oriented
optional argument).
If oriented
(default false) is true, for an undirected graph g
, the matrix will contain arbitrary non-zero values representing connectivity between v
and i
.
Graphs.LinAlg.laplacian_matrix
— Methodlaplacian_matrix(g[, T=Int; dir=:unspec])
Return a sparse Laplacian matrix for a graph g
, indexed by [u, v]
vertices. T
defaults to Int
for both graph types.
Optional Arguments
dir=:unspec
: :unspec
, :both
, :in
, and :out
are currently supported. For undirected graphs, dir
defaults to :out
; for directed graphs, dir
defaults to :both
.
Graphs.LinAlg.laplacian_spectrum
— Functionlaplacian_spectrum(g[, T=Int; dir=:unspec])
Return the eigenvalues of the Laplacian matrix for a graph g
, indexed by vertex. Default values for T
are the same as those in laplacian_matrix
.
Optional Arguments
dir=:unspec
: Options for dir
are the same as those in laplacian_matrix
.
Performance
Converts the matrix to dense with $nv^2$ memory usage.
Implementation Notes
Use eigvals(Matrix(laplacian_matrix(g, args...)))
to compute some of the eigenvalues/eigenvectors.
Graphs.LinAlg.spectral_distance
— Functionspectral_distance(G₁, G₂ [, k])
Compute the spectral distance between undirected n-vertex graphs G₁
and G₂
using the top k
greatest eigenvalues. If k
is omitted, uses full spectrum.
References
- JOVANOVIC, I.; STANIC, Z., 2014. Spectral Distances of Graphs Based on their Different Matrix Representations