Algebraic connectivity: Difference between revisions

Content deleted Content added

Inline

Revision as of 14:41, 18 June 2021

An example graph, with 6 vertices, diameter 3, connectivity 1, and algebraic connectivity 0.722

The algebraic connectivity (also known as Fiedler value or Fiedler eigenvalue) 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 truncated icosahedron or Buckminsterfullerene graph has a traditional connectivity of 3, and an algebraic connectivity of 0.243.

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 the graph, ${\text{algebraic connectivity}}\leq {\text{connectivity}}$ .^[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 connectivity, the algebraic connectivity is dependent on the 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

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\}}$ .

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. 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.
^ J.L. Gross and J. Yellen. Handbook of Graph Theory, CRC Press, 2004, page 314.
^ J.L. Gross and J. Yellen. Handbook of Graph Theory, CRC Press, 2004, page 571.
^ ^a ^b Bojan Mohar, The Laplacian Spectrum of Graphs, in Graph Theory, Combinatorics, and Applications, Vol. 2, Ed. Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk, Wiley, 1991, pp. 871–898.
^ Synchronization and Connectivity of Discrete Complex Systems, Michael Holroyd, International Conference on Complex Systems, 2006.
^ F. Chung. Spectral Graph Theory, Providence, RI: Amer. Math. Soc., 1997.[1]
^ Tiago Pereira, Stability of Synchronized Motion in Complex Networks, arXiv:1112.2297v1, 2011.
^ D. Watts, Six Degrees: The Science of a Connected Age, Vintage, 2003.
^ Norman Biggs. Algebraic Graph Theory, 2nd ed, Cambridge University Press, 1993, pp. 28 & 58.
^ M. Fiedler. "Algebraic connectivity of Graphs", Czechoslovak Mathematical Journal 23(98) (1973), 298–305.
^ M. Fiedler. "Laplacian of graphs and algebraic connectivity", Combinatorics and Graph Theory (Warsaw, 1987), Banach Center Publications 25(1) (1989), 57–70.

[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. 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] J.L. Gross and J. Yellen. Handbook of Graph Theory, CRC Press, 2004, page 314.

[4] J.L. Gross and J. Yellen. Handbook of Graph Theory, CRC Press, 2004, page 571.

[Mohar-5] Bojan Mohar, The Laplacian Spectrum of Graphs, in Graph Theory, Combinatorics, and Applications, Vol. 2, Ed. Y. Alavi, G. Chartrand, O. R. Oellermann, A. J. Schwenk, Wiley, 1991, pp. 871–898.

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

[7] F. Chung. Spectral Graph Theory, Providence, RI: Amer. Math. Soc., 1997.[1]

[8] Tiago Pereira, Stability of Synchronized Motion in Complex Networks, arXiv:1112.2297v1, 2011.

[9] D. Watts, Six Degrees: The Science of a Connected Age, Vintage, 2003.

[10] Norman Biggs. Algebraic Graph Theory, 2nd ed, Cambridge University Press, 1993, pp. 28 & 58.

[11] M. Fiedler. "Algebraic connectivity of Graphs", Czechoslovak Mathematical Journal 23(98) (1973), 298–305.

[12] M. Fiedler. "Laplacian of graphs and algebraic connectivity", Combinatorics and Graph Theory (Warsaw, 1987), Banach Center Publications 25(1) (1989), 57–70.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Line 1: / Line 1: @@
 [[Image:6n-graf.svg|thumb|250px|An example graph, with 6 vertices, [[Distance (graph theory)|diameter]] 3, [[connectivity (graph theory)|connectivity]] 1, and algebraic connectivity 0.722]]
-The '''algebraic connectivity''' (also known as ''Fiedler value'' or ''Fiedler eigenvalue'') of a [[Graph (discrete mathematics)|graph]] ''G'' is the second-smallest [[eigenvalue]] (counting multiple eigenvalues separately) of the [[Laplacian matrix]] of ''G''.<ref>Weisstein, Eric W. "[http://mathworld.wolfram.com/AlgebraicConnectivity.html Algebraic Connectivity]." From MathWorld--A Wolfram Web Resource.</ref> 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 analysing the robustness and [[synchronizability]] of networks.
+The '''algebraic connectivity''' (also known as ''Fiedler value'' or ''Fiedler eigenvalue'') of a [[Graph (discrete mathematics)|graph]] ''G'' is the second-smallest [[eigenvalue]] (counting multiple eigenvalues separately) of the [[Laplacian matrix]] of ''G''.<ref>Weisstein, Eric W. "[http://mathworld.wolfram.com/AlgebraicConnectivity.html Algebraic Connectivity]." From MathWorld--A Wolfram Web Resource.</ref> 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 ==
 [[Image:C60a.png|thumb|The [[truncated icosahedron]] or [[Buckminsterfullerene]] graph has a traditional [[connectivity (graph theory)|connectivity]] of 3, and an algebraic connectivity of 0.243.]]
-The algebraic connectivity of a [[Graph (discrete mathematics)|graph]] ''G'' can be positive or negative, even if ''G'' is a [[connected graph]].<ref name="wu2004">{{cite journal|author-last=Wu|author-first=Chai Wai| title=Algebraic connectivity of directed graphs| year=2005|volume=53|number=3|pages=203-223|doi=10.1080/03081080500054810| journal=Linear and Multilinear algebra | publisher=[[Taylor and Francis]]| quote=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.}}</ref> Furthermore, the value of the algebraic connectivity is bounded above by the traditional (vertex) [[connectivity (graph theory)|connectivity]] of the graph, <math>\text{algebraic connectivity} \le \text{connectivity}</math>.<ref>J.L. Gross and J. Yellen. ''Handbook of Graph Theory'', CRC Press, 2004, page 314.</ref>  If the number of vertices of an undirected connected graph with nonnegative edge weights is ''n'' and the [[Distance (graph theory)|diameter]] is ''D'', the algebraic connectivity is also known to be bounded below by <math>\text{algebraic  connectivity} \ge \frac{1}{nD} </math>,<ref>J.L. Gross and J. Yellen. ''Handbook of Graph Theory'', CRC Press, 2004, page 571.</ref> and in fact (in a result due to [[Brendan McKay (mathematician)|Brendan McKay]]) by <math>\frac{4}{nD}</math>.<ref name="Mohar">[[Bojan Mohar]], [http://www.fmf.uni-lj.si/~mohar/Papers/Spec.pdf The Laplacian Spectrum of Graphs], in ''Graph Theory, Combinatorics, and Applications'', Vol. 2, Ed. Y. Alavi, G. Chartrand, [[Ortrud Oellermann|O. R. Oellermann]], A. J. Schwenk, Wiley, 1991, pp. 871–898.</ref> For the graph with 6 nodes show above (n=6,D=3) these bound means, 4/18&nbsp;=&nbsp;0.222&nbsp;≤&nbsp;algebraic connectivity 0.722&nbsp; ≤&nbsp;connectivity 1.
+The algebraic connectivity of undirected graphs with nonnegative weights, <math>a(G)\geq0</math> 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]].<ref name="wu2004">{{cite journal|author-last=Wu|author-first=Chai Wai| title=Algebraic connectivity of directed graphs| year=2005|volume=53|number=3|pages=203-223|doi=10.1080/03081080500054810| journal=Linear and Multilinear algebra | publisher=[[Taylor and Francis]]| quote=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.}}</ref> Furthermore, the value of the algebraic connectivity is bounded above by the traditional (vertex) [[connectivity (graph theory)|connectivity]] of the graph, <math>\text{algebraic connectivity} \le \text{connectivity}</math>.<ref>J.L. Gross and J. Yellen. ''Handbook of Graph Theory'', CRC Press, 2004, page 314.</ref>  If the number of vertices of an undirected connected graph with nonnegative edge weights is ''n'' and the [[Distance (graph theory)|diameter]] is ''D'', the algebraic connectivity is also known to be bounded below by <math>\text{algebraic  connectivity} \ge \frac{1}{nD} </math>,<ref>J.L. Gross and J. Yellen. ''Handbook of Graph Theory'', CRC Press, 2004, page 571.</ref> and in fact (in a result due to [[Brendan McKay (mathematician)|Brendan McKay]]) by <math>\frac{4}{nD}</math>.<ref name="Mohar">[[Bojan Mohar]], [http://www.fmf.uni-lj.si/~mohar/Papers/Spec.pdf The Laplacian Spectrum of Graphs], in ''Graph Theory, Combinatorics, and Applications'', Vol. 2, Ed. Y. Alavi, G. Chartrand, [[Ortrud Oellermann|O. R. Oellermann]], A. J. Schwenk, Wiley, 1991, pp. 871–898.</ref> For the graph with 6 nodes show above (n=6,D=3) these bound means, 4/18&nbsp;=&nbsp;0.222&nbsp;≤&nbsp;algebraic connectivity 0.722&nbsp; ≤&nbsp;connectivity 1.
 Unlike the traditional connectivity, the algebraic connectivity is dependent on the number of vertices, as well as the way in which vertices are connected.  In [[random graph]]s, the algebraic connectivity decreases with the number of vertices, and increases with the average [[degree (graph theory)|degree]].<ref>[http://www.cs.virginia.edu/~mjh7v/papers/ICCSpresentation.ppt Synchronization and Connectivity of Discrete Complex Systems], Michael Holroyd, International Conference on Complex Systems, 2006.</ref>

Revision as of 14:41, 18 June 2021

Properties

Fiedler vector

Partitioning a graph using the Fiedler vector

See also

References