Graph Definitions and Properties with Animations and Visualizations
Graphs are easily everywhere. They dominate the world of data because of their power of expressing the relationship between objects. In chemistry, graphs are often used to represent the connectivity between molecules. In neuroscience, the relationship between the parts of brain are represented with graphs. We can also easily express the topology of a social network by leveraging graphs.
We can trace back the graph theory and its applications to mid-XIX century with the introduction of Kirchoff’s laws. Since then, many applications and research paradigms were rapidly developed over time. In each context, we encounter with formal definitions of graphs. They can be really overwhelming when it comes to represent complex structures such as normalized Laplacian and spatio-temporal graphs. So I decided to provide a story where each of these mathematical representations (definitions, properties, etc.) are illustrated with proper animations. It is much easier to grasp the idea in glance by the help of such animations!
Let’s start with some common definitions and properties. For each remark, I first give formal definition with mathematical expressions. Then, I provide a proper animation (GIF) to illustrate the concept.
Graph
Formal Definition: A graph G = {V,E} is a set of vertices V which are connected together by a set of edges E.
Directed/Undirected Graph
Definition: A graph G is undirected if the edge connecting a vertex m to a vertex n also connects vertex n to the vertex m, for all m and n. Otherwise, G is directed.
Adjacency Matrix
Definition: An adjacency matrix A represents the connectivity of a graph, where A is an N x N matrix.
Remark: The adjacency matrix of an undirected graph is symmetric; that is A=A^T .
Weight Matrix
Definition: A weight matrix W represents the weights of edges E of a graph G.
Remark: The weighting matrix of an undirected graph is symmetric.
Degree Matrix
Definition: A degree matrix D for an undirected graph is a diagonal matrix with elements, Dmm, which are equal to the sum of all weights of connected edges to m.
Remark: For an unweighted and undirected graph, the value of Dmm is equal to the number of connected edges to m.
So let’s take a look at how degree matrix is configured:
Laplacian Matrix
Definition: The Laplacian matrix L is defined as D-W where D is the diagonal degree matrix and W is the weighting matrix.
Normalized Laplacian Matrix
For practical reasons, it is often advantageous to use the normalized Laplacian, which is defined as:
L = I — A
where I is the identity matrix, and A is the adjacency matrix.
Vertex-weighted Graph Laplacian
It is common to assign weights to vertices instead of edges in a graph. Therefore, we may use a diagonal weight-matrix, V, to represent weights of each node in the graph. Consequently, a vertex-weighted graph Laplacian[2] matrix is defined as:
L = V^(1/2) . L . V^(1/2)
where V = D^-1.
References
[1] Stankovic, Ljubisa and Mandic, Danilo and Dakovic, Milos and Brajovic, Milos and Scalzo, Bruno and Constantinides, Tony. Graph Signal Processing — Part I: Graphs, Graph Spectra, and Spectral Clustering. (2019)
[2] F. R. Chung, R. P. Langlands. A combinatorial laplacian with vertex weight. Journal of combinatorial theory, Series A 75 (2) (1996) 316–327.
