Red compleja

En el contexto de la ciencia de redes, una red compleja se refiere a una red (modelada como grafo) que posee ciertas propiedades estadísticas y topológicas no triviales que no ocurren en redes simples; p.e., distribuciones de grado que siguen leyes de potencia, estructuras jerárquicas, estructuras comunitarias, longitud entre cualesquiera dos entes del sistema corto, o alta cohesividad local (medida a través del coeficiente de agrupamiento). Ejemplo de redes con tales características en la naturaleza son las redes sociales, las redes neuronales, las redes de tráfico aéreo y las redes tróficas, entre muchas otras.

Red de co-aparición de los personajes de la novela Les Miserables de Victor Hugo

Definición matemática de red

Una red o grafo $R=(𝒩,ℰ)$ se define por un conjunto $𝒩=𝒩(R)$ de elementos llamados nodos o vértices y otro conjunto, $ℰ=ℰ(R)\subset 𝒩\times 𝒩$ de elementos denominados enlaces o aristas. Cada enlace corresponde a un par no-ordenado $\{i,j\}$ de nodos. Si consideramos los enlaces como pares ordenados, diremos que $R$ es una red dirigida o grafo dirigido. Si cada enlace $\{i,j\}$ tiene asignado un valor numérico $w_{ij}$, diremos que la red es ponderada y el valor $w_{ij}$ será llamado peso o ponderación del enlace $\{i,j\}$.

Conceptos básicos en redes

Dos nodos $i,j$ de una red se dicen adyacentes si estos están conectados por un enlace. Se dirá que un enlace es incidente en un nodo $i$ si dicho enlace es de la forma $\{i,j\}$ para algún $j$ en $𝒩(R)$. El vecindario de $i$, generalmente denotado por $V(i)$, se define como el conjunto de los $j\in 𝒩(R)$ tales que $\{i,j\}\in ℰ(R)$. El conjunto $V^{+}(i)=V(i)\cup \{i\}$ será llamado vecindario inclusivo de $i$.

Definición de subred

Si ${𝒩}^{\prime }\subseteq 𝒩$ y ${ℰ}^{\prime }\subseteq {𝒩}^{\prime }\times {𝒩}^{\prime }$ tal que ${ℰ}^{\prime }\subseteq ℰ$, se dice que el par $R^{\prime }=({𝒩}^{\prime },{ℰ}^{\prime })$ es una subred (o subgrafo) de $R=(𝒩,ℰ)$. Si ${ℰ}^{\prime }=({𝒩}^{\prime }\times {𝒩}^{\prime })\cap ℰ$ diremos que $R^{\prime }$ es la sub-red inducida por ${𝒩}^{\prime }$.

k-Clique o k- red completa

Un $k-${clique} (o $k-${red completa}), denotada por $K_n$, es una red en la que todo par de nodos $i,j\in 𝒩(K_n)$ esta conectado por un enlace en $ℰ(K_n)$. Un clique $C\subseteq R$ se dice maximal si no puede agregarse otro nodo a $R$ sin que este deje de ser un clique en $R$.

Redes bipartitas

Red Bipartita. Los colores rojo y azul simbolizan las dos clases nodales. Obsérvese que no hay enlaces entre nodos de un mismo color.

Básicamente, en este tipo de redes el conjunto de nodos $𝒩$ puede escribirse como la unión disjunta de dos conjuntos ${𝒩}_1$ y ${𝒩}_2$ de manera que en la red no hay enlaces de la forma $\{i,j\}\in ℰ$ con $i\in {𝒩}_1$ y $j\in {𝒩}_2$. En la figura puede verse un ejemplo de este tipo de redes.

Matriz de adyacencia

La matriz de adyacencia $A$ de una red $R$ es una matriz de $n\times n$ tal que

$A_{ij}=\{\begin{array}{cc}1& \text{ si }\{i,j\}\in ℰ(R)\\ 0& \text{ en caso contrario.}\end{array}$

Esta matriz nos permite representar de manera algebraica la estructura de red.