Algebraic connectivity
The magnitude of this value reflects how well connected the overall graph is.
The algebraic connectivity of undirected graphs with nonnegative weights is
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.
[10] 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.
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 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:
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:
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.
