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.
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.
para el que el grafo tiene un corte de nodos-
, porque no hay que quitar ningún vértice; si el grafo tiene un punto de corte, entonces
, porque basta quitar un único vértice para que el grafo se vuelva inconexo, y así sucesivamente.
vértices, con lo que se obtiene el grafo trivial.
para el que el grafo tiene un corte de aristas-
[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.
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.
