Conectividad algebraica

Dado un grafo Γ, la conectividad algebraica de un grafo es el segundo autovalor más pequeño no nulo de la matriz laplaciana $\mathcal{L}(\Gamma)$^[1] —por ello se le signa como λ₂—. También se denomina salto espectral, gap o parámetro de Fiedler.^[2]

Este autovalor es mayor que cero si y sólo si Γ es un grafo conexo. La medida de este valor refleja la conectividad del grafo en general, y se ha utilizado para el análisis de la sincronización de nodos en redes. A medida que λ₂ se hace más pequeño el grafo adquiere una estructura más modular.

En los modelos para la sincronización de nodos en redes, como el modelo de Kuramoto, la matriz laplaciana surge de manera natural (a través del laplaciano discreto), por lo que la conectividad algebraica da una idea de la facilidad con la que la red se sincronizará. Sin embargo, otras medidas, tales como la media de la distancia también se puede utilizar,^[3] y, de hecho, la conectividad algebraica está estrechamente relacionado con el inverso de la distancia media.^[4]

Al autovector asociado a λ₂ se le denomina $\vec u_2$ vector de Fiedler , y se usa para la partición de grafos. Por ejemplo, sea:

grafo	matriz laplaciana
	$\left(\begin{array}{rrrrrr} 2 & -1 & 0 & 0 & -1 & 0\\ -1 & 3 & -1 & 0 & -1 & 0\\ 0 & -1 & 2 & -1 & 0 & 0\\ 0 & 0 & -1 & 3 & -1 & -1\\ -1 & -1 & 0 & -1 & 3 & 0\\ 0 & 0 & 0 & -1 & 0 & 1\\ \end{array}\right)$

El vector de Fiedler es

(0.415, 0.309, 0.069, -0.221, 0.221, -0.794).

Los valores negativos se asocian con el nodo 6, y el punto de articulación entre vecinos, el nodo 4, mientras que los valores positivos están asociados con los otros nodos. El signo de los valores en el vector de Fiedler puede ser utilizado para dividir el gráfos en componentes: {1, 2, 3, 5} y {4, 6}. Por otra parte, el valor de 0,069 (que es cercana a cero) se pueden colocar en una clase propia, la partición del grafo en tres componentes: {1, 2, 5}, {3} y {6 4}.

Este autovalor ha sido investigado ampliamente por ser un invariante muy importante. El principio de Courant-Fischer dice que:^[5]

$\lambda_2^{\Gamma}=\min_{\begin{array}{r} \vec{u} \perp \vec{1} \\ \vec{u}\neq\vec{0}\end{array}}\frac{(\hat{\mathcal{L}}\vec{u},\vec u)}{(\vec u,\vec u)}$

Fiedler obtiene otra expresión para grafos con pesos a_μν no nulos:

$\lambda_2^{\Gamma}=2n\min_{\begin{array}{r} \vec{u} \perp \vec{1} \\ \vec{u}\neq\vec{0} \end{array}}{\frac{\sum_{\mu\nu}{a_{\mu\nu}(u_{\mu}-u_{\nu})^2}}{\sum_{\mu\nu}{(u_{\mu}-u_{\nu})^2}}}$

Aplicaciones

La conectividad algebráica da un límite inferior al diámetro de un grafo Γ:

$\mathtt{diam}(\Gamma)\geqslant\frac{4}{n\lambda_2^{\Gamma}}$

Referencias

1. ↑ Weisstein, Eric W. "Algebraic Connectivity." De MathWorld--A Wolfram Web Resource.
2. ↑ M. Fiedler, "Algebraic Connectivity of Graphs", Czech. Math. J. 23:298--305, 1973
3. ↑ D. Watts,Six Degrees: The Science of aEdad Conectado, Vintage, 2003.
4. ↑ 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.
5. ↑ Nota: $\vec{1}=\left(\begin{array}{r} 1 \\ 1 \\ \vdots \\ 1 \\ \end{array}\right) \qquad \vec{0}=\left(\begin{array}{r} 0 \\ 0 \\ \vdots \\ 0 \\ \end{array}\right)$