Conectividad (teoría de grafos)

En teoría de grafos y análisis de redes sociales, la conectividad de un grafo o red social refiere al mínimo número de elementos (vértices o aristas) que se necesitan para, al ser removidos, dividir al grafo o red en componentes aisladas. A estos vértices o aristas críticos se les denomina vértices de corte o aristas de corte, respectivamente.^[1]​

La conectividad de un grafo es una medida de su cohesión o robustez. Intuitivamente, un grafo es cohesivo si posee muchas aristas, si los vértices tienen grados relativamente altos, si tiene muchos caminos cortos entre pares de vértices, o si tiene distancias pequeñas (y por tanto un diámetro pequeño) en relación con su tamaño. Por el contrario, un grafo más «vulnerable» corre el riesgo de volverse inconexo si se le retiran unas pocas aristas o vértices.^[1]​

La conectividad de vértices, nodos o puntos de un grafo ${displaystyle G}$, denotada ${displaystyle kappa (G)}$, es el número mínimo ${displaystyle kappa }$ para el que el grafo tiene un corte de nodos-${displaystyle kappa }$.^[2]​ Así, si el grafo es inconexo, entonces ${displaystyle kappa (G)=0}$, porque no hay que quitar ningún vértice; si el grafo tiene un punto de corte, entonces ${displaystyle kappa (G)=1}$, porque basta quitar un único vértice para que el grafo se vuelva inconexo, y así sucesivamente. Además, para cualquier valor ${displaystyle kleq kappa (G)}$, el grafo se dice que es ${displaystyle k}$-conexo o ${displaystyle k}$-conectado por nodos. Note que un grafo completo ${displaystyle K_{n}}$ no tiene puntos de corte, y que la única forma de desconectarlo es quitando ${displaystyle n-1}$ vértices, con lo que se obtiene el grafo trivial. Por lo tanto, κ${displaystyle (K_{n})=n-1}$.^[1]​

Análogamente, la conectividad de aristas o conectividad lineal, ${displaystyle lambda (G)}$, es el número mínimo ${displaystyle lambda }$ para el que el grafo tiene un corte de aristas-${displaystyle lambda }$.^[2]​ Además, para cualquier valor ${displaystyle lleq lambda (G)}$, el grafo se dice que es ${displaystyle l}$-linealmente conexo.^[1]​

Dado un grafo dirigido, un par de vértices está:^[1]​

Si se cumple alguno de estos tipos de conexiones, entonces se cumplen todos los tipos anteriores.^[1]​

En el contexto del análisis de redes sociales, para las redes sociales representadas como grafos ponderados, es decir, con pesos en las aristas, el valor de un camino o semicamino puede definirse como el valor mínimo de todas las aristas que contiene.^[3]​ Un camino a nivel c es un camino entre un par de vértices tal que todas las aristas que contiene son mayores o iguales al valor c.^[4]​ Dos vértices son accesibles a nivel c si existe un camino a nivel c entre ellos.^[5]​

Un grafo no dirigido en que todos sus vértices están conectados por un camino es un grafo conexo. Para un grafo dirigido, se distingue entre los siguientes tipos de conectividad:^[1]​

En análisis de redes sociales, la conectividad de una red social es un concepto importante,^[1]​ dado que está relacionado con el concepto de cohesión social, estudiado en áreas de las ciencias sociales como la sociología o la psicología. La noción de conectividad se relaciona con propiedades de los lazos interpersonales. Para redes sociales representadas como grafos ponderados, los conceptos de camino a nivel c y accesibilidad a nivel c se utilizan para estudiar subgrupos cohesivos para relaciones valoradas.^[1]​