Conectividad algebraica

La conectividad algebraica (también conocida como valor de Fiedler o autovalor de Fiedler , en honor a Miroslav Fiedler ) de un grafo G es el segundo autovalor más pequeño (contando los autovalores múltiples por separado) de la matriz laplaciana de G. ^{[ 1 ]} Este autovalor es mayor que 0 si y solo si G es un grafo conexo . Esto es un corolario del hecho de que el número de veces que aparece 0 como autovalor en la matriz laplaciana es el número de componentes conexas en el grafo. La magnitud de este valor refleja cuán bien conectado está el grafo en general. Se ha utilizado para analizar la robustez y la sincronizabilidad de las redes.

La conectividad algebraica de grafos no dirigidos con pesos no negativos es${\displaystyle a(G)\geq 0}$, siendo la desigualdad estricta si y solo 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á acotado superiormente por la conectividad tradicional (de vértices) de un grafo,${\displaystyle {\text{conectividad algebraica}}\leq {\text{conectividad}}}$, a menos que el grafo sea completo (la conectividad algebraica de un grafo completo K _n es su orden n ). ^{[ 3 ]} Para un grafo conexo no dirigido con pesos de aristas no negativos, n vértices y diámetro D , también se sabe que la conectividad algebraica está acotada inferiormente por${\textstyle {\frac {1}{nD}}}$, ^{[ 4 ]} y de hecho (en un resultado debido a Brendan McKay ) por${\textstyle {\frac {4}{nD}}}$. ^{[ 5 ]} Para el gráfico de ejemplo con 6 nodos que se muestra arriba (${\textstyle n=6,D=3}$), estos límites se calcularían de la siguiente manera:$${\displaystyle 4/18=0.222\leq {\text{conectividad algebraica 0.722}}\leq {\text{conectividad 1.}}}$$A diferencia de la forma tradicional de conectividad de grafos , definida por configuraciones locales cuya eliminación desconectaría el grafo, la conectividad algebraica depende del número global de vértices, así como de la forma en que estos se conectan. En grafos 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 teoría extensa utilizando una versión reescalada del laplaciano, eliminando la dependencia del número de vértices, por lo que los límites son algo diferentes. ^{[ 7 ]}

En los modelos de sincronización en redes, como el modelo de Kuramoto , la matriz laplaciana surge de forma natural, por lo que la conectividad algebraica indica la facilidad con la que la red se sincronizará. ^{[ 8 ]} También se pueden utilizar otras medidas, como la distancia media (longitud de trayectoria característica), ^{[ 9 ]} y, de hecho, la conectividad algebraica está estrechamente relacionada con la distancia media (o su recíproca). ^{[ 5 ]}

La conectividad algebraica también se relaciona con otros atributos de conectividad, como el número isoperimétrico , que está acotado inferiormente por la mitad de la conectividad algebraica. ^{[ 10 ]}

La teoría original relacionada con la conectividad algebraica fue desarrollada 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 puede utilizarse para particionar un grafo.

Particionamiento de un grafo utilizando el vector de Fiedler.

Para el gráfico de ejemplo en la sección introductoria, el vector de Fiedler es${\textstyle {\begin{pmatrix}0.415&0.309&0.069&-0.221&0.221&-0.794\end{pmatrix}}}$Los valores negativos están asociados con el vértice 6, que presenta poca conectividad, y con el punto de articulación vecino , el 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 pueden utilizarse para dividir este grafo en dos componentes:${\textstyle \{1,2,3,5\},\{4,6\}}$Alternativamente, el valor de 0,069 (que está cerca de cero) puede colocarse en una clase propia, dividiendo el gráfico en tres componentes:${\textstyle \{1,2,5\},\{3\},\{4,6\}}$o se trasladó a la otra partición${\textstyle \{1,2,5\},\{3,4,6\}}$, as pictured. 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.

• Connectivity (graph theory)
• Graph property