Tema 2: Red Compleja como ejemplo de

sistema complejo

February 19, 2020

1 Introducción
Los grafos son objetos matemáticos constituidos por un conjunto de nodos
(llamados vértices) conectados mediante uniones (aristas) formando una estructura
más o menos compleja. La teoría de grafos es una rama de las matemáticas que
comenzó a desarrollarse en el siglo XVIII. Fue el gran genio Leonhard Euler
(1707-1783) (ver figura 1) quien primero resolvió un problema combinatorio
haciendo uso de las propiedades estructurales de los grafos. En particular
Leonhard Euler en 1735 resolvió el problema de los Siete Puentes de Königsberg
(actual Kaliningrado, capital del Oblast de Kaliningrado)
En esa época la ciudad de Königsberg, Prusia, tenía 7 puertos conectando
las orillas del río Pregel con dos grandes islas. El problema de los siete puentes
de Königsberg es decidir si es posible seguir un camino que cruce cada puente
sólo una vez y volver al punto de origen del camino.
La respuesta es que no es posible. No existe tal ciclo Euleriano. Euler
demostró que tal camino no existe mapeando el problema en un problema
definido en un grafo (ver figura 2)1 , comenzando la rama de las matemáticas
que se conoce como Teoría de Grafos. De esta forma esta teoría tiene una
antigüedad de 300 años. Sin embargo en este curso vamos a estudiar el nuevo
campo de las redes complejas, que en su lugar sólo lleva desarrollándose unas
pocas décadas. Más concretamente, el campo de las redes complejas aparece
en la última década del siglo pasado con dos artículos seminales, el de Watts
& Strogatz sobre redes pequeño mundo 2 y el de Barabasi & Albert sobre
1 Euler determinó que si tal camino existiera los puntos intermedios del mismo estarán

conectados a un número par de líneas (la entrante y la saliente). Entonces sólo el punto inicial
y el final podrían estar conectados con un número impar de líneas. Pero además se tiene que
cumplir que el punto inicial debe ser igual al final, por lo que tendrán también un número par
de líneas. Conclusión en dicho camino posible no hay ningún punto conectado con un número
impar de líneas. Si vemos el grafo de los puentes de Königsberg, los 4 nodos poseen un número
impar de líneas incidentes por lo que es imposible definir un camino con las características
buscadas.
2 Watts, Duncan J.; Strogatz, Steven H. (June 1998). "Collective dynamics of ’small-world’

networks". Nature. 393 (6684): 440-442.

1
Figure 1: Retrato de L. Euler (1707-1783), considerado el padre fundador de la
teoría de grafos

Figure 2: El problema de los 7 puentes de Königsberg y su representación usando

un grafo.

2
Figure 3: Las redes complejas representan sistemas cuya complejidad está
comprendida entre estructuras regulares y aleatorias.

la aparición de redes complejas invariantes de escala 3 , en los cuales

se propone un nuevo paradigma para el estudio de las redes complejas. La
idea fundamental detrás de estos trabajos es que ciertos sistemas complejos,
como los que hemos introducido en el tema anterior, por ejemplo, Internet,
infraestructuras complejas como las redes de carreteras o vuelos comerciales,
redes sociales, redes de interacción de proteínas dentro de las células, redes
tróficas, el propio cerebro, etc. todas ellas tienen una estructura en forma
de red subyacente que describe el complejo conjunto de interacciones entre las
unidades elementales que constituyen estos sistemas.
Una red compleja difiere de un grafo puesto que describe también las interacciones
presentes de un sistema complejo concreto, mientras que un grafo en general
no tiene por qué estar asociado a un sistema complejo. En los dos trabajos
anteriormente citados se muestra que a pesar de la gran cantidad y diversidad
de sistemas complejos que se pueden describir mediante redes complejas, hay
algunas propiedades en estas redes que son universales: es decir, son comunes a
una gran variedad de sistema complejos, algunas de las cuales ya hemos descrito
en el tema anterior. Este hecho sugiere que las propiedades de organización
características de los sistemas complejos auto-organizados que emergen, por
ejemplo, debido a la evolución biológica (como en las redes metabólicas celulares
o en el cerebro) o como producto de una organización no centralizada de la
actividad humana (como en la red de Internet o en las redes sociales) presentan
muchas más similitudes que las esperadas. Estas propiedades de los sistemas
complejos son las responsables de su robustez y eficacia.
Como ya hemos dicho las redes complejas se pueden extraer de muchos
sistemas complejos. Las encontramos en la sociedad (redes sociales en Internet,
redes familiares, redes de amigos, etc) y también en los ecosistemas y en las
interrelaciones tróficas dentro de ellos, no solo incluyendo interacciones de tipo
3 Albert-LászlóBarabási & Réka Albert (octubre de 1999). "Emergence of scaling in
random networks". Science 286: 509-512.

3
depredador-presa o de parasitismo sino también relaciones de simbiosis (mutualistas)
cuya ultimo finalidad es incrementar el beneficio mutuo de las especies (nodos)
que intervienen (por ejemplo un alga y un hongo formando un liquen o una abeja
y una flor que favorece el sustento de la abeja y la polinización de la flor). Las
redes complejas se encuentran también en el conjunto de complejas reacciones
entre proteínas que organizan la actividad y metabolismo celular y en la propia
red del cerebro que condiciona los procesos mentales como memoria, recuerdos,
procesamiento de información espacio-temporal y la propia conciencia. Algunos
ejemplos están resumidos en la tabla 1.

Red compleja Nodos Aristas/uniones

Red de actores Actores actuar en la misma película
Red de colaboraciones Científicos Coautores en una publicación
Redes de citas bibliográficas Artículos científicos Citación
La red de Facebook Personas Amistad en facebook
Redes metabólicas Metabolitos Aparecer en la misma reacción
Redes de interacción de proteínas Proteínas Interacción física
Redes de transcripción genética Genes Regulación
Red cerebral Neuronas Conexiones sinápticas
Internet Routers Líneas físicas
WWW Páginas Web Direcciones URL
Redes de Aeropuertos Aeropuertos Vuelos entre aeropuertos
Redes eléctricas Centrales eléctricas Conexiones eléctricas

Table 1: Ejemplos de redes complejas

2 Teoría de grafos
Como hemos expuesto anteriormente, existen multitud de sistemas naturales
cuyo comportamiento emergente es el resultado de la interacción de un gran
número de constituyentes que interaccionan entre sí mediante influencias diversas,
de forma que su estructura se puede definir en términos de una complicada red
de nodos y uniones entre ellos donde cada constituyente viene definido por
una variable de estado asociada al nodo y donde el estado de las uniones
define la influencia o interacción entre nodos. Esta intrincada red tiene a
priori una estructura compleja, de cuyas propiedades puede inferirse cierto
comportamiento emergente en el sistema.
Históricamente el estudio de las redes complejas ha sido abarcado cierta rama
de las matemáticas discretas denominada teoría de grafos. Una red compleja
se puede representar formalmente por un grafo. Vamos a definir a continuación
este concepto:
1. Un grafo no dirigido (dirigido) G = (N , L) está constituido por dos
conjuntos N = {n1 , . . . , nN } cuyos elementos son los nodos, vértices
o puntos del grafo y L = {l1 , . . . , lL } cuyos elementos son las uniones,

4
 n8
l11
n7
l8

n6

l9
l10

n5
n4

l7
l6
l4

n3

l2
n1 l53
l1
n2

Figure 4: Ejemplo de grafo con 8 nodos y 11 aristas.

aristas o líneas del grafo. Por lo tanto un grafo tiene N nodos y L

aristas y se denota como G(N, L) o simplemente (N , L).
2. Cada vértice o nodo ni viene determinado por su orden i en el conjunto
N.

3. Las aristas vienen definidas por los órdenes de los nodos que unen, es decir,
la unión entre los vértices ni y nj se denota por lk = (i, j) = (ni , nj ) = lij .
En este caso, si hay una unión o arista entre dos nodos, los nodos se llaman
vecinos o adyacentes.

4. Una arista de la forma lk = (i, i) es decir conecta el nodo i consigo mismo se

denomina un lazo, auto-unión o auto-conexión (tadpole). Pueden
aparecer tanto en redes dirigidas como no dirigidas (ver más abajo)
5. Dos aristas que unen dos mismos vértices se llaman paralelas (en el grafo
de la figura 4 serían la l1 y l2 )

6. Aristas que tienen en común un vértice se llaman aristas adyacentes.

5
 n2 n2 n2 n2
5
n1 n1 n1 n1 1
6
n3 n3 n3 n3
3
n4 n4 n4 n4
5
1
n5 n5 n5 n5

Figure 5: De izquierda a derecha: grafo no dirigido (también es un grafo simple),

grafo dirigido, multigrafo, grafo pesado.

2.1 Tipos de Grafos

1. Grafo no-dirigido: aquel en el que el orden de los índices en las uniones
es el mismo: lij = lji .
2. Grafo dirigido: se tiene que el orden de los índices en las uniones es
importante de forma que lij 6= lji .
3. Multigrafos: son grafos que tienen auto-uniones o lazos, por ejemplo lii ,
o múltiples uniones entre los mismos dos nodos. Los grafos no dirigidos
que no tienen lazos ni aristas paralelas se llaman grafos simples.
4. Grafos pesados: Son grafos en los que a cada arista se le asigna un peso
o valor numérico que mide la intensidad de la unión. En caso contrario
la red o grafo se llama no pesado. Si todos los valores son del mismo
signo (positivo o negativo) se dice que la red es “unsigned” y si los pesos
de las aristas tienen asociados diferentes signos entonces el grafo se llama
“signed”.
5. Grafo vacío: grafo sin aristas, sólo con nodos
6. Grafo nulo: el que no tiene vértices (y por lo tanto no tiene aristas)
7. Para un grafo no dirigido G(N, L), el número posible de uniones L está
comprendido entre 0 y N (N − 1)/2.
8. Un grafo se dice diluido o escaso si L  N 2 y denso si L ∼ O(N 2 ).
 
N
9. Un N -grafo completo es aquel G(N, L) tal que L = = N (N −
2
1)/2, y se denota por LN . En un grafo completo se tiene que cada par de
nodos está conectado por una sola arista. Un grafo L3 se llama triángulo.
Un grafo completo es un grafo regular con todos sus vértices de grado
N − 1. La única forma de hacer que un grafo completo se torne disco-nexo
a través de la eliminación de vértices, sería eliminándolos todos.

6
 n1 m1

n2 m2

n3 m3

n4 m4

n5 m5

Figure 6: Grafo bipartito no dirigido.

Ejercicio: dibujar Li i = 0, . . . , 8

10. Definimos un subgrafo G0 = (N 0 , L0 ) de un grafo G = (N , L) cuando

N 0 ⊆ N y L0 ⊆ L. Si G0 contiene todas las aristas que unen dos puntos
en N 0 se dice que G0 es un subgrafo inducido por N 0 y se denota como
G0 = G[N 0 ]. Un subgrafo muy importante es el subgrafo de los vecinos
de un nodo dado i y denotado por Gi que se define como el subgrafo
inducido por Ni , es decir el conjunto de los vecinos del nodo i, y se denota
como Gi = G[Ni ]. Un subgrafo G0 (N 0 , L0 ) que es completo se denomina
“clique” (pandilla, panda, camarilla, grupete).
11. Grafos bipartitos: Un grafo bipartito GB = (N , M, L) es un grafo
constituido por dos conjuntos de vértices disjuntos N = {n1 , . . . , nN }, M =
{m1 , . . . , mM } y un conjunto de aristas L tal que cada arista une un nodo
de N con un nodo de M. A los nodos de M se les suele asociar el nombre
de grupos ya que este tipo de redes aparecen mucho en sociología.
En un grafo bipartito se pueden definir a su vez dos grafos proyectados,
el grafo proyección de nodos GN = (N , LN ) y el grafo proyección
de grupos GM = (M, LM ). GN = (N , LN ) tiene como nodos los el
conjunto N y se dice que dos nodos en ese grafo están unidos por una
arista si los dos están unidos al menos a mismo grupo (nodo de M) en
la red bipartita de partida. Por su parte el grafo GM = (M, LM ) tiene
como nodos los grupos de M y se construye de tal forma que existe una
arista entre dos grupos si al menos están unidos a un mismo nodo de N .
12. Arboles. En teoría de grafos un árbol es un grafo no dirigido en el que
cualquier par de nodos está conectado exactamente por una sola unión.
Un conjunto disjunto de árboles es un bosque. Un árbol en el que un
nodo está conectado con todos los demás se llama una red estrella.

7
 Figure 7: Árbol, bosque y estrella.

2.2 Representación gráfica de grafos

Los grafos se representan gráficamente mediante redes donde lo nodos se representan
por puntos y las uniones mediante líneas que conectan puntos adyacentes. Para
caracterizar a dichas redes se usan dos tipos de representaciones, la lista de
aristas y la matriz de adyacencia. Ambas caracterizaciones van a depender del
tipo de grafo que estemos estudiando

2.2.1 Lista de aristas y matriz de adyacencia en un grafo simple

1. Lista de aristas: En el caso de un grafo simple la lista de aristas es una
lista de L pares de nodos (nj , ni ) , o sus etiquetas (j, i) indicando que el
nodo j está unido al i por una arista. Para un grafo simple la lista de
aristas no admite redundancias, es decir si existe el par (j, i), el par (i, j)
no está incluido en la misma. En el grafo simple de la figura 5 la lista de
aristas es
Lista de aristas
(1, 2)
(2, 4)
(2, 3)
(3, 4)
(3, 5)
(4, 5)

2. Matriz de adyacencia: La matriz de adyacencia A de un grafo simple de

N nodos es una matriz cuadrada N × N cuyos elementos son:

1 si el nodo j está unido al i por una arista
Aij =
0 cualquier otra situación

8
 En el grafo simple de la figura 5 la matriz de adyacencia es:
 
0 1 0 0 0
 1 0 1 1 0 
 
A=  0 1 0 1 1 

 0 1 1 0 1 
0 0 1 1 0

Se tiene que la matriz es simétrica (por ser el grafo no dirigido) y los

elementos de la diagonal son cero (por no haber lazos o auto-conexiones).
3. Matriz de incidencia: Para el caso de una red no-dirigida se pueden
definir dos tipos de matrices de incidencia: las no orientadas y las orientadas.
Las matrices de incidencia no orientadas (llamadas simplemente matrices
de incidencia) es una matriz B N × L donde N es el número de vértices
y L el número de uniones o aristas l = (i, j) y tal que

1 si la unión l contiene al vértice i
Bil =
0 cualquier otra situación

2.2.2 Lista de aristas y matriz de adyacencia de un grafo dirigido

1. Lista de aristas: En este caso es una lista formada por L pares de nodos
(o etiquetas de nodos) ordenados (nj , ni ) = (j, i) que indica que el nodo
j apunta al nodo i en la arista dirigida. L indica, por tanto el número de
aristas dirigidas en la red. En el grafo dirigido de la figura 5 la lista de
aristas dirigidas es:
Lista de aristas
(1, 2)
(2, 4)
(2, 3)
(4, 3)
(3, 5)
(5, 4)

2. Matriz de adyacencia: La matriz de adyacencia A se define para un grafo

dirigido como la matriz cuadrada N × N con elementos:

1 si el nodo j apunta al nodo i
Aij =
0 cualquier otra situación

En el ejemplo de grafo dirigido de la figura 5 se tiene

 
0 0 0 0 0
 1 0 0 0 0 
 
A=  0 1 0 1 0  
 0 1 0 0 1 
0 0 1 0 0

9
 Nota: En algunos libros se define como matriz de adyacencia de una grafo
dirigido a la AT . Se tiene que la matriz de adyacencia es asimétrica (por
ser el grafo dirigido) y los elementos de la diagonal son cero (por no haber
lazos o auto-conexiones).
Ejercicio: Calcular la lista de aristas y la matriz de adyacencia
para el multigrafo representado en la figura 5
3. Matrix de incidencia para un grafo o red dirigida: la matriz de incidencia
es una matriz B N × L que como antes representan el número de vértices
y aristas de la red, respectivamente, tal que

 −1 si la arista l sale del vértice i
Bil = 1 si la arista l apunta al vértice i
0 cualquier otra situación


Podemos definir una red de incidencia orientada en una red no-dirigida

de la misma forma is establecemos una orientacion en la red, por ejemplo,
introduciendo un ordenamiento de los índices y denotando las uniones de
acuerdo a esa ordenación, es decir si denotamos cualquier arista en la red
no-dirigida de la forma l = (i, j) con i < j entonces:

 −1 si k = i
Bkl = 1 si k = j
0 cualquier otra situación


2.2.3 Redes pesadas

1. Lista de aristas: Es una lista de L tripletas (i, j, wij ) cada una de ellas
indicando que entre el nodo j e i hay una unión o arista con un peso o
valor wij . Como antes L es el número total de aristas en la red o grafo.
2. Matriz de adyacencia de una red pesada. La matriz de adyacencia A se
define para un grafo pesado como la matriz cuadrada N ×N con elementos:

(a) Red no dirigida


wij si el nodo j está conectado con el i mediante una arista de peso wij
Aij =
0 cualquier otra situación

(b) Red dirigida


wij si el nodo j apunta al nodo i con una unión de peso wij
Aij =
0 cualquier otra situación

Ejercicio: Calcular la lista de aristas y la matriz de adyacencia

del grafo pesado que aparece en la figura 5

10
2.2.4 Matriz de incidencia de un grafo bipartito
Un grafo bipartito GB (N, M, L) viene descrito por una matriz de incidencia
B definida como una matriz N × M con elementos

1 si el nodo i de N está unido por una arista al nodo j de M
Bij =
0 cualquier otra situación

Ejercicio: Calcular la matriz de incidencia del grafo bipartito

mostrado en el figura 6. Cual sería la matriz de incidencia si no
existiera en dicho grafo el nodo m5 ?
Ejercicio: Dibujar el grafo proyección de nodos del grafo bipartito
de la figura 6y demostrar que el grafo proyección de nodos viene
descrito por una matriz de adyacencia P tal que

P = BBT

Ejercicio: dibujar el grafo proyección de grupos del grafo bipartito

de la figura 6 y demostrar que el grafo proyección de grupos viene
descrito por una matriz de adyacencia P̃ tal que

P̃ = BT B

2.3 Algunos conceptos previos en redes complejas

Las propiedades estructurales más fundamentales de una red compleja son su
número de nodos N y su número de uniones L. En la mayoría de las ocasiones
estos números son grandes por lo que el análisis de las redes complejas necesita
el uso de técnicas computacionales y el uso del ordenador.
1. Número total de aristas en una red compleja se puede calcular directamente
a partir de la matriz de adyacencia:
N N N
1 XX X
L= Aij + Aii red no dirigida con autoconexiones
2 i=1 j=1 i=1
N N
1 XX
L= Aij red no dirigida sin autoconexiones
2 i=1 j=1
N X
X N
L= Aij red dirigida
i=1 j=1

2. Grado de un nodo:
En una red no dirigida se define el grado de un nodo i como el número
total de aristas incidentes en dicho nodo y se denota por ki . En una red
dirigida se distingue entre grado entrante (in-degree) de un nodo i como
el número total de nodos que apuntan a dicho nodo y se representa por
kiin , y grado saliente (out degree) de un nodo i como el número total de

11
 nodos a los que apunta el nodo i y se denota por kiout . En el caso de redes
no pesadas el grado de un nodo se puede calcular directamente a partir
de la matriz de adyacencia:
N
X N
X
ki = Aij = Aji red no dirigida
j=1 j=1
XN
kiin = Aij red dirigida
j=1
XN
kiout = Aji red dirigida
j=1

En un grafo simple no dirigido ki ∈ [0, N − 1], y en un red dirigida kiin ∈

[0, N − 1] y kiout ∈ [0, N − 1].
3. Secuencia de grados:
En una red no dirigida es la secuencia ordenada de los grados de todos los
nodos de la red {ki } = {k1 , . . . , kN }.Esta definición se puede generalizar
para un grado dirigido a las secuencias de grados entrantes{kiin } = {k1in , . . . , kN
in
}
out out out
y a la secuencia de grados salientes {ki } = {k1 , . . . , kN }.
4. Grado medio:
Dada la secuencia de grados de un grafo no dirigido se define el grado
medio hki en la forma:
N N N N
1 X 1 XX 1 XX
hki = ki = Aij = Aji
N i N i=1 j=1 N i=1 j=1

Se tiene trivialmente que para una red simple L = 21 hkiN.

El grado máximo en una red simple no dirigida se define como K = max ki .
i
Para redes dirigidas trivialmente podemos definir el grado entrante promedio
hk in iy el grado saliente promedio hk out i:
N N N N
1 X in 1 XX 1 XX 1 X out
hk in i = ki = Aij = Aji = k = hk out i
N i N i=1 j=1 N i=1 j=1 N i i

es decir son iguales y trivialmente se tiene L = hk in iN = hk out iN . Además

se pueden definir el grado máximo saliente y entrante en la forma usual

K in = max kiin
i
K out = max kiout
i

12
5. Distribución de probabilidad de grados de un grafo:
El grado de un nodo es una propiedad local de la red pero considerando
la secuencia de grados podemos determinar algunas propiedades globales
de la red. La organización y estructura global de una red inducida por su
secuencia de grados está caracterizada por la distribución de probabilidad
de grados de la red P (k).
Para un grafo no dirigido se define P (k) como la fracción de nodos de
grado k y representa la probabilidad que un nodo elegido al azar en la red
tenga un grado k.
Para un grafo dirigido se definen respectivamente y de forma análoga
P in (k) y P out (k) como la fracción de nodos de grado entrante k y la
fracción de nodos de grado saliente k, que me definen las distribuciones
de probabilidad de grados entrantes y salientes. Esto es P in (k) y P out (k)
representan las probabilidades de que al elegir al azar un nodo en la red
tenga un grado entrante k o, respectivamente, un grado saliente k. Vamos
a formalizar esto que acabamos de definir
(a) Grafo no dirigido: definimos N (k) como el número total de nodos en
la red con conectividad k,es decir
N
X
N (k) = δ(k, ki )
i=1

donde δ(k, ki ) indica la delta de Kronecker, entonces se tiene

N
N (k) 1 X
P (k) = = δ(k, ki )
N N i=1

y se tiene que por definición es definida positiva y que

K N K N
X 1 XX 1 X
P (k) = δ(k, ki ) = 1 = 1,
N i=1 N i=1
k=0 k=0

es decir está normalizada por lo que es una verdadera probabilidad.

Ejercicio: Calcular la distribución de probabilidad de grados
del grafo no dirigido de la figura 5 y ver que está normalizada
(b) Grafo dirigido: denotamos por N in (k) y N out (k) respectivamente el
número total de nodos en la red con grado entrante k y con grado
saliente k :
N
X
N in (k) = δ(k, kiin )
i=1
XN
N out (k) = δ(k, kiout )
i=1

13
 entonces P in (k) y P out (k) se definen como:

N in (k)
P in (k) =
N
N out (k)
P out (k) =
N
de donde se tiene que son definidas positivas y normalizadas a la
unidad, es decir:
in
K
X
P in (k) = 1
k=0
out
K
X
P out (k) = 1
k=0

Ejercicio: Calcular la distribución de probabilidad de grados

del grafo dirigido y del multigrafo que aparecen en la figura
5.
La forma de la P (k) de una red compleja tiene gran influencia sobre
su robustez ante defectos aleatorios o ataques dirigidos, y puede
determinar el comportamiento de procesos dinámicos definidos en
la red. Las propiedades estadísticas de P (k) pueden cambiar las
propiedades locales de las red que caracterizan como por ejemplo su
número de subgrafos (ciclos y “cliques”).
6. Matriz Laplaciana de un grafo: Dado un grafo simple G(N, L) su matriz
Laplaciana es una matriz cuadrada N × N definida como:

L=D−A

donde D = ki I es la matriz de grados coin I la matriz identidad, y A es

la matriz de adyacencia. Puesto que G(N, L) es un grafo simple se tiene
que A solo contiene 1s o 0s y sus elementos de la diagonal principal son
0s. Se tiene

 ki si i = j
Lij = −1 si i 6= j pero son adyacentes
0 cualquier otra situación


7. Camino en un grafo. Las redes complejas pueden usarse para buscar

y navegar a través de los sistemas complejos que representan y en general
para transmitir información. El ejemplo más típico por ejemplo es la red
de páginas web de Internet. Cuando exploramos la “web” para buscar
información seguimos un camino a través de la misma, cuando volamos de
un aeropuerto a otro seguimos un camino en la red de aeropuertos, cuando
vemos que dos de nuestros amigos son amigos entre ellos descubrimos
esencialmente un camino en nuestra red social.

14
 De manera formal definimos un camino en un grafo como una secuencia
de nodos tal que dos nodos consecutivos en la secuencia están conectados
por una arista. Un camino dirigido en una red dirigida es un camino
con las aristas dirigidas desde cada nodo al siguiente en la secuencia.
Cada camino tiene su longitud definida como el número de aristas que
se pasan al seguirlo incluyendo posibles repeticiones en caminos que se
intersectan asimismo. Los caminos que partiendo de un nodo vuelven al
final a él mismo se llaman caminos cíclicos o ciclos, mientras que los
que empiezan y acaban en nodos distintos se llama caminos acíclicos o
aciclos. Los caminos acíclicos que visitan los nodos del camino solo una
vez se llaman caminos acíclicos auto-evitados. Los caminos cíclicos
que visitan los nodos del camino solo una vez, salvo el nodo primero,
también se llaman caminos cíclicos auto-evitados.
El número de caminos (caminos dirigidos en una red dirigida) de longitud
n que unen un nodo j y un nodo i en una red, que denotamos como Nijn
se puede determinar en función de la matriz de adyacencia en la forma

Nijn = [An ]ij

es decir viene dado por el elemento (i,j) de la matriz An . La demostración

es sencilla para n = 1, 2 y se puede generalizar fácilmente para cualquier
n. Entonces el número de caminos cíclicos de longitud n que une un nodo
i consigo mismo en la red viene dado por

Niin = [An ]ii .

El número total de caminos cíclicos de longitud n en una red con matriz

de adyacencia A es:
XN
Niin = TrAn .
i=1

Ejercicio: En el grafo no dirigido de la figura 5 calcular el

número total de caminos cíclicos de longitud n = 3 que empiezan
en el nodo i = 1, 2, 3, 4, 5.
Un ciclo Euleriano es un camino cíclico que pasa por cada arista de la
red exactamente una vez. Una red no dirigida posee un ciclo Euleriano si
y solo si todos sus nodos tienen un número par de aristas y cada par de
nodos con aristas pueden ser conectados al menos con una arista.
Un ciclo Hamiltoniano es un camino cíclico que visita cada nodo de una
red exactamente una vez.
8. Distancia, Longitud promedio de caminos (Average path length)
y diámetro de una red. El concepto de distancia en redes complejas
no depende del espacio en un espacio que la contiene, sino solo en la
longitud más corta de los caminos conectando los nodos. Por ejemplo en

15
redes de aeropuertos ciudades con vuelos directos están a una distancia
más corta que ciudades que se alcanzan a través ce otras intermedias,
aunque pueden estar físicamente más cercanas que las anteriores. Muchas
redes complejas están caracterizadas pequeñas distancias entre nodos, por
ejemplo cada dos personas en el mundo están separadas por unos pocos
saludos de manos a través de otras personas. Vamos a cuantificar todos
esto aspectos con las definiciones que siguen:
Definimos el camino más corto entre dos nodos i y j en una red como el
camino (camino dirigido en el caso de una red dirigida) de mínima longitud
(medida en número de aristas que hay en el camino para llegar de un nodo
al otro). Definimos la distancia más pequeña entre uno nodo i y j y
la denotamos como d(ni , nj ) = d(i, j) como la longitud del camino más
corto entre dichos nodos.
Definimos la longitud promedio de caminos o distancia promedio
como el promedio de las distancias más pequeñas entre dos nodos cualesquiera
de la red (estamos suponiendo que existen un camino conectando cualquiera
dos nodos de la red):

N N
1 X X
`= d(ni , nj )
N (N − 1) i=1
j=1
j 6= i

El diámetro D de una red conectada se define como el máximo de la

distancias más cortas entre cualquiera dos nodos de la red es decir:

D = max d(ni , nj )
i,j6=i

Se tiene de forma trivial que ` ≤ D.

Consideremos el caso particular de una red regular describiendo un espacio
euclídeo de dimensión 1 y 2. En dimensión 1 se tiene que D = N − 1 y
en√dimensión dos, donde tenemos N = l × l se tiene que D = 2(l − 1) =
2( N − 1) ≈ 2N 1/2 que para dimensión d se puede generalizar a

D ≈ N 1/d

es decir el número medio de vértices que tenemos que visitar para llegar
a cualquier otro vértice de la red crece con el tamaño (N ) de la red. Sin
embargo en muchas redes reales a pesar de tener tamaños muy grandes
existe un relativamente corta longitud de camino entre cualesquiera dos
nodos, cualidad que caracteriza la propiedad de pequeño mundo que
implica tener un diámetro D ∼ O(ln N ) es decir que

D
lim = cte.
N →∞ ln N

16
 La propiedad de pequeño mundo en redes complejas suele estar asociada
con la existencia de un alto grado de agrupamiento de nodos (clustering)
en la red. Por esta razón Watts y Strogatz definieron las redes tipo
pequeño mundo como aquellas que tienen ` pequeño (como veremos las
redes aleatorias) y C grande (coeficiente de agrupamiento grande como en
las redes regulares).
9. Una red puede ser conectada (conteniendo un solo componente) o desconectada
(conteniendo diferentes componentes).
10. Un lazo no dirigido es un tipo especial de subgrafo de un grafo no
dirigido tal que cada nodo del mismo tiene grado 2 y cada nodo se puede
alcanzar desde cualquier otro nodo del lazo. Un lazo dirigido es aquel
subgrafo de un grafo dirigido tal que cada nodo del lazo tiene un grado
saliente 1 y un grado entrante 1, y puede ser alcanzado por todos los otros
nodos del lazo. En un lazo el número de nodos es igual al número de
aristas y a este número n lo llamamos longitud del lazo. Para un grafo no
dirigido se tiene que el número de lazos de longitud n = 3 es:
1
L3 = TrA3
6

y el número de lazos dirigidos de longitud n = 3 en un grafo dirigido es

1
L3 = TrA3
3

11. Coeficiente de agrupamiento (clustering coeficient). Es una medida

del grado en el que los nodos de una red tienen a agruparse entre ellos.
Dado un grafo G(N, L) no dirigido se define el coeficiente de agrupamiento
de un nodo i de dicho grafo y se denota como Ci al cociente:

número de pares (l, m) de nodos vecinos de i conectados por aristas

Ci =
número total de pares que puedrían existir de nodos vecinos de i

Dado que el número de vecinos de un nodo i es ki el denominador en la

expresión anterior es simplemente ki (ki − 1)/2. En el caso de un grafo
dirigido se tiene la definición:
número de pares (l, m) de nodos vecinos de i conectados por aristas dirigidas
Ci =
número total de pares dirigidos que podrían existir de nodos vecinos de i

En este caso el denominador es ki (ki − 1).

A Ci se le llama también coeficiente de agrupamiento local. Una definición
alternativa para un grafo no dirigido es la siguiente:
número de triángulos que contienen el nodo i
Ci =
número de tripletes que contienen al nodo i incidente a las dos aristas del triplete

17
 Figure 8: Calculo del coeficiente de agrupamiento

donde un triplete es un grafo con 3 nodos y dos aristas. Se puede ver

fácilmente que las dos definiciones coinciden. Por otra parte se define el
coeficiente de clustering de la red simplemente como:
N
1 X
C= Ci
N i=1

y la transitividad del grafo o coeficiente de agrupamiento global como:

3 × número de triángulos en G
T =
número de tripletes de nodos en G

y por lo tanto se tiene 0 ≤ T ≤ 1.

12. Matriz Laplaciana de un grafo L, llamada también Laplaciano del
grafo, Laplaciano discreto, matriz admitancia o matriz de Kirchhoff, es
una matriz que al igual que la matriz adyacente sirve para representar el
grafo. Para un grafo simple no dirigido G(N, L) se define como la matriz
L = D − A donde D es la matriz de grados de nodos cuyos elementos son
Dji = kj δji y donde Aes la matriz adyacente del grafo no dirigido. Se
tiene trivialmente que L es simétrica con elementos de la diagonal principal
igual a los grados de los nodos, es decir

kj si j = i

Lji = −1 si i 6= j y nj es adyacete a ni

0 en cualquiere otro caso.


18
3 Redes regulares y redes aleatorias
De forma intuitiva, una red totalmente conectada tiene la menor longitud promedio
de caminos (` = 1) y el mayor coeficiente de agrupamiento (C = 1). Aunque este
tipo de redes tienen las propiedades de pequeño mundo y alto agrupamiento de
muchas redes reales presenta un alto número de aristas, a saber N (N −1)/2 para
una red no dirigida, mientras que en la mayoría de redes reales tienen un número
de aristas que es O(N ). Las redes complejas están ubicadas como veremos entre
la redes regulares y las redes totalmente aleatorias, por lo que vamos a comenzar
la descripción tanto de redes regulares como de redes aleatorias.

3.1 Redes regulares

Se define una red regular como aquella en la que todos los nodos tienen el mismo
grado, es decir tienen la misma cantidad de aristas incidentes y se denota como
red o grafo k−regular donde k es el grado de todos los nodos. Ejemplos de
grafos k regulares se muestran en la figura 9.
Trivialmente se tiene que un grafo completo Kn es un grafo n−1 regular. Las
redes regulares aparecen en muchos sistemas en la naturales como, por ejemplo,
en la formación de estructuras cristalinas y obedecen como ya hemos indicado
a un principio de regularidad. Las redes regulares están caracterizadas por un
coeficiente de agrupamiento C muy alto (cercano a 1) y una longitud de camino
promedio ` también grande sobre todo para k  N . De hecho ` ∼ N/k.

Figure 9: Ejemplos de grafos regulares

Ejercicio: Demostrar que para una red regular en forma de anillo

donde cada nodo tiene grado k = 2m el coeficiente de agrupamiento
es C = 3(m − 1)/2(2m − 1)

19
3.2 Redes aleatorias: red de Erdös-Rényi
Una red aleatoria es aquella en que el grado de cada nodo es una variable
aleatoria ki ∈ [0, N ]. El estudio sistemático de las redes aleatorias fue iniciado
en 1959 por dos matemáticos Erdös y Rényi (ER) con el propósito original
de estudiar mediante métodos probabilísticos las propiedades de los grafos en
función de un incremento aleatorio del número de conexiones en el grafo. Hicieron
un gran avance en la teoría matemática clásica de grafos que revolucionaría
la forma en que se pueden modelar estos problemas describiendo una red con
topología compleja por medio de un grafo aleatorio, estableciendo los fundamentos
de la teoría de redes aleatorias. Aunque la intuición indica claramente que
muchas redes complejas de la vida real no son ni totalmente regulares ni completamente
aleatorias, el modelo ER fue el único enfoque sensato y riguroso que dominó el
pensamiento de los científicos acerca de las redes complejas durante la segunda
mitad del siglo XX.
El término grafo aleatorio se refiere a la naturaleza aleatoria de la localización
de aristas entre diferentes nodos del grafo ER. En su primer artículo, Erdös
y Rényi propusieron un modelo para generar grafos aleatorios con N nodos
y L aristas, que en lo que sigue denotaremos como red aleatoria de Erdös
y Rényi (ER) o grafo GER (N, L). La forma de construirlo es la siguiente:
Comenzamos con N nodos desconectados y empezamos conectando parejas
de nodos seleccionados al azar mediante aristas, impidiendo la posibilidad de
múltiples aristas entre los mismos nodos, hasta que el número total de aristas
alcanza el valor L. De esta forma el grafo resultante es uno solo de los muchos
que se pueden generar con N nodos y L aristas. Es decir sería un elemento del
conjuntos estadístico de todas las posibles combinaciones de L aristas. Para
una descripción completa del modelo ER necesitaríamos el conjunto entero
estadístico de todas las posibles realizaciones, esto es, en la representación
matricial, del conjunto de matrices de adyacencia.
Una forma alternativa de construir una red ER es conectar cada par de nodos
en la red con probabilidad 0 < p < 1. Este procedimiento define un conjunto
de diferente de grafos con diferentes número de aristas, que denotamos por
GER (N, p). En este conjunto aparecen grafos con L aristas con una probabilidad
pL (1 − p)N (N −1)/2−L . Los dos modelos coinciden en el límite de N  1. Notad
que el límite N → ∞ se toma para mean degree hki fijo, que se corresponde
aPfijar 2L/N Pen el primer modelo y p(N − 1) en el segundo, puesto que hki =
j [A ij ] = j p = p(N − 1), donde [Aij ] es el promedio de los elementos de la
matriz de adyacencia. En este caso se tiene trivialmente hLi = pN (N −1)/2,que
permite ver la equivalencia entre las dos descripciones. El segundo modelo es
más útil para hacer cálculos analíticos.
Las propiedades estructurales de las redes ER varían en función de p mostrando
un cambio muy dramático a pc = 1/N correspondiente a un valor crítico del
grado promedio hkic = 1. Erdös y Rényi demostraron que:
• si p < pc entonces con probabilidad cercana a uno, cuando N → ∞, el
grafo no tiene componentes de tamaño mayor que O(ln N ) y las componentes
no tienen más de un ciclo.

20
 • Si p = pc entonces el componente mas grande del grafo es O(N 2/3 )
• Si p > pc entonces el grafo tiene un componente que es O(N ) y tiene un
número O(N ) de ciclos y los otros componentes son O(ln N ) y no tienen
más de un ciclo.

El cambio que ocurre a pc tiene las características de una transición de fase

de segundo orden. En particular si consideramos como parámetro de orden
el tamaño de la componente de la red más grande (componente gigante)
la transición cae en la misma clase de universalidad de la transición de fase
de percolación. Es decir la percolación se puede entender que tiene una red
compleja subyacente que es de tipo ER.
La probabilidad de que un nodo i tenga un grado k = ki (ki aristas) es la
distribución de probabilidad binomial.
k k N −1−k
P (k = ki ) = CN −1 p (1 − p)

donde pk es la probabilidad de que existan k aristas conectadas al nodo y

(1 − p)N −1−k es la probabilidad de que falten N − 1 − k aristas conectadas al
k
correspondiente nodo. El factor CN −1 es el número de formas diferentes que
tenemos de seleccionar los nodos finales de las k aristas. Puesto que todos los
nodos en un grafo aleatorio son estadística-mente equivalentes, todos tienen la
misma distribución binomial por lo que la probabilidad para cualquier nodo de
la red escogido al azar de tener una determinado grado ki viene dada por

P (ki ) = P (k:i = k).

Para N 1 y hki fijo, esta distribución de probabilidad se puede aproximar

muy bien por la distribución de Poisson:

hkik
P (k) = e−hki ,
k!
por lo que también la red ER se llama red aleatoria Poissoniana. En la figura
10 se muestra la forma de la distribución caracterizando una red ER, y muestra
un pico que está centrado entorno a hki. Debido a esta característica se habla
de una distribución de grados homogénea.

Propiedades estructurales de las redes ER:

• La longitud promedio de caminos es ` ∼ ln N/ lnhki
• Diámetro D ∼ ln N/ lnhki

• Coeficiente de agrupamiento Ci = p = hki N , es decir el coeficiente de

agrupamiento es cero en el límite termodinámico.
Ejercicio: Demostrar estos valores.

21
Figure 10: Diferencias entre la distribución Binomial y la de Poisson y como la
distribución Binomial se aproxima a la de Poisson para N  hki.

Las redes aleatorias se pueden generalizar a redes que no tengan una distribución
de tipo Poissoniana dando lugar a lo que se conoce como modelo configuracional
de red aleatoria y que se construye de la siguiente forma:
Especificamos una distribución de probabilidad arbitraria P (k) de forma
que este número representa la fracción de vértices en la red que tienen una
conectividad k. Especificamos una secuencia de grados {k1 , . . . , kN } tomada de
esta distribución. A continuación empezamos a establecer aristas entre nodos
de la red de forma que se satisfaga al final esta secuencia de grados con lo que
generamos una posible topología de red que viene descrita por P (k). Con este
procedimiento se puede generar cualquier configuración o topología de red que
viene descrita por P (k). El modelo configuracional se define entonces como
el conjunto de todas estas posibles topologías que se pueden generar con este
procedimiento y que tienen en común P (k), todas teniendo el mismo peso en
el conjunto. En el límite N  1 se puede demostrar que P (k) coincide con la
distribución de grados de cada configuración. El modelo configuracional falla sin
embargo en incorporar la estructura de bucles que se encuentra en la mayoría
de las redes reales.
En el modelo configuracional se puede demostrar las siguientes propiedades
estructurales:
ln(N/z1 )
• ` = ln(z2 /z1 )
+ 1 donde zm es el número de vecinos a una distancia m de
una nodo dado 4 . En ER se tiene que z1 = hki y z2 = hki2
h 2 i2
• C = hki
N
hk i−hki
hki 2

4 Ver por ejemplo M.E.J. Newman, S.H. Strogatz, D.J. Watts, Phys. Rev. E 64 (2001)

26118.

22
4 Redes pequeño mundo
En 1998, con el fin de describir la transición de una red regular en una red
aleatoria, Watts y Strogatz (WS) introdujeron el concepto de red pequeño
mundo. Debe notarse que el fenómeno de mundo pequeño es de hecho muy
común, y nada alejado de nuestras experiencias diarias. A menudo, poco después
de conocer a un extraño, uno se sorprende al descubrir que tenemos un amigo
común con él, de modo que es habitual la expresión: "¡Qué pequeño es el
mundo!". Un experimento que se realizó hace más de 40 años dio lugar al
llamado "principio de los seis grados de separación", sugerido por el
psicólogo social Milgram a finales de 1960, y que establece que entre cualesquiera
dos personas del mundo hay una media de 6 conexiones de amistad, independientemente
de lo lejanas que estén dichas personas. Aunque este punto sigue siendo controvertido,
el patrón del mundo pequeño ha demostrado estar presente en muchas redes
reales. Una característica importante y común al modelo de redes aleatorias
(ER) y al de mundo pequeño (WS) es que la función de distribución de grados
tiene un máximo en el valor medio del grado y decae exponencial-mente, lo
que quiere decir que casi todos los nodos de la red tienen el mismo número de
conexiones. Por ello, es común denominar a estos tipos de redes de manera
conjunta como redes exponenciales o redes homogéneas.
El modelo de WS fue propuesto como una forma de extender los modelos
de redes aleatorias para explicar dos observaciones que se habían descrito en las
redes reales: a) la propiedad de pequeño mundo que se caracteriza en las redes
reales por tener un longitud media de caminos entre dos nodos que va como
ln N lo que las diferencia de las redes regulares donde va como N , y b) el alto
coeficiente de agrupamiento observado en las redes reales y que las redes ER no
podían explicar (ver figura 11).
Para conseguir una red aleatoria con estas propiedades de las redes complejas
Watts y Strogatz proponen un modelo de red que se obtiene mediante un proceso
de re-cableado con una cierta probabilidad p. La forma de construir la red es la
siguiente:
• Partimos de una red regular de N nodos donde cada nodo tiene k = 2m
vecinos. Los nodos están dispuestos en un anillo circular tal que de cada
nodos salen m aristas conectando los primeros m vecinos a la derechas del
nodo y otras m aristas conectando los primeros m vecinos a la izquierda
del nodo. En la figura 12 se observa en el panel de arriba la red regular de
partida en (a) donde se está tomando m = 2, es decir cada nodo tiene 4
vecinos. El número total de aristas en la red inicial es por tanto K = mN.
• Entonces para cada nodo del anillo, re-cableamos con probabilidad p a un
nodo al azar en el anillo cada una de las aristas con sus vecinos situados
en el sentido de las agujas del reloj. Por lo tanto las aristas con los
vecinos permanecen con probabilidad (1 − p) y se quitan con probabilidad
p. Entonces si p = 0 el re-cableado no se produce y la red sigue siendo la de
partida, es decir regular (caso a en la figura 12). Si p = 1 todas las aristas
son cambiadas y puestas al azar sobre nuevos nodos en la red de forma que

23
Figure 11: Comparación entre el coeficiente de agrupamiento de redes reales
(círculos de colores) con diferente número de nodos con el correspondiente
coeficiente de agrupamiento para una red ER (línea verde)

la red resultante es aleatoria (caso c en la figura). Para valores intermedios

de p tendríamos una red que tiene una alto grado de agrupamiento y
la propiedad de pequeño mundo debido a los atajos de largo alcance
(shortcuts) producidos por el re-cableado no nulos presente para ese valor
de p (caso b en la figura) que conectan nodos distantes. Notad que en
esta tipo de red el número de total aristas permanece contante durante el
re-cableado.
El efecto del re-cableado sobre la longitud promedio de caminos es altamente
no-lineal pues puede disminuir considerablemente ` con muy pocos shortcuts.
Sin embargo el re-cableado de unas pocas aristas de una vecindad de nodos
muy agrupados solo tiene un efecto lineal sobre ese grado de agrupamiento.
Por esto puede haber una región de valores de p para la que el grado de
agrupamiento apenas se ve afectado mientras que ` pasa abruptamente de
valores altos a pequeños (ver el panel de abajo de la figura 12)
Las propiedades estructurales de las redes WS son las siguientes:
• La longitud promedio de caminos `(N, p):

24
Figure 12: Generación de redes tipo pequeño mundo y su comparación con redes
regulares y redes aleatorias.

para p = 0 se tiene
N (N + 2m − 2) N
`(N, 0) = ∼
4m(N − 1) 4m

para p = 1 se tiene
ln N
`(N, 1) =
ln(2m − 1)
Existen una transición de fase continua entre estos dos valores, es decir un
pc que separa estos dos comportamientos con una longitud característica
que diverge como p−1
• Coeficiente de agrupamiento:
3(m − 1)
C(p) = (1 − p)3
2(2m − 1)

25
Figure 13: Red pequeño mundo en cultivos neuronales (Santos Sierra et al.
Plos One 2014). Panel (A) coeficiente de clusteris y longitud promedio de
caminos mostrando comportamiento pequeño mundo. Panel (B), comparación
de dichos parámetros con respecto a redes aleatorias y redes regulares. Panel
(C), comparación de la eficiencia local y global comparada con la de redes
aleatorias, medidas, respectivamente, como el inverso de la distancia más corta
entre dos nodosPEij = 1/d(i, j) y el promedio de dichas eficiencias locales
E(G) = N (N1−1) i6=j Eij .

• Distribución de probabilidad de grados:

min(k−m,m) 
(pm)k−m−i −pm

X m
P (k) = (1 − p)i pm−i e
i (k − m − i)!
i=0

5
para k ≥ m y 0 para k < m
Ejercicio: Construir una red WS con re-cableado y otra en la que
no hay re-cableado sino establecimiento con probabilidad p de atajos
y comparar las dos redes resultantes y sus propiedades estructurales,
P (k), ` y C.

5 Redes invariantes de escala

Los grafos que hemos estudiado hasta al momento caracterizan redes complejas
que tienen la propiedad de ser homogéneas. La homogeneidad en la estructura
de interacciones de estas redes significa que todos los nodos son topológicamente
5 la derivación para estas cantidades se puede encontrar en A. Barrat, M. Weigt, Eur. Phys.

J. B 13 (2000) 547.

26
Figure 14: Probabilidad acumulada de la red de servidores en Internet donde
las aristas son conexiones físicas entre servidores.

equivalentes como en el caso de redes regulares y en el caso de redes aleatorias.

En este último caso, cada uno de los N (N − 1)/2 posibles aristas aparece con
la misma probabilidad de forma que la distribución de grados es binomial y
en N → ∞ Poissoniana que implica tener distribuciones centradas entorno a
un valor medio bien definido y con una varianza bien definida. Sin embargo
cuando se hace un estudio sistemático de los datos disponibles sobre redes reales
se encuentra sorprendente-mente que la mayoría de las distribuciones de grado
son en forma de leyes de potencias P (k) = Ak −γ con exponentes variando en
el rango 2 < γ < 3. Uno tiene sencillamente para estas distribuciones que el
promedio está bien definido y que la varianza σ 2 = hk 2 i − hki2 está dominada
por el segundo momento de la distribución que diverge con el grado máximo
kmax en la forma Z kmax
hk 2 i = k 2 P (k) ∼ kmax
3−γ
kmin

Este tipo de redes se denominan redes invariantes de escala pues muestran

un aspecto similar en cualquier escala de observación. De hecho como ya hemos
visto en el tema anterior la forma funcional en forma de ley de potencias es la
única que queda invariante cuando cambiamos la escala, es decir son las únicas
que son solución a la ecuación:

f (αx) = βf (x)

27
 En general denotaremos como redes invariantes de escala la que vienen
descritas por una distribución de grados que tipo ley de potencias pero
esto no significa necesariamente que dichas redes sean también invariantes de
escala respecto de otros propiedades estructurales de la red. Además, la forma
funcional en forma de ley de potencia implica que todos los grados entre kmin y
kmax pueden aparecer en la red, es decir tienen una probabilidad no nula en el
límite termodinámico de aparecer a diferencia de las redes homogéneas donde
casi todos los nodos tienen el mismo grado y la probabilidad de que aparezca
un nodo con un grado muy diferente de la media decae rápidamente a cero.
Este hecho implica una alta heterogeneidad en los posibles grados en la red
y la existencia de unos pocos nodos con una alto grado, los llamados “hubs”
conectados con un alto número de nodos con grados pequeños. En redes de
tamaño finito pueden existir cortes (“cut-offs”) en la distribución de grados.
También para grandes grados las distribuciones muestran una alta dispersión a
conectividades altas, es decir en las colas, debido a la pobre estadística. En estos
P∞ es más0 útil estudiar la probabilidad acumulada definida como Pcum (k) =
caso
k0 =k P (k ) (ver por ejemplo figura 14). En este caso se puede obtener el
exponente de P (k) como γ = 1 + γcum .

5.1 Modelos estáticos de redes invariantes de escala

Son modelos construidos del modelo configuracional, es decir, se generan redes
de forma que la distribución de grados tenga la forma de ley de potencias
eligiendo N valores aleatorios para las ki distribuidos según P (k), y después
conectando al azar sobre todos los nodos de forma que se satisfagan las ki .
Estos modelos así construidos se denominan modelos estáticos invariantes de
escala.
Uno de los modelos estáticos estudiados es el que se construye asumiendo que
el número de nodos que tienen un determinado grado k es N (k) = eα k −γ que
tiene dos parámetros libres 6 . En este modelo, dados α y γ, quedan totalmente
determinados el número de nodos y aristas en la red. Se puede demostrar que
las redes que se generan con este modelo tienen una componente gigante si
γ < γc ≈ 3.478.
Estos modelos estáticos configuracionales tienen las siguientes propiedades
estructurales:
• Longitud promedio de caminos: ` ∼ ln N (para γ > 3) y órdenes menores
para 2 < γ < 3, y el diámetro D ∼ ln N
• Coeficiente de agrupamiento: C ∼ N (3γ−7)/(γ−1)
6 ver por ejemplo, W. Aiello, F. Chung, L. Lu, Proceedings of the 32nd
AnnualACMSymposium on Theory of Computing, Association of Computing Machinery, 63
New York, 2000, p. 171.

28
5.2 Modelos dinámicos de redes invariantes de escala
Estos modelos surgen cuando se trata de modelar la dinámica de crecimiento
de ciertas redes reales. En estos casos las propiedades estructurales de la red
resultante dependen de la propia dinámica evolutiva de la red que la ha llevado
a ese estado final. El modelo más conocido de este tipo es el modelo de Barabási
y Albert (BA) también conocido como de añadido preferencial de nodos 7 .
El modelo BA está basado en como la WWW se ha ido formando y se
basa fundamentalmente en dos aspectos: crecimiento y añadido preferencial
de nodos. La idea principal es que los lugares de la WWW con grados altos
adquieren nuevas aristas a nuevos nodos con más probabilidad que los lugares
con grados más bajos. De forma más precisa un grafo GBA (N, L) se construye
de la siguiente forma. Se parte de m0 nodos aislados y a cada instante de tiempo
t = 1, 2 . . . , N − m0 se añade un nuevo nodo j a la red con m ≤ m0 aristas. La
probabilidad de que una arista conecte el nodo nuevo j con un nodo i de los m0
existentes es proporcional al grado del nodo i, es decir ki :
ki
pj→i = P .
l kl

Dado que cada nodo que se añade tiene m aristas entonces en cada instante
de tiempo t tenemos N = m0 + t nodos y L = mt aristas, de forma que la
conectividad promedio es hki = 2m para tiempos muy grandes.
El modelo BA has sido resuelto en aproximación de campo medio obteniendo
una ecuación de tipo rate y una ecuación maestra. En el límite de t → ∞ se
puede obtener como solución una distribución P (k) ∼ k −γ con γ = 3 (ver figura
15)
Podemos determinar una ecuación dinámica para la evolución de las conectividades
en el modelo BA en la siguiente forma: supongamos que añadimos un nuevo
nodo j a la red que se puede conectar con los existentes a través de m aristas
entonces se tiene que
dki
= mpj→i
dt
pues el nodo i tiene m posibilidades
P de poder conectarse con el j con
probabilidad pj→i . Por otra parte l kl = 2mt − m pues la suma se extiende a
número total de nodos menos el j, que tiene una conectividad kj = m. Usando
este resultado tenemos
dki ki
=
dt 2t − 1
cuya solución para t largos es
 1/2
t
ki (t) = m
ti
7 Albert-László Barabási & Réka Albert (1999). "Emergence of scaling in random
networks". Science 286: 509-512.

29
Figure 15: Generación de una topología de red BA con m = 3 y N = 100000
nodos. Los puntos morados corresponden al histograma que se obtiene con
intervalos lineales, y los verdes al que se obtiene con intervalos tomados en
escala log.

donde ti es el tiempo en el que se añadió el nodo i. Consecuencia de este

resultado es que los nodos que se añaden antes a la red son los que acaban
teniendo una conectividad mayor (hubs).
Las propiedades estructurales de la red de BA son las siguientes:
• La longitud promedio de caminos: ` ∼ ln N/ ln (lnN )
• Coeficiente de agrupamiento: C ∼ N −3/4 .
El modelo de BA has sido ampliamente estudiado y numerosas versiones de
redes evolutivas han sido propuestas utilizando una dinámica similar, incluyendo
algunas generalizaciones del mismo.
La red BA pierde el carácter de invariante de escala y de heterogeneidad
para m grande, donde empieza a hacerse más homogénea.

6 Correlaciones grado-grado
La distribución de grados P (k) caracteriza completamente las propiedades estadísticas
de redes complejas descorrelacionadas, que son aquellas en las que el grado de
un nodo es independiente del grado del resto de los nodos en la red. Sin embargo
hay multitud de redes reales en las que la probabilidad de que un nodo de grado
k esté conectado a otro nodo de grado k 0 depende de k. En estos caso es necesario

30
Figure 16: Panel superior: dependencia de las conectividades ki con el tiempo.
Panel inferior: evolución de la P (k) con el tiempo en el modelo de BA

31
introducir una probabilidad condicional P (k 0 |k) definida como la probabilidad
de que un nodo de grado k y un nodo de grado k 0 estén conectados por una
arista. Esta probabilidad satisface la normalización
X
P (k 0 |k) = 1
k0
y la condición de balance detallado
kP (k 0 |k)P (k) = k 0 P (k|k 0 )P (k 0 ).
Para redes descorrelacionadas P (k 0 |k) no depende de k de donde usando la
normalización y la condición anterior obtenemos
P (k 0 |k) = k 0 P (k 0 )/hki.
Aunque las correlaciones grado-grado quedan formalmente caracterizadas
por P (k 0 |k) en la práctica debido al tamaño finito de muchas redes complejas
(que da resultados muy ruidosos para esta probabilidad condicionada) es más
conveniente trabajar para medir correlaciones grado-grado con el grado promedio
de los vecinos próximos de un grado i definido como
N
i 1 X 1 X
knn = kj = Aij kj
ki ki j=1
j∈vec(i)

A partir de aquí podemos calcular el grado promedio de vecinos próximos

que tienen un determinado grado k como
X
knn (k) = k 0 P (k 0 |k).
k0

Si no hay correlaciones se tiene

hk 2 i
knn (k) =
hki
es decir es independiente de k.
En virtud de las correlaciones grado-grado, los grafos se clasifican en asortativos
si knn (k) es una función creciente en k, o disasortativos si knn (k) es
una función decreciente en k.
En definitiva las redes de tipo asortativo tienen correlaciones positivas de
grados en el sentido de que nodos muy conectados tienden a conectarse con nodos
muy conectados y nodos poco conectados con nodos poco conectados, mientras
que en las disasortativas los nodos con mayor grado se conectan con nodos con
grado pequeño. En definitiva el grado de asortatividad se mide mediante la
pendiente de la curva knn (k) (ver figura 17).
Otro parámetro que se utiliza para medir las correlaciones es el llamado
coeficiente de Pearson aplicado a las aristas definido como:
[kl kl0 ] − [kl ]2
r=
[kl2 ] − [kl ]2

32
Figure 17: Generación de redes invariantes de escala con diferentes tipos de
correlaciones grado-grado.

kl y kl0 son
donde P P los grados de los dos nodos conectados por una arista l y
1
[.] = hkiN l (.) = ij Aij es un promedio sobre todas las aristas en la red que
se puede escribir en la forma:

hkihk 2 knn (k)i − hk 2 i2

r=
hkihk 3 i − hk 2 i2

y es tal que para un valor positivo significa que la red es asortativa (como
ocurre en la mayoría de las redes sociales) y un valor negativo implica disasortatividad
(como en las redes biológicas y tecnológicas) como se muestra en la figura 19.

7 Redes jerárquicas.
Muchas redes reales presentan dos propiedades genéricas: invariante de escala
y un elevado coeficiente de agrupamiento para todos los nodos. Estas dos
características pueden aparecer debido a la existencia de una alta jerarquización
en la forma que pequeños grupos de nodos se organizan de una forma jerárquica
en grupos de nodos mayores manteniendo la invariante de escala. Podemos
así definir las redes jerárquicas como aquellas redes complejas que presentan
invariancia de escala a la vez que un coeficiente de agrupamiento muy elevado
para todos los nodos. En estas redes el grado de agrupamiento que caracterizan
los diferentes grupos de nodos sigue una estricta ley de escala que puede ser
usada para detectar jerarquización en redes reales.

33
Figure 18: Panel superior, diferencias entre redes asortativas y disasortativas.
Panel inferior muestras dos ejemplos de redes reales con diferente asortatividad,
por ejemplo en (a) (grupos de amigos en una escuela de EEUU) una red
asortativa y en (b) (red de interacción de proteínas en la levadura de la cerveza
Saccharomyces cerevisae) una red real disasortativa.

Figure 19: Grado de asortatividad y disasortatividad en diferentes redes reales.

34
Figure 20: Comparación entre redes aleatorias, invariantes de escala y redes
jerarquizadas.

35
Propiedades:

1. Tienen una distribución de grados que es una ley de potencias:

P (k) = ck −γ

En una red jerárquica se puede demostrar que

ln M
γ =1+
ln(M − 1)

donde M es el factor que se replica (en el ejemplo mas abajo M = 4)8

(a) Coeficiente de agrupamiento de un nodo de grado k sigue una ley de
escala
C(k) ∼ k −β
A diferencia de otro tipo de redes complejas como las redes aleatorias
y las redes invariantes de escala, el coeficiente de agrupamiento de
nodos con grado k depende del grado no es constante.
(b) Coeficiente de agrupamiento en función de la tamaño de la red N :

C(N ) ∼ cte

de hecho hemos visto que en las redes invariantes de escala va como

C ∼ N −0.75 .
(c) Las redes jerarquizadas tienen una clara estructura fractal y modular
(ver figura 20) .
(d) El exponente β que controla el escalado del coeficiente de agrupamiento
con el grado puede cambiar si se cambian ciertos parámetros que
controlan la estructura de la red (es decir no es un parámetro universal).
Esto se puede ver haciendo una versión estocástica de un modelo
jerárquico como el que se muestra en la figura 20 conectando una
fracción pn de nodos de cada módulo en el paso n de la iteración
mediante unión preferencial para construir la red jerárquica. Las
propiedades estructurales de estas redes jerárquicas aleatorias se muestran
en la figura 21.

Muchas redes reales muestran características de las redes jerárquicas como

claramente muestra la figura 22.
8 Ver Noh, J. (2003). "Exact scaling properties of a hierarchical network model". Physical

Review E. 67 (4)

36
 Figure 21: Propiedades estructurales de redes jerárquicas aleatorias.

Figure 22: Redes reales jerárquicas: (a) red de actores (b) red semántica de
palabras inglesas (c) la red WWW y (d) Internet

37
8 Redes modulares
Muchas redes reales muestran cierta modularidad , en el sentido que puede
subdividirse en grupos de nodos más interconectados entre sí, que constituyen
comunidades o módulos, que a su vez están conectados entre sí con una menor
densidad de aristas (ver figura 23) . Este característica ya la hemos visto en el
caso de las redes jerárquicas que muestran una clara modularidad. El problema
de detectar y caracterizar las estructura modular de una red compleja tiene una
gran interés actual pues permite entender la estructura y función de la red y su
mecanismo de crecimiento. De hecho constituye una de las principales líneas de
investigación en el campo de las redes complejas. Generalmente para determinar
los módulos o comunidades presentes en una red compleja se utiliza un proceso
de optimización que maximiza un determinado parámetro que denotamos por
“modularidad”.
De forma más cuantitativa se puede definir la modularidad de una red
compleja como la fracción de aristas que caen dentro de un grupo de
nodos en una red compleja menos la fracción de aristas que habría en
dicho grupo de nodos si la red fuera aleatoria. El rango de la modularidad
es [−1/2, 1), donde un valor positivo indica que el número de aristas dentro del
grupo de nodos es mucho más grande que el que se esperaría simplemente de
conectar al azar los nodos. Podemos por lo tanto determinar la estructura en
comunidades de una red compleja, explorando divisiones de la red que impliquen
una modularidad positiva. Uno de los métodos tradicionales que se han utilizado
para esto es optimizar la modularidad sobre diferentes particiones de la red
mediante el algoritmo de “recocido simulado” (simulated annealing). Sin
embargo este método requiere un alto coste computacional. Los métodos más
aceptados actualmente son los que re-formulan la modularidad en términos de
las propiedades espectrales de la red en cuestión.
Supongamos una red constituida por N vértices y L aristas. Supongamos
que la red puede dividirse en dos grupos I y II. Denotamos si = 1 si el vértice i
pertenece al grupo I y si = −1 si i pertenece al grupo II. Sea Aij el elemento ij
de la matriz de adyacencia que en principio puede tomar el valor 0 o 1, aunque
también puede tomar otro valor si consideramos la posibilidad de múltiples
aristas entre dos nodos. De esta forma Aij nos da el número de aristas entre
los nodos i y j. Por otra parte el valor esperado de aristas entre los nodos
ki kk ki kj
i y j si la red fuera aleatoria sería [Aij ]RAN D = N hki = 2L . Entonces la
modularidad, que denotamos por la letra Q, se define como la suma de las
diferencias Aij − [Aij ]RAN D sobre todo par de índices (ij) que caen en el mismo
grupo. Dado que la cantidad ηij = 12 (si sj + 1) es 1 si los nodos i y j están en el
mismo grupo y 0 si no lo están entonces se puede poner (la suma es ahora sin
restricciones)
1X
Q= (Aij − [Aij ]RAN D )ηij (1)
L ij

38
Figure 23: Ejemplo de red modular.

39
 que se puede expresar como
1 X
Q= (Aij − [Aij ]RAN D )si sj (2)
2L ij

Ejercicio: Demostrar la expresión anterior.

Particiones en grupos I y II que maximizan Q son buenas candidatos a
diferentes comunidades o módulos en la red.
La expresión (2) se puede generalizar al caso de tener una partición de M
grupos simplemente definiendo Siρ = 1 si el vértice i pertenece al grupo ρ y
Siρ = 0 si no pertenece, en cuyo caso se define
M
X
ηij = Siρ Sjρ
ρ=1

que como antes es 1 si el nodo i y j pertenecen al mismo grupo de la partición

y 0 si no pertenecen al mismo grupo, por lo que la modularidad queda:
1 XX
Q= (Aij − [Aij ]RAN D )Siρ Sjρ .
2L ij ρ

La expresión anterior se puede poner en forma matricial, lo que es útil para

el uso de algoritmos de optimización espectrales, introduciendo las matriz S (de
dimensión N × M ) cuyos elementos de matriz son los Siρ , y la matriz cuadrada
B cuyos elementos de matriz son

Bij = Aij − [Aij ]RAN D , (3)

y que se llama la matriz modularidad . Entonces en forma matricial la

modularidad queda:
1
Q= TrST BS (4)
2L
Ejercicio: Para Predes divididas en solo dos comunidades I y II,
demostrar que la ρ nos da un factor SiI SjI + SiII SjII = 12 (si sj + 1).
Usando este resultado tenemos que para una red dividida en dos comunidades
la modularidad en forma matricial se expresa:
1 T
Q= s Bs (5)
2L
donde s es el vector columna con elementos si . La expresiones de la modularidad
(4) y (5) tienen la forma de un hamiltoniano tipo Ising describiendo un vidrio de
espín, por lo que como hemos dicho antes son útiles los algoritmos de recocido
simulado para maximizar la modularidad.
Vamos a ver en este caso como podemos hacer una análisis espectral de la
modularidad:

40
 Sea uα los auto-vectores de la matriz B, es decir

Buα = λα uα

donde {λα } es el conjunto de auto-valores de la matriz B, que suponemos

ordenados de mayor a menor λ1 ≥ . . . ≥ λN . Sin pérdida de generalidad
podemos poner X
s= aα uα
α

con aα = uTα · s. Entonces la modularidad para dos grupos se puede poner

como
1 X
Q= aα aβ uT α Buβ
2L
α,β

dado que los {uα } constituyen una base orto-normal. Entonces nos queda
1 X 2 1 X T 2
Q= aα λα = (u ·s) λα .
2L α 2L α α

Como tenemos que decidir que nodos pertenecen a cada grupo, esto en la
práctica significa elegir el vector s. Entonces para maximizar Q deberíamos
elegir s tal que sea paralelo al auto-vector asociado al auto-valor más grande,
esto es λ1 , pues de esta forma solo nos queda un término en la suma anterior,
el correspondiente a α = 1. Sin embargo el vector s tiene componentes binarias
por lo que no podemos hacerlo paralelo a u1 . De todas formas, todavía podemos
maximizar Q eligiendo s en la forma si = 1 si u1,i > 0 y si = −1 si u1,i < 0.
Si tenemos más de dos particiones procedemos de la siguiente forma, la idea
es dividir cada una de las dos particiones que resultan del método anterior
en otras dos particiones y así sucesivamente hasta que tengamos el número de
particiones que queremos. Lo que se hace dividir la modularidad de un grupo
g en la suma de la modularidad que queda después de dividirlo en dos más una
cantidad ∆Qg en la forma:

Qg = Qdespués + ∆Qg .

Por definición (ver expresion (3))

1 X
Qg = Bij
L i,j∈g

y de (1) se tiene
1 X
Qdespués = Bij ηij
L i,j∈g

con lo que  
1 X X
∆Qg = Bij si sj − Bij 
2L ij∈g ij∈g

41
 que se puede poner como:
 
1 X X
∆Qg = Bij − δij Bik  si sj
2L ij∈g
k∈g

donde δij es la delta de Kronecker. Definiendo la matriz B(g) cuyos elementos

de matriz son X
(B (g) )ij = Bij − δij Bik
k∈g

finalmente obtenemos:
1 T (g)
∆Qg = s B s
2L
que tiene la forma de la ecuación (5) y por tanto podemos también maximizar
por el mismo método espectral que hemos descrito anteriormente.
El proceso continua hasta el momento en que una nueva división no incremente
la modularidad de la red, es decir el ∆Q que resulte de la nueva división del
grupo sea cero o negativo.

9 Redes multiplex.
Muchas redes reales están interrelacionadas entre ellas y no se pueden analizar
de forma aislada. En este sentido en los últimos años se ha empezado a estudiar
redes de redes reales, lo que se conoce con el nombre de redes multiplex ,
o redes multicapa no solo desde un punto de vista estático sino también
dinámico. Un ejemplo muy fácil de entender es la red de transportes que incluye
por ejemplo la red de aeropuertos, la red de carreteras y la red de metro.
En el caso de la red de aeropuertos se suele modelar como una sola red
donde los nodos son los aeropuertos y las aristas son los vuelos directos entre
aeropuertos. Sin embargo una mejor representación sería considerar una red
multiplex constituida de muchas redes cada una de las cuales correspondería a
una compañía aérea particular, donde cada nodo sería de nuevo los aeropuertos y
cada arista correspondería a los vuelos directos entre aeropuertos realizados por
esa compañía. Puede ocurrir cada una de estas redes tenga el mismo conjunto de
nodos pero diferentes aristas, pues no todas las compañías aéreas tienen vuelos
entre los mismos aeropuertos. El estudio de esta red multiplex tiene mucha
importancia por ejemplo para re-alojar pasajeros que han perdido sus vuelos
y deben ser re-colocados en algún vuelo de otra compañía por el elevado coste
económico que este hecho lleva consigo.
En general las infraestructuras complejas son totalmente interdependientes
de forma que un pequeño fallo en una red puede provocar una cascada de fallos
en todas las redes interdependientes (ver figura 25)
Otro ejemplo claro lo tenemos en la biológica y más concretamente en la
neurociencia, donde en medios neuronales como el cerebro encontramos tanto

42
Figure 24: Red multicapa de transporte en EEUU. Las líneas azules
corresponden a líneas de transporte terrestre (coches, trenes, etc). Las líneas
rojas, naranjas y amarillas corresponden a líneas de transporte aéreo siendo las
rojas las que mayor intensidad llevan.

conexiones o sinapsis de tipo eléctrico (uniones gap) como sinapsis químicas, y la

dinámica asociada a cada una de ellas es totalmente distinta. Por lo tanto tales
medios neuronales pueden ser caracterizados por una red multiplex constituida
por dos subredes, de forma que cada neurona puede jugar un papel diferente en
cada subred.
Podemos definir por tanto las redes multicapa como aquellas que incorporan
diferentes canales de conectividad, y describen a sistemas que están interconectados
con diferentes categorías de conexiones: cada canal es representado por una
subred o capa y un mismo nodo puede tener diferentes tipos de interacciones y
una vecindad diferente en cada capa. Vamos a formalizar el concepto de redes
multiplex o redes multicapa:
• Red multicapa es un par M = (G, E) donde G = {Gα , α = 1, . . . , M }
es una familia de grafos Gα = (Nα , Lα ) (capas de la red multicapa M)
y E = {Eαβ ⊆ Nα × Nβ , α 6= β} es el conjunto de las interconexiones
entre nodos de las diferentes capas. Los elementos de E se llaman capas
cruzadas, los elementos de Lα se llaman conexiones intracapa, y los
elementos de cada capa cruzada Eαβ se llaman conexiones intercapas.
El conjunto de nodos en cada capa lo denotamos por Nα = {nα α
1 , . . . , nNα }
y la matriz de adyacencia de cada capa la denotamos con A[α] cuyos
elementos son
1 si la arista (nα α

α i , nj ) ∈ Lα
Aij =
0 cualquier otra situación

La matriz de adyacencia entre capas correspondiente al conjunto Eαβ de

43
Figure 25: Cascada de fallos originada por una avería en un planta eléctrica
de la red eléctrica de Italia (nodos sobre el mapa) y como afecta a la red de
Internet ( nodos fuera del mapa) eliminando importantes hubs en esa red que a
su vez induce fallos de nuevo en otras plantas eléctricas (Italia 2003).

las interconexiones entre las capas α y β es A[α,β] con elementos de matriz

β

αβ 1 si la arista (nα
i , nj ) ∈ Eαβ
Aij =
0 cualquier otra situación

• Red proyección de M es el grafo proj(M) = (NM , EM ) donde

 
!  
M
[ M
[ [ M
[ 
NM = Nα EM = Lα Eαβ 
 

 
α=1 α=1  α, β = 1 
α 6= β

• Red multiplex: Es una caso particular de red multicapa donde N1 =

N2 = ... = NM = N y donde los únicos elementos de E son el conjunto de
β
aristas Eαβ = {(nα
i , ni ) i ∈ N , α 6= β} como se muestra en la figura 27.

• Redes temporales: El formalismo de redes multicapa también se puede

usar para describir la dinámica temporal de una red compleja. En este caso
se tiene el conjunto de capas es G = {Gt , t = 0, . . . , T } donde Gt = G(t)
y los elementos de E son Eαβ con Eαβ = ∅ si β 6= α + 1 y
\
α+1
Eαα+1 = {(nα i , ni ) i ∈ Nα Nα+1 , }

• Las redes interactuantes: {G1 , . . . , GM }una familia de redes que interaccionan

entre sí se pueden modelar con una red multicapa con M capas {G1 , . . . , GM }
y cuyos elementos Eαβ corresponde con el conjunto de interacciones entre
la capa Gα y la Gβ como se muestra en la figura 28

44
Figure 26: Red multicapa y su grafo proyección

45
Figure 27: Red multiplex.

46
 Figure 28: Redes interactuantes y su descripción en forma de multicapa

9.1 Caracterización de la estructura de las redes multicapa

Podemos extender definiciones que hemos realizado para caracterizar los grafos
al caso de redes multicapas, y que sirven para determinar la importancia o rango
de cada nodo en la red (medidas de centralidad). Así podemos definir:
• Grado de un nodo en una red multicapa, al vector

ki = (ki1 , . . . , kiM )

donde kiα es el grado del nodo i en la capa α, y donde se tiene kiα = j Aα

P
ij .
Para medir también la importancia de un nodo en la red multicapa se
define el solapamiento de los grados de un nodo sobre las diferentes
capas en la forma
XM
Oi = kiα
α=1

el solapamiento total entre capas como

X β
Oα,β = Aαij Aij
i<j

el solapamiento local entre capas como

X
Oiα,β = Aα β
ij Aij
j

• Coeficiente de agrupamiento de un nodo i en una red multicapa M:

PM
2 α=1 |Lα (i)|
CM (i) = PM
α=1 |Nα (i)|(|Nα (i)| − 1)

47
 donde Lα (i) = {(nα α
k , nj ) ∈ Lα ; k, j ∈ Nα (i)} y Nα (i) es el conjunto de
nodos que son vecinos del nodo i en el grafo proj(M) Tde la red multicapa
y que pertencen a la capa α (es decir Nα (i) = N (i) Nα , donde N (i) es
el conjunto de nodos vecinos del nodo i en el grafo proj(M)), y donde |A|
denota el cardinal del conjunto A. El coeficiente de agrupamiento de la
red multicapa se puede definir como el promedio de CM (i).
• Longitud de caminos más corta. Una geodésica entre dos nodos u y
v de una red multicapa es una de las distancias más cortas que unen u y
v. La distancia d(u, v) se define como la longitud de cualquier geodésica
entre u y v.
• La máxima distancia entre dos nodos de M define el diámetro de la red
multicapa y se denota por D(M).
• Se define la longitud de caminos característica como
1 X
L(M) = d(u, v)
N (N − 1)
u, v
u 6= v

• Se define la eficiencia de una red multicapa como

1 X 1
E(M) =
N (N − 1) d(u, v)
u, v
u 6= v

9.2 Correlaciones de grado en un multiplex

Dado el conjunto de nodos de un multiplex que tienen un grado kiα en cada
capa del multiplex, entonces los grados del mismo nodo en cada capa pueden
estar correlacionados. Por ejemplo, un nodo que es un hub en una red de
colaboradores científicos con alta probabilidad será también un hub en una
red de citas científicas. Por lo tanto el grado de la red de colaboraciones
científicas está positivamente correlacionado con el grado de las citas científicas.
Correlaciones negativas también existen cuando los hubs en una capa no lo son
en las otras.
Introducimos la probabilidad de tener en una capa α un grado k α condicionado
a tener en una capa β un grado k β en la forma

P (k α , k β )
P (k α |k β ) = P α β
kα P (k , k )

donde la matriz P (k α , k β ) viene definida por

N (k α , k β )
P (k α , k β ) =
N

48
 donde N (k α , k β ) es el número de nodos que tienen grado k α en la capa α y
grado k β en la capa β.
• Grado promedio en la capa α condicionado a tener un grado en la
capa β X
k̄ α (k β ) = k α P (k α |k β )
kα

• Coeficiente de Pearson:

hkiα kiβ i − hkiα ihkiβ i

rαβ =
σα σβ
p
donde σα = hkiα kiα i − hkiα i2 .

49