Adjacency matrix

Last updated

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

Contents

In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal. If the graph is undirected (i.e. all of its edges are bidirectional), the adjacency matrix is symmetric. The relationship between a graph and the eigenvalues and eigenvectors of its adjacency matrix is studied in spectral graph theory.

The adjacency matrix of a graph should be distinguished from its incidence matrix, a different matrix representation whose elements indicate whether vertex–edge pairs are incident or not, and its degree matrix, which contains information about the degree of each vertex.

Definition

For a simple graph with vertex set U = {u1, …, un}, the adjacency matrix is a square n × n matrix A such that its element Aij is one when there is an edge from vertex ui to vertex uj, and zero when there is no edge. [1] The diagonal elements of the matrix are all zero, since edges from a vertex to itself (loops) are not allowed in simple graphs. It is also sometimes useful in algebraic graph theory to replace the nonzero elements with algebraic variables. [2] The same concept can be extended to multigraphs and graphs with loops by storing the number of edges between each two vertices in the corresponding matrix element, and by allowing nonzero diagonal elements. Loops may be counted either once (as a single edge) or twice (as two vertex-edge incidences), as long as a consistent convention is followed. Undirected graphs often use the latter convention of counting loops twice, whereas directed graphs typically use the former convention.

Of a bipartite graph

The adjacency matrix A of a bipartite graph whose two parts have r and s vertices can be written in the form

where B is an r × s matrix, and 0r,r and 0s,s represent the r × r and s × s zero matrices. In this case, the smaller matrix B uniquely represents the graph, and the remaining parts of A can be discarded as redundant. B is sometimes called the biadjacency matrix.

Formally, let G = (U, V, E) be a bipartite graph with parts U = {u1, …, ur}, V = {v1, …, vs} and edges E. The biadjacency matrix is the r × s 0–1 matrix B in which bi,j = 1 if and only if (ui, vj)E.

If G is a bipartite multigraph or weighted graph, then the elements bi,j are taken to be the number of edges between the vertices or the weight of the edge (ui, vj), respectively.

Variations

An (a, b, c)-adjacency matrix A of a simple graph has Ai,j = a if (i, j) is an edge, b if it is not, and c on the diagonal. The Seidel adjacency matrix is a (−1, 1, 0)-adjacency matrix. This matrix is used in studying strongly regular graphs and two-graphs. [3]

The distance matrix has in position (i, j) the distance between vertices vi and vj. The distance is the length of a shortest path connecting the vertices. Unless lengths of edges are explicitly provided, the length of a path is the number of edges in it. The distance matrix resembles a high power of the adjacency matrix, but instead of telling only whether or not two vertices are connected (i.e., the connection matrix, which contains boolean values), it gives the exact distance between them.

Examples

Undirected graphs

The convention followed here (for undirected graphs) is that each edge adds 1 to the appropriate cell in the matrix, and each loop adds 2. [4] This allows the degree of a vertex to be easily found by taking the sum of the values in either its respective row or column in the adjacency matrix.

Labeled graph Adjacency matrix
6n-graph2.svg


Coordinates are 1–6.

Symmetric group 4; Cayley graph 1,5,21 (Nauru Petersen); numbers.svg


Nauru graph

Symmetric group 4; Cayley graph 1,5,21 (adjacency matrix).svg


Coordinates are 0–23.
White fields are zeros, colored fields are ones.

Directed graphs

The adjacency matrix of a directed graph can be asymmetric. One can define the adjacency matrix of a directed graph either such that

  1. a non-zero element Aij indicates an edge from i to j or
  2. it indicates an edge from j to i.

The former definition is commonly used in graph theory and social network analysis (e.g., sociology, political science, economics, psychology). [5] The latter is more common in other applied sciences (e.g., dynamical systems, physics, network science) where A is sometimes used to describe linear dynamics on graphs. [6]

Using the first definition, the in-degrees of a vertex can be computed by summing the entries of the corresponding column and the out-degree of vertex by summing the entries of the corresponding row. When using the second definition, the in-degree of a vertex is given by the corresponding row sum and the out-degree is given by the corresponding column sum.

Labeled graphAdjacency matrix
Symmetric group 4; Cayley graph 4,9; numbers.svg


Directed Cayley graph of S 4

Symmetric group 4; Cayley graph 4,9 (adjacency matrix).svg


Coordinates are 0–23.
As the graph is directed, the matrix is not necessarily symmetric.

Trivial graphs

The adjacency matrix of a complete graph contains all ones except along the diagonal where there are only zeros. The adjacency matrix of an empty graph is a zero matrix.

Properties

Spectrum

The adjacency matrix of an undirected simple graph is symmetric, and therefore has a complete set of real eigenvalues and an orthogonal eigenvector basis. The set of eigenvalues of a graph is the spectrum of the graph. [7] It is common to denote the eigenvalues by

The greatest eigenvalue is bounded above by the maximum degree. This can be seen as result of the Perron–Frobenius theorem, but it can be proved easily. Let v be one eigenvector associated to and x the component in which v has maximum absolute value. Without loss of generality assume vx is positive since otherwise you simply take the eigenvector , also associated to . Then

For d-regular graphs, d is the first eigenvalue of A for the vector v = (1, …, 1) (it is easy to check that it is an eigenvalue and it is the maximum because of the above bound). The multiplicity of this eigenvalue is the number of connected components of G, in particular for connected graphs. It can be shown that for each eigenvalue , its opposite is also an eigenvalue of A if G is a bipartite graph. [8] In particular −d is an eigenvalue of bipartite graphs.

The difference is called the spectral gap and it is related to the expansion of G. It is also useful to introduce the spectral radius of denoted by . This number is bounded by . This bound is tight in the Ramanujan graphs, which have applications in many areas.

Isomorphism and invariants

Suppose two directed or undirected graphs G1 and G2 with adjacency matrices A1 and A2 are given. G1 and G2 are isomorphic if and only if there exists a permutation matrix P such that

In particular, A1 and A2 are similar and therefore have the same minimal polynomial, characteristic polynomial, eigenvalues, determinant and trace. These can therefore serve as isomorphism invariants of graphs. However, two graphs may possess the same set of eigenvalues but not be isomorphic. [9] Such linear operators are said to be isospectral.

Matrix powers

If A is the adjacency matrix of the directed or undirected graph G, then the matrix An (i.e., the matrix product of n copies of A) has an interesting interpretation: the element (i, j) gives the number of (directed or undirected) walks of length n from vertex i to vertex j. If n is the smallest nonnegative integer, such that for some i, j, the element (i, j) of An is positive, then n is the distance between vertex i and vertex j. This implies, for example, that the number of triangles in an undirected graph G is exactly the trace of A3 divided by 6. The adjacency matrix can be used to determine whether or not the graph is connected.

Data structures

The adjacency matrix may be used as a data structure for the representation of graphs in computer programs for manipulating graphs. The main alternative data structure, also in use for this application, is the adjacency list. [10] [11]

Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only |V|2/8 bytes to represent a directed graph, or (by using a packed triangular format and only storing the lower triangular part of the matrix) approximately |V|2/16 bytes to represent an undirected graph. Although slightly more succinct representations are possible, this method gets close to the information-theoretic lower bound for the minimum number of bits needed to represent all n-vertex graphs. [12] For storing graphs in text files, fewer bits per byte can be used to ensure that all bytes are text characters, for instance by using a Base64 representation. [13] Besides avoiding wasted space, this compactness encourages locality of reference. However, for a large sparse graph, adjacency lists require less storage space, because they do not waste any space to represent edges that are not present. [11] [14]

An alternative form of adjacency matrix (which, however, requires a larger amount of space) replaces the numbers in each element of the matrix with pointers to edge objects (when edges are present) or null pointers (when there is no edge). [14] It is also possible to store edge weights directly in the elements of an adjacency matrix. [11]

Besides the space tradeoff, the different data structures also facilitate different operations. Finding all vertices adjacent to a given vertex in an adjacency list is as simple as reading the list, and takes time proportional to the number of neighbors. With an adjacency matrix, an entire row must instead be scanned, which takes a larger amount of time, proportional to the number of vertices in the whole graph. On the other hand, testing whether there is an edge between two given vertices can be determined at once with an adjacency matrix, while requiring time proportional to the minimum degree of the two vertices with the adjacency list. [11] [14]

See also

Related Research Articles

In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph G =, a perfect matching in G is a subset M of E, such that every vertex in V is adjacent to exactly one edge in M.

Regular graph Where each vertex has the same number of neighbors

In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other. A regular graph with vertices of degree is called a ‑regular graph or regular graph of degree . Also, from the handshaking lemma, a regular graph contains an even number of vertices with odd degree.

Graph (discrete mathematics) Mathematical structure consisting of vertices and edges connecting some pairs of vertices

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

Cayley graph

In mathematics, a Cayley graph, also known as a Cayley color graph, Cayley diagram, group diagram, or color group is a graph that encodes the abstract structure of a group. Its definition is suggested by Cayley's theorem and uses a specified, set of generators for the group. It is a central tool in combinatorial and geometric group theory.

In mathematics, an incidence matrix is a logical matrix that shows the relationship between two classes of objects, usually called an incidence relation. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related and 0 if they are not. There are variations; see below.

In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. Finding a matching in a bipartite graph can be treated as a network flow problem.

In spectral graph theory, a Ramanujan graph, is a regular graph whose spectral gap is almost as large as possible. Such graphs are excellent spectral expanders. As Murty's survey paper notes, Ramanujan graphs "fuse diverse branches of pure mathematics, namely, number theory, representation theory, and algebraic geometry". These graphs are indirectly named after Srinivasa Ramanujan; their name comes from the Ramanujan–Petersson conjecture, which was used in a construction of some of these graphs.

In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time as the determinant of the Laplacian matrix of the graph. It is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.

Strongly regular graph

In graph theory, a strongly regular graph is defined as follows. Let G = be a regular graph with v vertices and degree k. G is said to be strongly regular if there are also integers λ and μ such that:

In the mathematical field of graph theory, the Laplacian matrix, also called the graph Laplacian, admittance matrix, Kirchhoff matrix or discrete Laplacian, is a matrix representation of a graph. The Laplacian matrix can be used to find many useful properties of a graph. Together with Kirchhoff's theorem, it can be used to calculate the number of spanning trees for a given graph. The sparsest cut of a graph can be approximated through the second smallest eigenvalue of its Laplacian by Cheeger's inequality. It can also be used to construct low dimensional embeddings, which can be useful for a variety of machine learning applications.

Centrality

In graph theory and network analysis, indicators of centrality assign numbers or rankings to nodes within a graph corresponding to their network position. Applications include identifying the most influential person(s) in a social network, key infrastructure nodes in the Internet or urban networks, super-spreaders of disease, and brain networks. Centrality concepts were first developed in social network analysis, and many of the terms used to measure centrality reflect their sociological origin.

In matrix theory, the Perron–Frobenius theorem, proved by Oskar Perron (1907) and Georg Frobenius (1912), asserts that a real square matrix with positive entries has a unique largest real eigenvalue and that the corresponding eigenvector can be chosen to have strictly positive components, and also asserts a similar statement for certain classes of nonnegative matrices. This theorem has important applications to probability theory ; to the theory of dynamical systems ; to economics ; to demography ; to social networks ; to Internet search engines (PageRank); and even to ranking of football teams. The first to discuss the ordering of players within tournaments using Perron–Frobenius eigenvectors is Edmund Landau.

In linear algebra, an eigenvector or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted by , is the factor by which the eigenvector is scaled.

The expander mixing lemma intuitively states that the edges of certain -regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets and is always close to the expected number of edges between them in a random -regular graph, namely .

In linear algebra, eigendecomposition is the factorization of a matrix into a canonical form, whereby the matrix is represented in terms of its eigenvalues and eigenvectors. Only diagonalizable matrices can be factorized in this way. When the matrix being factorized is normal or real symmetric matrix, the decomposition is called "spectral decomposition", derived from the Spectral theorem.

The image segmentation problem is concerned with partitioning an image into multiple regions according to some homogeneity criterion. This article is primarily concerned with graph theoretic approaches to image segmentation applying graph partitioning via minimum cut or maximum cut. Segmentation-based object categorization can be viewed as a specific case of spectral clustering applied to image segmentation.

In mathematics, a Bratteli diagram is a combinatorial structure: a graph composed of vertices labelled by positive integers ("level") and unoriented edges between vertices having levels differing by one. The notion was introduced by Ola Bratteli in 1972 in the theory of operator algebras to describe directed sequences of finite-dimensional algebras: it played an important role in Elliott's classification of AF-algebras and the theory of subfactors. Subsequently Anatoly Vershik associated dynamical systems with infinite paths in such graphs.

In the mathematical field of spectral graph theory, Brouwer's conjecture is a conjecture by Andries Brouwer on upper bounds for the intermediate sums of the eigenvalues of the Laplacian of a graph in term of its number of edges.

References

  1. Biggs, Norman (1993), Algebraic Graph Theory, Cambridge Mathematical Library (2nd ed.), Cambridge University Press, Definition 2.1, p. 7.
  2. Harary, Frank (1962), "The determinant of the adjacency matrix of a graph", SIAM Review, 4 (3): 202–210, Bibcode:1962SIAMR...4..202H, doi:10.1137/1004057, MR   0144330 .
  3. Seidel, J. J. (1968). "Strongly Regular Graphs with (−1, 1, 0) Adjacency Matrix Having Eigenvalue 3". Lin. Alg. Appl. 1 (2): 281–298. doi: 10.1016/0024-3795(68)90008-6 .
  4. Shum, Kenneth; Blake, Ian (2003-12-18). "Expander graphs and codes". Volume 68 of DIMACS series in discrete mathematics and theoretical computer science. Algebraic Coding Theory and Information Theory: DIMACS Workshop, Algebraic Coding Theory and Information Theory. American Mathematical Society. p. 63.
  5. Borgatti, Steve; Everett, Martin; Johnson, Jeffrey (2018), Analyzing Social Networks (2nd ed.), SAGE, p. 20
  6. Newman, Mark (2018), Networks (2nd ed.), Oxford University Press, p. 110
  7. Biggs (1993), Chapter 2 ("The spectrum of a graph"), pp. 7–13.
  8. Brouwer, Andries E.; Haemers, Willem H. (2012), "1.3.6 Bipartite graphs", Spectra of Graphs, Universitext, New York: Springer, pp. 6–7, doi:10.1007/978-1-4614-1939-6, ISBN   978-1-4614-1938-9, MR   2882891
  9. Godsil, Chris; Royle, Gordon Algebraic Graph Theory, Springer (2001), ISBN   0-387-95241-1, p.164
  10. Goodrich & Tamassia (2015), p. 361: "There are two data structures that people often use to represent graphs, the adjacency list and the adjacency matrix."
  11. 1 2 3 4 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Section 22.1: Representations of graphs", Introduction to Algorithms (Second ed.), MIT Press and McGraw-Hill, pp. 527–531, ISBN   0-262-03293-7 .
  12. Turán, György (1984), "On the succinct representation of graphs", Discrete Applied Mathematics , 8 (3): 289–294, doi: 10.1016/0166-218X(84)90126-4 , MR   0749658 .
  13. McKay, Brendan, Description of graph6 and sparse6 encodings .
  14. 1 2 3 Goodrich, Michael T.; Tamassia, Roberto (2015), Algorithm Design and Applications, Wiley, p. 363.