La conectividad algebraica (también conocida como valor de Fiedler o valor propio de Fiedler en honor a Miroslav Fiedler ) de un gráfico G es el segundo valor propio más pequeño (contando múltiples valores propios por separado) de la matriz laplaciana de G. [1] Este valor propio es mayor que 0 si y solo si G es un gráfico conexo . Este es un corolario del hecho de que el número de veces que 0 aparece como valor propio en el laplaciano es el número de componentes conectados en el gráfico. La magnitud de este valor refleja qué tan bien conectado está el gráfico general. Se ha utilizado para analizar la robustez y sincronizabilidad de las redes.
La conectividad algebraica de gráficos no dirigidos con pesos no negativos, siendo la desigualdad estricta si y sólo si G es conexo. Sin embargo, la conectividad algebraica puede ser negativa para grafos dirigidos generales, incluso si G es un grafo conexo . [2] Además, el valor de la conectividad algebraica está limitado arriba por la conectividad tradicional (vértice) del gráfico . [3] Si el número de vértices de un gráfico conectado no dirigido con pesos de borde no negativos es n y el diámetro es D , también se sabe que la conectividad algebraica está limitada por debajo de , [4] y de hecho (en un resultado debido a Brendan McKay ) por . [5] Para el gráfico con 6 nodos que se muestra arriba (n=6,D=3), estos límites significan, 4/18 = 0,222 ≤ conectividad algebraica 0,722 ≤ conectividad 1.
A diferencia de la conectividad tradicional [ se necesita aclaración ] , la conectividad algebraica depende del número de vértices, así como de la forma en que se conectan los vértices. En gráficos aleatorios , la conectividad algebraica disminuye con el número de vértices y aumenta con el grado promedio . [6]
La definición exacta de la conectividad algebraica depende del tipo de laplaciano utilizado. Fan Chung ha desarrollado una extensa teoría utilizando una versión reescalada del Laplaciano, eliminando la dependencia del número de vértices, de modo que los límites son algo diferentes. [7]
En modelos de sincronización en redes, como el modelo de Kuramoto , la matriz laplaciana surge de forma natural, por lo que la conectividad algebraica da una indicación de la facilidad con la que se sincronizará la red. [8] También se pueden utilizar otras medidas, como la distancia promedio (longitud del camino característico), [9] y, de hecho, la conectividad algebraica está estrechamente relacionada con la distancia promedio (recíproca de la). [5]
La conectividad algebraica también se relaciona con otros atributos de conectividad, como el número isoperimétrico , que está acotado por debajo de la mitad de la conectividad algebraica. [10]
La teoría original relacionada con la conectividad algebraica fue elaborada por Miroslav Fiedler . [11] [12] En su honor, el vector propio asociado con la conectividad algebraica ha sido denominado vector de Fiedler . El vector de Fiedler se puede utilizar para dividir un gráfico.
Para el gráfico de ejemplo de la sección introductoria, el vector de Fiedler es . Los valores negativos están asociados al vértice 6 mal conectado, y al punto de articulación vecino , vértice 4; mientras que los valores positivos están asociados con los demás vértices. Por lo tanto, los signos de los valores en el vector de Fiedler se pueden usar para dividir este gráfico en dos componentes: . Alternativamente, el valor de 0,069 (que es cercano a cero) se puede colocar en una clase propia, dividiendo el gráfico en tres componentes: o moverlo a la otra partición , como se muestra en la imagen. Los valores al cuadrado de los componentes del vector de Fiedler, que suman uno desde que el vector está normalizado, pueden interpretarse como probabilidades de los puntos de datos correspondientes que se asignarán a la partición basada en signos.
Incluso si G está casi fuertemente conectado, lo que equivale a que G contenga un árbol de expansión dirigido, a (G) aún puede no ser positivo, como lo indican la estrella en explosión y el Teorema 1.
