Red compleja

En el contexto de la ciencia de redes,^[1]​ 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,^[2]​ las redes neuronales, las redes de tráfico aéreo y las redes tróficas, entre muchas otras.

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

Dos nodos ${\displaystyle 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 ${\displaystyle i}$ si dicho enlace es de la forma ${\displaystyle \{i,j\}}$ para algún ${\displaystyle j}$ en ${\displaystyle {\mathcal {N}}(R)}$. El vecindario de ${\displaystyle i}$, generalmente denotado por ${\displaystyle V(i)}$, se define como el conjunto de los ${\displaystyle j\in {\mathcal {N}}(R)}$ tales que ${\displaystyle \{i,j\}\in {\mathcal {E}}(R)}$. El conjunto ${\displaystyle V^{+}(i)=V(i)\cup \{i\}}$ será llamado vecindario inclusivo de ${\displaystyle i}$.

Si ${\displaystyle {\mathcal {N}}'\subseteq {\mathcal {N}}}$ y ${\displaystyle {\mathcal {E}}'\subseteq {\mathcal {N}}'\times {\mathcal {N}}'}$ tal que ${\displaystyle {\mathcal {E}}'\subseteq {\mathcal {E}}}$, se dice que el par ${\displaystyle R'=({\mathcal {N}}',{\mathcal {E}}')}$ es una subred (o subgrafo) de ${\displaystyle R=({\mathcal {N}},{\mathcal {E}})}$. Si ${\displaystyle {\mathcal {E}}'=({\mathcal {N}}'\times {\mathcal {N}}')\cap {\mathcal {E}}}$ diremos que ${\displaystyle R'}$ es la sub-red inducida por ${\displaystyle {\mathcal {N}}'}$.

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

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

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

${\displaystyle A_{ij}=\left\{{\begin{array}{c l}1&{\text{ si }}\{i,j\}\in {\mathcal {E}}(R)\\0&{\text{ en caso contrario.}}\end{array}}\right.}$

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