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 R = ( N , E ) {\displaystyle R=({\mathcal {N}},{\mathcal {E}})} se define por un conjunto N = N ( R ) {\displaystyle {\mathcal {N}}={\mathcal {N}}(R)} de elementos llamados nodos o vértices y otro conjunto, E = E ( R ) ⊂ N × N {\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 { i , j } {\displaystyle \{i,j\}} de nodos. Si consideramos los enlaces como pares ordenados, diremos que R {\displaystyle R} es una red dirigida o grafo dirigido. Si cada enlace { i , j } {\displaystyle \{i,j\}} tiene asignado un valor numérico w i j {\displaystyle w_{ij}} , diremos que la red es ponderada y el valor w i j {\displaystyle w_{ij}} será llamado peso o ponderación del enlace { i , j } {\displaystyle \{i,j\}} .

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

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

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

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

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

A i j = { 1  si  { i , j } ∈ E ( R ) 0  en caso contrario. {\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.