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}} imes {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 jin {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}}' imes {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}}' imes {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,jin {mathcal {N}}(K_{n})}$ esta conectado por un enlace en ${displaystyle {mathcal {E}}(K_{n})}$. Un clique ${displaystyle Csubseteq 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 iin {mathcal {N}}_{1}}$ y ${displaystyle jin {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 imes n}$ tal que

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

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