Adjacency matrix
The adjacency matrix of a graph is the square binary matrix that encodes its connectivity: a 1 in position (i,j) means nodes i and j are connected by an edge; a 0 means they are not. It is the most fundamental matrix representation in graph theory and network science, transforming a topological object into an algebraic one that can be manipulated with the tools of matrix algebra.
The adjacency matrix is not merely a data structure. Powers of the adjacency matrix Ak count the number of walks of length k between any pair of nodes. Its eigenvalues — the spectrum of the graph — encode global properties invisible in the local wiring: the spectral gap determines how quickly a random walk mixes, and the eigenvector centrality ranks nodes by their influence in the network's long-term dynamics.
The adjacency matrix generalizes naturally to weighted graphs (where entries are edge weights rather than binary values) and to bipartite networks (where it becomes rectangular rather than square). It is also distinct from the Incidence matrix, which encodes node-edge relationships rather than node-node relationships.