Algebraic connectivity

Last updated September 24, 2024

The algebraic connectivity (also known as Fiedler value or Fiedler eigenvalue after Miroslav Fiedler) of a graph G is the second-smallest eigenvalue (counting multiple eigenvalues separately) of the Laplacian matrix of G.^[1] This eigenvalue is greater than 0 if and only if G is a connected graph. This is a corollary to the fact that the number of times 0 appears as an eigenvalue in the Laplacian is the number of connected components in the graph. The magnitude of this value reflects how well connected the overall graph is. It has been used in analyzing the robustness and synchronizability of networks.

Properties

The algebraic connectivity of undirected graphs with nonnegative weights, $a(G)\geq 0$ with the inequality being strict if and only if G is connected. However, the algebraic connectivity can be negative for general directed graphs, even if G is a connected graph.^[2] Furthermore, the value of the algebraic connectivity is bounded above by the traditional (vertex) connectivity of a graph, ${\text{algebraic connectivity}}\leq {\text{connectivity}}$ , unless the graph is complete (the algebraic connectivity of a complete graph $K n$ is its order $n$ ).^[3] If the number of vertices of an undirected connected graph with nonnegative edge weights is n and the diameter is D, the algebraic connectivity is also known to be bounded below by ${\text{algebraic connectivity}}\geq {\frac {1}{nD}}$ ,^[4] and in fact (in a result due to Brendan McKay) by ${\frac {4}{nD}}$ .^[5] For the graph with 6 nodes show above (n=6,D=3) these bound means, 4/18 = 0.222 ≤ algebraic connectivity 0.722 ≤ connectivity 1.

Unlike the traditional form of graph connectivity, defined by local configurations whose removal would disconnect the graph, the algebraic connectivity is dependent on the global number of vertices, as well as the way in which vertices are connected. In random graphs, the algebraic connectivity decreases with the number of vertices, and increases with the average degree.^[6]

The exact definition of the algebraic connectivity depends on the type of Laplacian used. Fan Chung has developed an extensive theory using a rescaled version of the Laplacian, eliminating the dependence on the number of vertices, so that the bounds are somewhat different.^[7]

In models of synchronization on networks, such as the Kuramoto model, the Laplacian matrix arises naturally, so the algebraic connectivity gives an indication of how easily the network will synchronize.^[8] Other measures, such as the average distance (characteristic path length) can also be used,^[9] and in fact the algebraic connectivity is closely related to the (reciprocal of the) average distance.^[5]

The algebraic connectivity also relates to other connectivity attributes, such as the isoperimetric number, which is bounded below by half the algebraic connectivity.^[10]

Fiedler vector

The original theory related to algebraic connectivity was produced by Miroslav Fiedler.^[11]^[12] In his honor the eigenvector associated with the algebraic connectivity has been named the Fiedler vector. The Fiedler vector can be used to partition a graph.

Partitioning a graph using the Fiedler vector

Partitioning into two connected graphs. 6n-graf2.svg — Partitioning into two connected graphs.

For the example graph in the introductory section, the Fiedler vector is ${\textstyle {\begin{pmatrix}0.415&0.309&0.069&-0.221&0.221&-0.794\end{pmatrix}}}$ . The negative values are associated with the poorly connected vertex 6, and the neighbouring articulation point, vertex 4; while the positive values are associated with the other vertices. The signs of the values in the Fiedler vector can therefore be used to partition this graph into two components: ${\textstyle \{1,2,3,5\},\{4,6\}}$ . Alternatively, the value of 0.069 (which is close to zero) can be placed in a class of its own, partitioning the graph into three components: ${\textstyle \{1,2,5\},\{3\},\{4,6\}}$ or moved to the other partition ${\textstyle \{1,2,5\},\{3,4,6\}}$ , as pictured. The squared values of the components of the Fiedler vector, summing up to one since the vector is normalized, can be interpreted as probabilities of the corresponding data points to be assigned to the sign-based partition.

Related Research Articles

In graph theory, 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 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 internal vertex are equal to each other. A regular graph with vertices of degree $k$ is called a $k$ ‑regular graph or regular graph of degree $k$ .

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.

<span class="mw-page-title-main">Component (graph theory)</span> Maximal subgraph whose vertices can reach each other

In graph theory, a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph. The components of any graph partition its vertices into disjoint sets, and are the induced subgraphs of those sets. A graph that is itself connected has exactly one component, consisting of the whole graph. Components are sometimes called connected components.

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. The structure and symmetry of Cayley graphs makes them particularly good candidates for constructing expander graphs.

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 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 from the determinant of a submatrix of the graph's Laplacian matrix; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

In mathematics, the discrete Laplace operator is an analog of the continuous Laplace operator, defined so that it has meaning on a graph or a discrete grid. For the case of a finite-dimensional graph, the discrete Laplace operator is more commonly called the Laplacian matrix.

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. Named after Pierre-Simon Laplace, the graph Laplacian matrix can be viewed as a matrix form of the negative discrete Laplace operator on a graph approximating the negative continuous Laplacian obtained by the finite difference method.

In the mathematical field of graph theory, a graph $G$ is symmetric if, given any two pairs of adjacent vertices $u 1 — v 1$ and $u 2 — v 2$ of $G$ , there is an automorphism

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

Miroslav Fiedler was a Czech mathematician known for his contributions to linear algebra, graph theory and algebraic graph theory.

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graph $Q n$ is the graph formed from the vertices and edges of an $n$ -dimensional hypercube. For instance, the cube graph $Q 3$ is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. $Q n$ has $2 n$ vertices, $2 n - 1 n$ edges, and is a regular graph with $n$ edges touching each vertex.

In mathematics, the Cheeger constant of a graph is a numerical measure of whether or not a graph has a "bottleneck". The Cheeger constant as a measure of "bottleneckedness" is of great interest in many areas: for example, constructing well-connected networks of computers, card shuffling. The graph theoretical notion originated after the Cheeger isoperimetric constant of a compact Riemannian manifold.

In graph theory, a random geometric graph (RGG) is the mathematically simplest spatial network, namely an undirected graph constructed by randomly placing N nodes in some metric space and connecting two nodes by a link if and only if their distance is in a given range, e.g. smaller than a certain neighborhood radius, r.

<span class="mw-page-title-main">Spectral clustering</span> Clustering methods

In multivariate statistics, spectral clustering techniques make use of the spectrum (eigenvalues) of the similarity matrix of the data to perform dimensionality reduction before clustering in fewer dimensions. The similarity matrix is provided as an input and consists of a quantitative assessment of the relative similarity of each pair of points in the dataset.

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 graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

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

↑ Weisstein, Eric W. "Algebraic Connectivity." From MathWorld--A Wolfram Web Resource.
↑ Wu, Chai Wai (2005). "Algebraic connectivity of directed graphs". Linear and Multilinear Algebra. 53 (3). Taylor and Francis: 203–223. doi:10.1080/03081080500054810. S2CID 121368189. Even if G is quasi-strongly connected, which is equivalent to G containing a directed spanning tree, a(G) can still be nonpositive as the exploding star and Theorem 1 indicate.
↑ Fiedler, Miroslav (1973). "Algebraic connectivity of graphs". Czechoslovak Mathematical Journal. 23 (2): 298–305. doi:10.21136/cmj.1973.101168. ISSN 0011-4642.
↑ Gross & Yellen 2004 , p. 571
1 2 Mohar, Bojan (1991). "The Laplacian Spectrum of Graphs" (PDF). In Alavi, Y.; Chartrand, G.; Oellermann, O.R.; Schwenk, A.J. (eds.). Graph Theory, Combinatorics, and Applications. Proceedings of the sixth quadrennial international conference on the theory and applications of graphs. Vol. 2. Wiley. pp. 871–898. Zbl 0840.05059.
↑ Holroyd, Michael (2006). "Synchronization and Connectivity of Discrete Complex Systems". International Conference on Complex Systems.
↑ Chung, F.R.K. (1997). Spectral Graph Theory. Regional Conference Series in Mathematics. Vol. 92. Amer. Math. Soc. ISBN 0-8218-8936-2. Incomplete revised edition
↑ Pereira, Tiago (2011). "Stability of Synchronized Motion in Complex Networks". arXiv: 1112.2297 [nlin.AO].
↑ Watts, D. (2003). Six Degrees: The Science of a Connected Age. Vintage. ISBN 0-434-00908-3. OCLC 51622138.
↑ Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge University Press. pp. 28, 58. ISBN 0-521-45897-8.
↑ Fiedler, M. (1973). "Algebraic connectivity of Graphs". Czechoslovak Mathematical Journal. 23 (98): 298–305. doi: 10.21136/CMJ.1973.101168 . MR 0318007. Zbl 0265.05119.
↑ Fiedler, M. (1989) [1987]. "Laplacian of graphs and algebraic connectivity". Banach Center Publications. 25 (1): 57–70. doi: 10.4064/-25-1-57-70 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Weisstein, Eric W. "Algebraic Connectivity." From MathWorld--A Wolfram Web Resource.

[wu2004-2] Wu, Chai Wai (2005). "Algebraic connectivity of directed graphs". Linear and Multilinear Algebra. 53 (3). Taylor and Francis: 203–223. doi:10.1080/03081080500054810. S2CID 121368189. Even if G is quasi-strongly connected, which is equivalent to G containing a directed spanning tree, a(G) can still be nonpositive as the exploding star and Theorem 1 indicate.

[3] Fiedler, Miroslav (1973). "Algebraic connectivity of graphs". Czechoslovak Mathematical Journal. 23 (2): 298–305. doi:10.21136/cmj.1973.101168. ISSN 0011-4642.

[4] Gross & Yellen 2004 , p. 571

[Mohar-5] 1 2 Mohar, Bojan (1991). "The Laplacian Spectrum of Graphs" (PDF). In Alavi, Y.; Chartrand, G.; Oellermann, O.R.; Schwenk, A.J. (eds.). Graph Theory, Combinatorics, and Applications. Proceedings of the sixth quadrennial international conference on the theory and applications of graphs. Vol. 2. Wiley. pp. 871–898. Zbl 0840.05059.

[6] Holroyd, Michael (2006). "Synchronization and Connectivity of Discrete Complex Systems". International Conference on Complex Systems.

[7] Chung, F.R.K. (1997). Spectral Graph Theory. Regional Conference Series in Mathematics. Vol. 92. Amer. Math. Soc. ISBN 0-8218-8936-2. Incomplete revised edition

[8] Pereira, Tiago (2011). "Stability of Synchronized Motion in Complex Networks". arXiv: 1112.2297 [nlin.AO].

[9] Watts, D. (2003). Six Degrees: The Science of a Connected Age. Vintage. ISBN 0-434-00908-3. OCLC 51622138.

[10] Biggs, Norman (1993). Algebraic Graph Theory (2nd ed.). Cambridge University Press. pp. 28, 58. ISBN 0-521-45897-8.

[11] Fiedler, M. (1973). "Algebraic connectivity of Graphs". Czechoslovak Mathematical Journal. 23 (98): 298–305. doi: 10.21136/CMJ.1973.101168 . MR 0318007. Zbl 0265.05119.

[12] Fiedler, M. (1989) [1987]. "Laplacian of graphs and algebraic connectivity". Banach Center Publications. 25 (1): 57–70. doi: 10.4064/-25-1-57-70 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]