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.

Definición matemática de red

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\))$.

Conceptos básicos en redes

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}$.

Definición de subred

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))'}$.

k-Clique o k- red completa

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}$.

Redes bipartitas

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.

Matriz de adyacencia

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.