Algebraic connectivity
The algebraic connectivity (also known as Fiedler value or Fiedler eigenvalue after
Properties
The algebraic connectivity of undirected graphs with nonnegative weights, 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
Unlike the traditional connectivity[clarification needed], 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
Fiedler vector
The original theory related to algebraic connectivity was produced by
Partitioning a graph using the Fiedler vector
For the example graph in the introductory section, the Fiedler vector is . The negative values are associated with the poorly connected vertex 6, and the neighbouring
See also
References
- ^ Weisstein, Eric W. "Algebraic Connectivity." From MathWorld--A Wolfram Web Resource.
- 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.
- ISBN 0-203-49020-7.
- ^ Gross & Yellen 2004, p. 571
- ^ ]
- ^ Holroyd, Michael (2006). "Synchronization and Connectivity of Discrete Complex Systems". International Conference on Complex Systems.
- ].
- OCLC 51622138.
- ISBN 0-521-45897-8.
- Zbl 0265.05119.
- .