El análisis de redes es uno de los campos científicos más emocionantes y dinámicos del siglo XXI.
Las redes están en todas partes, desde los metabolitos que alimentan a nuestro cuerpo hasta las redes sociales que dan forma a nuestras vidas
Este módulo ha sido diseñado como introducción a la teoría que subyace a las redes
en donde exploraremos la teoría de grafos como la base de nuestro lenguaje.
Aprenderemos acerca de la estructura topológica de las redes, mirando los diferentes modelos y propiedades de las redes, hablaremos de la red libre de escala
un fenómeno sorprendentemente ubicuo
y de redes biológicas.
Aunque el material de este módulo tiene una naturaleza matemática,
veremos como recordatorio del curso que todos los conceptos utilizados aquí surgen en redes de la vida real.
Además, la notación introducida en este módulo nos permitirá discutir la variedad de redes que veremos a lo largo del curso
de una manera uniforme y consistente.
El concepto matemático esencial utilizado para modelizar redes es el "grafo". Veamos pues, ¿Qué es un grafo?
Mira la imagen. ¿Qué ves?
A través de un conjunto de puntos hay unas líneas que los unen, esto son grafos.
Los grafos son un concepto clave en la matemática discreta y formalmente a los puntos se les llama vértices, o nodos de la red,
y las líneas o uniones entre ellos se llaman aristas.
Por lo tanto el grafo G, definido como un conjunto de vértices,
denotado por V o V(G), y un conjunto de aristas, denotado por E o E(G).
Los grafos son fáciles de dibujar y entender a partir de una imagen, y también son fáciles de procesar por programas de ordenador.
Dos vértices se llaman "adyacentes" o vecinos si están unidos por una arista.
Una arista que une u y v se denota por {u, v} o abreviado uv.
Así un grafo puede describirse con una lista de los vértices y las aristas, como hemos escrito aquí, o con una bonita imagen.
¿Cuál te gusta más?
Una arista es un par. Una arista dirigida o con dirección es un par ordenado.
Se representa como (v1, v2) mientras que una arista no dirigida es un par desordenado sin orientación
y se representa como {v1, v2}.
Más términos.
Una arista de un grafo cuyos n vértices son el mismo vértice se llama "bucle".
Una arista es incidente con un vértice si ese vértice es uno de sus extremos. Veamos pues el grafo G1.
v2 y v3 son adyacentes.
e2 is incidente con v2 y e6 es un bucle.
Los grafos o redes que nos podemos encontrar se pueden dividir en dos grandes clases según el tipo de aristas:
grafos dirigidos y grafos no dirigidos.
Los grafos no dirigidos consisten en un conjunto no vacío de vértices por V, y un conjunto de aristas no dirigidas, E.
Un grafo dirigido es un conjunto de vértices V con un conjunto de aristas dirigidas.
Por ejemplo, G1 es un grafo no dirigido mientras que G2 es un grafo dirigido. En biología,
redes de regulación transcripcional y redes metabólicas habitualmente son grafos dirigidos.
Por ejemplo los nodos de redes de regulación transcripcional
que representan los genes teniendo como aristas las interacciones entre ellos,
sería un caso de grafo dirigido porque si el gen A regula el gen B hay una dirección
asociada a la arista entre dichos nodos, empezando por A y terminando por B.
Mientras que las redes de interacción proteína-proteína
son normalmente modelizadas como grafos no dirigidos, en donde cada nodo representa una proteína y las aristas representan
las interacciones. Más adelante en este módulo y en otros hablaremos más sobre estas redes y sus propiedades.
Es costumbre referirse a algunos grafos especiales básicos con nombres descriptivos.
Revisaremos los más famosos. El primero es el "grafo ciclo". Un grafo ciclo de longitud n es un grafo
de n vértices unidos cíclicamente con n aristas.
El número de vértices ha de ser superior a tres.
El ciclo se denota por Cn donde n es el número de vértices, o de aristas si se prefiere, ya que son iguales.
El siguiente grafo se llama "camino". Un camino de longitud n se ve como una cuerda estirada con nudos a lo largo de ella.
Tiene n+1 vértices como consecuencia de n aristas.
El siguiente grafo es el "grafo completo de n vértices", que como el nombre sugiere
todos los vértices están conectados. El número de nodos debe de ser mayor de uno para poderse llamar grafo completo.
Un "grafo bipartito" es un grafo que tiene dos partes, y las aristas conectan los nodos de un parte con los de la otra.
Un grafo bipartito completo
C(m, n) tiene m+n vértices en dos partes y arisas uniendo todos los pares m,n de las dos partes
Los últimos dos tipos de grafos son las "ruedas" y los "n cubos".
La rueda denotada por Wn (W de "wheel", rueda en inglés) es un grafo formado de conectar un nuevo vértice a todos los vértices del ciclo Cn.
El último tipo de grafo que veremos es el "n cubo" o "hipercubo".
Se conoce como Qn y es un grafo cuyos vértices son la cadena binaria 2^n y dos vértices son adyacentes
si y sólo sí la cadena difiere exactamente en una coordenada.
El grado de un vértice V en un grafo G es el número de aristas de G
que inciden en él. Un grafo es d-regular si todos los vértices tienen el mismo grado d.
Para un grafo dirigido,
podemos refinar nuestra definición y dividirlo en dos: en grado, y fuera de grado.
En grado es el número de aristas para las que v es un vértice terminal, y fuera de grado es el número de aristas para las cuales
v es un vértice inicial.
Si escribes el grado de los vértices de un grafo en una secuencia de números naturales
entonces tenemos la "secuencia de grados" o "puntuación del grafo".
En grafos abstractos, sus vértices normalmente no tienen nombres y por tanto tenemos que ordenar de alguna manera sus secuencias de grados.
El orden en particular no es importante.
Si conoces la secuencia de grados de un grafo, ¿qué puedes decir del número de aristas del grafo?
Se puede demostrar que el número de aristas en un grafo simple no dirigido es el doble de la suma de su secuencia de grado.
El Teorema del Apretón de Manos (handshaking theorem) puede ser usado para si una secuencia puede o no ser un grafo.
¿Por qué la secuencia 1 2 3 4 no puede ser la secuencia de grado de un grafo?
Sí, la suma no es par y por tanto no puede serlo.