How is a matrix connected to a grid?

Question

I have a hard time finding information about and understanding how a matrix (adjacency matrix) is connected to a grid used in numerical analysis. What would the nodes be and are the matrix weighted or unweighted? I understand that it may very depending on what the grid is used for, but if anyone could give me an example i would appreciate it.

Answer 1

For a graph of N nodes, the adjacency matrix will always be a square matrix of size N x N, and it will generally be symmetric too (though there might be exceptions to this). The nodes correspond to whatever data you are working with: they could be cities, pixels within an image, positions within the brain etc. Thats determined by the problem you are working on, but from the point of view of the adjacency matrix it doesn't matter what the underlying data represents.

The simplest form of adjacency matrix just contains 1 and 0 values denoting connections between nodes. For example, if on row A there is a 1 in column B, then node number A is connected to node number B. The symmetry means this works the other way round: column B will also contain a 1 in row A because node B must also be connected to node A. In this form, the adjacency matrix is basically a boolean structure denoting 'connection' or 'no connection'. More info here

More sophisticated adjacency matrices may have values reflecting the 'strength' of connection between two nodes. For example, if both B and C are connected to A, but C is much further away than B, then the weight of the connection may be smaller. That is, M(A,C) < M(A,B), where M is the adjacency matrix.

Finally, various forms of (discrete) Laplacian are closely related to the adjacency matrix, though they represent very different things. The Laplacian operator is a measure of curvature of a function (ie, second derivative), and in order to calculate this quantity, you need to know the neighbours for each given node (you can't calculate rates of change without knowing how the data varies from one node to the next). This is why the Laplacian is closely related to the adjacency matrix: calculating it requires adjacency information.

The 'graph' or 'mesh' Laplacian is the simplest one and is constructed by taking the normal adjacency matrix with 1/0 values and then modifying the diagonal values. In the standard adjacency matrix, diagonal elements are zero (because nodes being 'connected to themselves' doesn't count as a connection); in the mesh Laplacian, the diagonal is set to the negative sum of how many connections that node has. So, if a node is connected to 4 other nodes, then the diagonal element for that node will be -4. This means that every row or column of the Laplacian then sums to zero, which is beneficial in many use cases. This definition also extends to cases where the weights are not 1/0 values. This article explains graph Laplacians in more detail 2.

Finally, the concept of adjacency isn't just related to graphs. For example, in image processing, many operations are performed on neighbourhoods of pixels/voxels, so an adjacency matrix is useful to quickly identify the appropriate neighbourhoods.

A note on implementation: adjacency matrices are by nature very sparse (almost all elements are zero) and very large (size N x N). Hence, if doing any serious computing with them you'll need to use some kind of 'sparse data structure' to speed things up.