Conectividad (teoría de grafos)

Pese a ser un grafo conexo, la conectividad de este grafo no dirigido depende de vértices o aristas de corte, que si se retiran, desconectarían al grafo en componentes.

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]​

Conectividad de vértices y de aristas

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 k\leq \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 l\leq \lambda (G)}$, el grafo se dice que es ${\displaystyle l}$-linealmente conexo.[1]​

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

• débilmente conectado, si están unidos por un semicamino (es decir, un camino que no considera la dirección de las aristas);
• unilateralmente conectado, si están unidos por un camino que va desde uno hasta el otro;
• fuertemente conectado, si están unidos por al menos dos caminos, uno que va desde uno hasta el otro, y viceversa;
• recursivamente conectado, si están fuertemente conectados y el camino desde uno hasta el otro usa los mismos vértices y aristas que los del camino inverso.

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

Conectividad de vértices en grafos ponderados

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]​

Conectividad de grafos

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]​

• débilmente conexo, si todos los pares de vértices están débilmente conectados;
• unilateralmente conexo, si todos los pares de vértices están unilateralmente conectados;
• fuertemente conexo, si todos los pares de vértices están fuertemente conectados;
• recursivamente conexo, si todos los pares de vértices están recursivamente conectados.

Aplicaciones

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]​

Véase también

• Grafo conexo
• Componente (teoría de grafos)
• Cohesión social

Referencias

1. Wasserman y Faust, 2013, «Grafos y matrices» (por Dawn Iacobucci), pp. 121-188.
2. Harary, 1969, p. 43.
3. Peay, E. R. (1980). «Connectedness in a general model for valued networks». Social Networks 2. pp. 385-410. doi:10.1016/0378-8733(80)90005-2.  Falta la |url= (ayuda)
4. Doreian, P. (1969). «A note on the detection of cliques in valued graphs». Sociometry 32. pp. 237-242. doi:10.2307/2786266.  Falta la |url= (ayuda)
5. Doreian, P. (1974). «On the connectivity of social networks». Journal of Mathematical Society 3. pp. 245-258. doi:10.1080/0022250X.1974.9989837.  Falta la |url= (ayuda)

Bibliografía

• Harary, F. (1969). Graph theory. Reading, MA: Addison-Wesley. 
• Wasserman, Stanley; Faust, Katherine (2013) [1994]. Análisis de redes sociales: Métodos y aplicaciones. Madrid: Centro de Investigaciones Sociológicas. ISBN 978-84-7476-631-8. OCLC 871814053. 

• Datos: Q72897900