-
We can represent the adjacency relation with a square Matrix called the adjacency matrix denoted
. It is and we obtain the entries as follows. For an undirected, graph
For a directed graph we can define the adjacency matrix with either the in-degree or the out-degree.
For the in-degree definition we have that
For the out-degree definition we have that
We denote the adjacency matrix of
as . - Notation: For digraphs, we assume the in-order definition by default unless otherwise stated.
-
The Incidence Matrix is an
matrix where: We denote the incidence matrix of
as . If the graph is directed, then we have
In this case, we say that the incidence matrix captures the graph’s orientation.
-
For any incidence matrix on
, the column sum of any column is . If there is no orientation, the column sum is
This corresponds to the fact that edges have exactly one head and one tail.
-
-
The Degree Matrix is the diagonal matrix
obtained by We denote this with
for graph . For digraphs, we may define this with either the in-degree or the out-degree instead.
- Notation: By default, we assume the in-degree notation unless otherwise stated.
-
The Laplacian Matrix of
is the square matrix whose components are obtained as It may also be obtained as
- The rows of the Laplacian of any graph sum to zero.
-
For a weighted graph, the Weight Matrix is an
diagonal matrix such that -
The Topological Overlap Matrix between nodes
and is calculated as Where
and are the degrees of node and is the Heaviside Function is the number of common neighbors of node and (i.e., )