¶ “Resumen de conceptos y código. Calificativo de Redes Sociales” ¶

1. ¿Qué son las redes?

Las redes son una forma de representación de información que contiene el mapeo de agentes a analizar (llamados “nodos”, y que puede ser cualquier cosa: personas, papers, celular, neuronas, ciudades, etc) y la vinculación que tienen unos con otros. Nunca entenderemos un sistema complejo a menos que tengamos un mapa y entendamos las redes detrás de ellos.

Las redes se han utilizado en distintas áreas y por tanto tienen distintos nombres para las mismas cosas. por ejemplo:

Nombre disciplina	Nombre de agentes	nombre a la relación
Redes complejas (física, economía, biología)	Nodos	Links
Grafos (Matemática, cs de la computación)	Vértices	Edges
Redes sociales (Sociología, Ciencia política)	Actores	relaciones

1.1 Ejemplo replicable

Para todos los apuntes de este documento, utilizaremos la siguiente red que se ha hecho de manera aleatoria. Cualquier similitud con nombres de personas conocidas es mera coincidencia.

## tidyverse     dplyr    igraph  triangle  poweRlaw 
##      TRUE      TRUE      TRUE      TRUE      TRUE

# Cargar el paquete "igraph"
library(igraph)

# Crear una lista con los nombres de los nodos
nodos <- c("Diego", "Jackie", "Ale", "Francisco", "Eugenio", "Pedro", "Reyne", "Mont", "Carlos", "Daniel")

# Crear una red dirigida aleatoria
set.seed(123) # Para que los resultados sean reproducibles
red_dirigida <- sample_gnp(length(nodos), p = 0.3, directed = TRUE)

# Asignar los nombres de los nodos a la red dirigida
V(red_dirigida)$name <- nodos

# Crear una red no-dirigida aleatoria
set.seed(456) # Para que los resultados sean reproducibles
red_no_dirigida <- sample_gnp(length(nodos), p = 0.3, directed = FALSE)

# Asignar los nombres de los nodos a la red no-dirigida
V(red_no_dirigida)$name <- nodos

Plot de red dirigida:

Plot de red no-dirigida:

1.2 ¿Qué son los grafos?

Son representaciones matemáticas de las redes. Consta de nodos y links o edges, que conectan a los nodos. Los nodos pueden etener estados; los enlaces pueden tener direcciones y pesos.

Si bien grafo y red son tratados habitualmente como sinónimos, hay situlezas, pues el grafo es la representación matemática de una red, y la red se refiere a sistemas reales (Ej: Facebook como red social no es igual al grafo social de Facebook).

Para saber cuántos vértices y edges tengo en una red, uso las funciones “V” y “E”:

V(red_dirigida)
E(red_dirigida)

1.3 Tipos de redes

Las redes podemos clasificarlas por si son dirigidas, no-dirigidas y con peso:

Las primeras son donde las redes tienen una dirección dada, hay un sentido específico de vinculación entre nodos; esto implica que la red es asímétrica. En las redes no dirigidas no hay dirección definida de sentido del vínculo, por lo que son redes simétricas.

La formas de representar matemáticamente las redes son a partir de matrices de adyacencia. Siguiendo el ejemplo de la red de arriba la representamos como:

\[A_{i j}=\left(\begin{array}{cccc} 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{array}\right) \quad A_{i j}=\left(\begin{array}{llll} 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{array}\right)\]

Donde la matriz izquierda representa a la red no-dirigida, con un nodo \(i\) y nodo \(j\). Cada fila es el nodo de partida y cada columna es el nodo hacia donde se proyecta el edge. En el caso de la matriz de la derecha, al ser una red dirigida, lo que se contabiliza es el nodo de entrada. En otras palabras, la fila 1 (que corresponde a nodo 1) tiene sólo ceros pues no tiene edgs de entrada, en cambio la fila 2 (que representa el nodo 2) tiene dos links de entrada que representan la columna 1 (nodo 1) y columna 4 (nodo 4).

El grado máximo de enlaces que puede tener una red de N nodos es:

\[L_{max} = \frac{N}{2}= \frac{B(N-1)}{2} \]

Esto es llamado grafo completo

1.4 Redes bipartitas

Redes que nacen a partir de dos conjuntos mútuamente excluyentes y que las relaciones estén dadas en cómo un conjunto se relaciona con otro (ej: actores y películas, genómas con fenómenos, autores y papers, etc).

2. Métricas básicas para analizar la topografía de las redes

Los índices de centralidad son respuestas a la pregunta ¿Qué caracteriza un nodo importante?. El mismo concepto de “Importancia” va a variar según cada tipo de métrica de centralidad, que veremos a continuación.

2.1 Centralidad de grado

Como señala Mark Newmann, la Centralidad responde a la pregunta sobre cuál es el nodo más importante de la red (2018). Corresponde al número de conexiones promedio en una red dadan (y también podemos obtenerla en cada nodo).

2.1.1 Grado promedio (grafos no-dirigidos)

Se entiende como la suma total de todos los grados de cada nodo dividido por el número total de nodos:

\[ \langle k\rangle \equiv \frac{1}{N} \sum_{i=1}^N k_i \quad\langle k\rangle \equiv \frac{2 L}{N}\]

2.1.2 Grados de entrada promedio (grafos dirigidos)

En los grafos dirigidos podemos analizar la cantidad de nodos de entrada y nodos de salida en una red. En este caso, los grados de entrada se refieren a la cantidad de conexiones que otros nodos otorgan hacia un nodo \(i\).

Los grados promedios de entrada se denotan como la sumatoria de todos los grados de entrada por nodo:

\[\langle k^{in} \rangle \equiv \frac{1}{N} \sum_{i=1}^N K_i^{in}\]

2.1.3 Grados de salida promedio (grafos dirigidos)

\[\langle k^{out} \rangle \equiv \frac{1}{N} \sum_{i=1}^N K_i^{out}\]

El código para obtener los grados son los siguientes:

degree(red_no_dirigida) #todos los grados de la red
degree(red_dirigida, mode="in") # solo grados in
degree(red_dirigida, mode="out") #solo grados out

2.2 Betweeness centrality

El betweeness centrality puede ser entendido como el nodo por donde fluye la información a través de un grafo dado.

Se calcula como:

\[x_i = \sum_{st}\frac{n_{st}^i}{g_{st}}\]

El Betweenness centrality del nodo de una red general es: donde es el número de caminos más cortos de \(s\) hacia \(t\) que pasan a través de \(i\), y número total de caminos más cortos desde \(s\) hacia \(t\), tomando la convención de que \(\frac{n_{st}^i}{g_{st}} = 0\) es el si tanto \(n_{st}^i\) como \(g_{st}\) son cero (Newman, 2018). Esta medición implica que, si de alguna manera sacáramos este nodo, la red se dividiría en más sub-redes. Que es una buena forma de ilustrar la importancia de los nodos con alto Betweenness centrality.

Esta medida no depende sólo del nodo sino de toda la red.

En R se calcula con la función betweeness:

betweenness(red_dirigida, v = V(red_nodos), directed = TRUE) #En este ejemplo sólo usé la red dirigida. puede utilizarse una no dirigida y cambiar a directed = FALSE.

2.3 Closeness centrality

Estar en el flujo de información es importante, pero la cercanía de un nodo frente a otros también es relevante para la comunicación directa de los líderes de opinión. En este caso el Closeness centrality (o centralidad por cercanía) se refiere a cuán rápido puede comunicarse un nodo con otro en la red. Un nodo con alto CC es un diseminador efectivo de opiniones e información (Bamakan et al., 2019) teniendo más influencia que nodos lejanos.

La centralidad de cercanía es la distancia media entre nodos, y de acuerdo a Newmann (2018) es el inverso de \(\ell_i\) . Se calcula se la siguiente forma:

\[C_i=\frac{1}{\ell_i}=\frac{n}{\sum_j d_{i j}}\]

Donde \(\ell_i\) es la sumatoria de todos los caminos más cortos de \(d_{ij}\).

Sin embargo algunos autores creen que es inapropiada porque asume que cada flujo de información pasa a través de los caminos más cortos. Sumado a eso, es muy sensible a la distancia o links perdidos. Para eso se sugiere el de centralidad armónica. (Bamakan et al., 2019)

Para calcularlo en R se usa la función closeness:

closeness(red_dirigida, mode = "in", vids = V(red_nodos)) #En este caso puse mode = "in" porque estaba buscando en una red direccionada en grados de entrada.

2.3 Eigenvector centrality

Esta métrica del nodo nos da la centralidad de un nodo considerando, además, la importancia de los nodos que tienen conexiones hacia él. El Eigenvector centrality es el “amigo de los amigos importantes”.

Su formula es la de la centralidad ed grado proporcional al grado de sus conexiones:

\[x_i = k^{-1} \sum_{Nodos j que \\ son vecinos de i} x_j\]

Esto tiene sentido: Uno puede ser influyente si tiene amigos importantes.

eigen_centrality(red_no_dirigida)$vector

Sin embargo esto tiene una condición: No puede calcularse el Eigenvector centrality en redes dirigidas

2.5 PageRank

Esta métrica de centralidad corrige un problema importante que aparece en el Katz centrality, que es que cuando nodos con alto katz centrality a partir de nodos que tienen muchos edges de salida, ellos también tienen un alto katz centrality. ¿Si una persona entrega vínculos a miles de personas, de verdad tiene un peso relevante ese vínculo? La intuición señala que no y por eso se realiza el PageRank.

El PageRank, es, entonces, una variante de la centralidad de Katz en el cual la centralidad derivada de los vecinos es proporcional a su centralidad dividida por su out-degree (Newman, 2018).

Se calcula como:

\[x_i=\alpha \sum_j A_{i j} \frac{x_j}{k_j^{out}} + \beta\]

Y el código de R es:

page.rank(red_dirigida, directed = TRUE)$vector  #En este caso elegí el ejemplo de la red dirigida, pero si usamos una red no dirigida simplemente ponemos "directed = FALSE"

2.6 Distribución de grado

Como buscamos obtener números que podamos analizar estadísticamente, uno de los elementos que necesitamos para entender la topología es la distribución de los grados en una red.

La notación es:

\[P(k) = \frac{N_k}{N}\] Donde \(P(k)\) es la probabilidad de que un nodo elegido aleatoriamente tenga grado k y \(N_k\) son los nodos con grado k.

El código de R es:

# Obtener la distribución de grado
distr_grado <- degree_distribution(red_no_dirigida)

# Graficar la distribución de grado
plot(distr_grado, main = "Distribución de grado", xlab = "Grado", ylab = "Frecuencia")

Otra forma de ver la distribución de grados es simplemente ploteando los histogramas de manera rápida:

#histogramas de la red
hist(degree(red_no_dirigida), breaks = 200)

inn <- hist(degree(red_dirigida, mode = "in"), breaks = 200)

out <- hist(degree(red_dirigida, mode = "out"), breaks = 200)

Las distribuciones de grado son habitualmente muy concentradas en pocos nodos, y los histogramas tienen una tendencia en “L”. Como son poco informativos por su forma de concentrarse, se pasan a logaritmos para poder observarlos mejor:

El código para hacerlo en R es el siguiente:

d.red <- degree(red_no_dirigida)
# por la rapidez con que decae la distribución es mejor usar log-log
dist.red <- degree_distribution(red_no_dirigida)
d <- 1:max(d.red) - 1 # generamos una secuencia que la usaremos en el gráfico
val <- (dist.red != 0) # creamos un vector lógico de valores con grado !=0
plot(d[val],dist.red[val], 
     log="xy", 
     col="red", 
     ylab="log frecuency", 
     xlab="log degree",
     pch = 19)

En la literatura veremos estos tres tipos de distribuciones de grados en redes:

2.7 Distancia

La distancia entre nodos se entiende como el camino más corto entre estos puntos. Si analizamos el ejemplo de abajo, la distancia entre el nodo 1 y 6 puede ser 1,2,5,7,4,6, pero la ruta más corta es la 1,2,4,6.

Es importante recordar que en el caso de redes dsirigidas, los únicos caminos posibles son los que siguen la dirección de la flecha, y que en nodos que están desconectados la distancia es infinita.

La forma para ver la distancia promedio en R es:

mean_distance(red_no_dirigida)

2.7.1 Diámetro de la red

Es la distancia máxima entre cualquier par de nodos en el grafo.

Para un grafo dirigido, se calcula como:

\[ \langle d \rangle \equiv \frac{1}{2L_{max}} \sum_{i,j \neq i}d_{ij}\]

Considerando que \(L_{max} = n(n -1)\): número total de enlaces.

Y en un grafo no-dirigido \(d_{ij = d_{ji}}\), sólo se cuenta una vez, (es decir: \(i,j >i\)):

\[\langle d \rangle \equiv \frac{1}{L_{max}} \sum_{i,j>i} d_{ij}\]

En otras palabras: el diámetro es la distancia más larga dentro de los caminos cortos.

Su código en R usa la función diameter :

# Calcular el diámetro del grafo
diameter(red_no_dirigida) #podemos agregar también un "directed = T" en caso de que sea una red dirigida

2.8 Componentes

Las redes pueden tener componentes o subconjuntos de nodos completamente conectados entre sí, pero que no tienen conexión con otros subconjuntos. Cuando hay más de un componente se habla de “grafos deconectados”.

Los grafos, cuando tienen componentes, tienen un componente principal que concentra más del 80% de las conexiones y otros componentes pequeños.

El código en R para analizar los componentes es:

#Para contar los componentes
count_components(red_dirigida, mode = c("weak", "strong")) #acá agregamos los dos tipos de modos que existen para grafos dirigidos

#Para encontrar el componente gigante y hacer un grafo

componentes <- clusters(red_dirigida)
componentes
g <- which.max(componentes$csize) # identificamos el gigante

red1 <- induced.subgraph(red_dirigida, which(componentes$membership == g)) # nos quedamos con el componente gigante

En el caso de redes dirigidas, existen grafos fuertemente conectados y débilmente conectados. El primero, se refiere a que un nodo tiene ruta de camino de conexión en los dos sentidos, y el segundo es cuando están conectados sí y sólo sí ignoramos las direcciones de los edges.

2.9 coeficiente de clustering

Responde a la pregunta sobre qué fracción de tus vecinos están conectados entre sí. Esto toma valores entre 0 y 1.

Para grafos dirigidos se calcula como:

\[C_i=\frac{\left|\left\{e_{j k}\right\}\right|}{k_i\left(k_i-1\right)}: v_j, v_k \in N_i, e_{j k} \in E\]

Para grafos no-dirigidos se calcula como

\[C_i=\frac{\left|\left\{e_{j k}\right\}\right|}{k_i\left(k_i-1\right)}: v_j, v_k \in N_i, e_{j k} \in E\]

La única diferencia es que la no-dirigida está multiuplicada por dos, que corresponde a las dos direcciones de los nodos.

En R se utiliza la función transitivity para calcularlo:

#Calcular coeficiente de clustering de la red

coeficiente_clustering <- transitivity(red_no_dirigida, type = "global")
print(coeficiente_clustering)

## [1] 0.5217391

El coeficiente de clustering tiene una teoría detrás importante, que es el de la fuerza de los enlaces débiles de Mark Granovetter. A partir de ella podemos pensar en la predicción de enlaces en base a secciones de los cluster conectados que podrían hacerlo.

Además los enlaces son los responsables de la difusión de ideas nuevas, ya que en los vínculos fuertes es difícil que aprendan cosas nuevas.

Me falta agregar eigenvector centrality, densidad de red, reciprocida con sus respectivo códigos. también los códigod de los vérticoes y nodos.

3. Plotear redes

En general no es muy difícil plotear una red. Utilizando la red no dirigida de muestra, simplemente presionamos plot(red_de_interés y listo:

plot(red_no_dirigida)

Pero se ve feo y podemos ir modificando ciertas cosas. por ejemplo, podemos agregarle los pesos de cada nodo según sus grados:

plot(red_no_dirigida, vertex.label=NA, vertex.size=degree(red_no_dirigida)*7.4)

Si se fijan, cada nodo tendrá tamaño en razón de sus grados y en el código se aplica un multiplicados para escalar el tramaño mismo del nodo, que en este caso es 7.4 pero sobre todo cuando sn redes muy grandes, se debe achicar lo más posible, y puedo eliminar el nombre de los nodos con vertex.label=NA. También podemos cambiar los colores del borde del nodo con vertex.frame.color, el color del link con edge.color y también el tamaño de los vértices con vertex.size.

plot(red_no_dirigida, vertex.label=NA, vertex.size=degree(red_no_dirigida)*7.4, vertex.frame.color="black", edge.color="blue")

4. Inferencia de redes

4.1 Redes aleatorias

¿Podemos capturar en un modelo las propiedades de una red que son random?. Esto es lo que buscó analizar Pául Erdös y Alfred Rènyi. La creación del modelo Erdös-Rènyi señala que “Los grafos aleatorios son grafos de N nodos donde cada par de nodos está conectado con una probabilidad P” (que puede ser cualquier probabilidad).

Entonces primero se parte con la red completamente desconectada y en cada iteraciòn nace una conexión nueva (1 = conectado, 0 = desconectado) con la probabilidad dada. De hecho, en el ejemplo de la red que hemos construído se usó ese principio con una probabilidad de 0.3.

La motivación inicial de ellos era saber cuánto tiempo va a tomar de que todas las personas de la fiesta sepan cuál es el vino caro si sólo se lo digo a una persona.

Nota: En el modelo la probabilidad y la cantidad de nodos están fijas, pero los enlaces son los aleatorios y por tanto serán distintas.

Está dada por la función:

\[P(L)= \left(\begin{array}{c}\left(\begin{array}{c} N \\ 2 \\ \end{array}\right) \\ L \end{array}\right) p^L(1-p)^{\frac{N(N-1)}{2}-L}\]

Donde \(L\) es la cantidad de links que tendrá la red, \(N\) el número de nodos que hemos definido, \(P^L\) es la probabilidad de links.

La distribución de grados de una red aleatoria es \(P(k)\) corresponde a una distribución binomial, en la que mientras más nodos tenga, más apuntalada estará y se acercará a k.

su distribución se puede entender como:

\[P(k)=\left(\begin{array}{c} N-1 \\ k \end{array}\right) p^k(1-p)^{(N-1)-k}\]

Selecciona k nodos de un conjunto de \(N-1\) nodos. y \(<k> = P(N-1)\). En el fondo es una función de densidad de probabilidad de distribuciòn de grados de una red aleatoria.

Sin embargo, por temas de facilidad, también se utilizan la distribución de poisson ya que es más fácil de computar, que responde a:

\[P(k) = e^-<k>\frac{<k>^k}{k!}\]

Aunque es importante recordar que en redes de pocos nodos se diferencian bastante una poisson de una binomial, en redes más grandes se asimilan mucho mejor ambas.

…Pero las redes random no son reales

En las redes random el nodo con más conexiones sería 1185, y por lo tanto encontrar un individuo con más de 2000 grados sería prácticamente imposible. En la realidad, las redes tienen muchos más nodos de lo que una red aleatoria señala.

La evolución de las conexiones de una red aleatoria se pueden definir en 4 grupos: Subcrítico (\(k < 1\)), Crítico (\(k = 1\)), Supercrítico (\(k <1\)) y Conectado (\(K > ln N\)). No es raro que con redes con grados promedio sobre uno la red contenga un componente principal, pero lo que sí es interesante es que con un grado promedio igual a 1 sea suficiente para que aparezca dicho componente. En otras palabras utilizando el ejemplo de Erdôs y Rènyi, basta con que sólo se tenga una conexión con una sola persona (promedio) para que la red completa sepa cuál es el vino caro.

4.2 Mundo Pequeño

Esta es otra propiedad peculiar de las redes, y responde a cuántas personas necesito para llegar a otra persona al azar. Esto parte con el experimento de Stanley Milgram de 1967, mandando postales desde Boston hasta Nebraska, con una descripción muy breve de quien era; se les solicitaba, entonces, que enviaran el paquete a quien ellos creían que pudiesen conocerse, bajo la condición de que conocieran los nombres de pila.

El resultado del experimento se ve en la siguiente imagen con la distribución de nodos necesarios para poder entregar el paquete:

Se ve entonces que los grados promedio son seis grados de separación promedio. Luego Facebook realizó el mismo experimento en 2016, y encuentra que la media es aún menor: 3.57.

Lo que importa del fenómeno del mundo pequeño más que e número, importa cómo la distancia promedio crece dependiendo del tamaño de la red , y de forma logarítmica.

4.2.1 Distancias en redes de mundo pequeño

Se calcula como

\[d_{max} = \frac{logN}{logk} \]

Con una aproximación de:

\[\langle d \rangle = \frac{logN}{Log\langle k \rangle}\]

Esto significa que las redes de mundo pequeño tienen la propiedad de que la longitud promedio de la trayectoria o el diámetro depende logarítmicamente del tamaño del sistema. Por lo tanto “pequeño” significa que \(\langle d \rangle\) es proporcional al logaritmo de N, en lugar de a N.

En definitiva, la gran diferencia de las redes aleatorias de mundo pequeño con las reales es que su distancia promedio es muy baja y se distribuye logaritmicamente, por lo que tendría que aumentar mucho el tamaño de la red para aumentar la distancia.

Podemos ver la comparación de distribuciones de distancias en redes en la siguiente imagen, que compara redes lineares, matrices, de 3d y redes random:

Esa curva roja es lo que se llama mundo pequeño, que tiene un carácter prácticamente asintótico.

4.2.2 Coeficiente de clustering en redes aleatorias de mundo pequeño

Se calcula como:

\[C_i \equiv \frac{2\langle L_i \rangle}{k_i(k_i -1)}\]

El coeficiente de clustering en una red random es una constante de valor P, que es igual a \(\frac{\langle k \rangle}{N}\), donde ambas son constantes. Además, tienden a ser coeficientes pequeños y que son independientes del grado k de nodos individuales (depende del grado promedio).

En resumen: los coeficiente sde clustering en redes aleatorias no dicen nada de los datos de redes reales

#### 4.2.3 Small world networks aleatorias (Watts & strogatz, 1998)

Ambos investigadores generan un algoritmo para crear redes aleatorias que tienen la propiedad de generar mundos pequeños. En este caso se genera una red aleatoria donde cada nodo tendrá un número determinado de edges, pero para generar el mundo pequeño se destruye el link original y se hace uno nuevo con probabilidad b, también llamado Rewriting probability, hasta llegar a la nueva red aleatoria con mundo pequeño.

Entonces la red va a tener el mismo coeficiente de clustering, pero la distancia promedio de la red será mucho menor, transformandose en mundo pequeño.

Según esta figura, los casos extremos sería en la esquina superior derecha, donde hay un alto clustering y alta distancia (como la red regular inicial), y la esquina inferior derecha con bajo clustering y baja y muy poca distancia. El fenómeno del mundo pequeño se da justamente entre ambos fenómenos: cuando hay un alto clustering y una baja distancia.

En síntesis, podemos decir de las redes random que

1. Nos entrega información útil sobre las distancias de la red en comparación a redes reales
2. Los coeficientes de clustering de las redes aleatorias subestiman en varios órdenes de magnitud el de las redes reales.
3. En lo que respecta la distribución de grado, las redes aleatorias no nos informan bien sobre las redes reales, ya que tiene a subestimar el nodo de grado mayor.

Pero sí nos informa bien de la longitud media de una red real.

Entonces … ¿Por qué carajos nos dedicamos a estudiar redes que aparentemente son irrelevantes?

Porque:

1. Se utiliza como modelo de referencia para el resto de las redes.
2. Ayuda a calcular cantidades que se pueden comparar con datos reales, para observar hasta qué punto es una propiedad particular el >resultado de algún proceso aleatorio.
3. Para observar patrones en redes reales.

Es decir las redes aleatorias nos sirven como un contrafactual para hacer inferencia sobre redes.

4.3 Redes libres de Escala

En distinta sdisciplinas se han estudiado redes regulares (como en física) y también redes aleatorias (como en matemáticas), pero los sistemas complejos no son ni regulares ni aleatorios.

Puede que sea una red libre de escala. ¿Qué significa eso? que no hay un lugar particular en la red en que se concentren la mayor cantidad de nodos. Cuando se habla de escala se refiere a que hay un lugar conocido y posible donde pasa la mayor cantidad de links (como en las distribuciones poisson de las que se habló anteriormente).

Las redes libre de estala se representan en gráficos de distribución Power Law, que implica que existe un multiplicador de potencias con valor constante que hace que los muchos nodos instalados en el lado izquierdo del gráfico c tengan el mismo peso que los pocos nodos con mucho poder dentro de la red. El Concepto de “libre de escala” captura la falta de una escala interna, una consecuendoa del hecho de que nodos con grados muy diferentes coexisten en la misma red.

Otras Propiedades:

En las redes libres de escala, si aumenta el tamaño de la red, aumentará el grado máximo.

En las redes libres de escala, el sistema completo está correlacionado. Por lo tanto los del mundo muy pequeño se ve igual que lo del mundo más grande. Todo ocurre en escala micro y macro.

Las redes libre de escala sus varianzas son infinitas.

El exponente es independiente del detalle de todo el sistema. Con un sólo número describo el sistema completo sin la necesidad de describir su detalle. es por esto que la gente los usa porque son muy simples

Esto movió una gran cantidad de investigación demostrando la universalidad de la presencia de redes libres de escala en muchos ámbitos (sociales, a nivel celular, en sistemas computacionales, etc), aunque con el tiempo han sido cuestionadas y se han encontrado algunos ámbitos donde no aparecen redes libres de escala (como en ciencia de materiales o redes eléctricas).

Propiedad ultrapequeña

Cuando tenemos redes libres de escala, la distancia promedio ya no es el logaritmo de N, sino que es el logaritmo del logaritmo de N. Es similar a lo que pasaba con las redes aleatorias, pero ahora con las libres de escala es mucho más pronunciado.

4.3.1 Graficar distribuciones de grado en redes libres de escala

Cuando se grafican las distribuciones de los grados, habitualmente pasamos de escalas lineares (gráfico a) que no dicen mucho a unos gráficos logaritmicos en escala pero con datos que aún son lineales (gráfico b). El problema que genera esto son esas “mecetas” de datos que se apilan en la parte baja del gráfico. Para arreglarlo se transforman a binning logaritmicos, que es cambiar los datos lineales a logaritmicos, ajustándose a la escala (gráfico c).

Finalmente el último gráfico D responde a la función de probabilidad acumulada para que se ajuste a la línea.

Sin embargo, no siempre es tan fácil ajustar los datos a una distribución power law. A veces existen saturaciones de grado bajo (como en el gráfico a) donde pocos puntos se desvían de la línea dibulada logaritmicamente. para esto lo que se hace es cortart la linea en base a un punto de sasturación \(K_{sat}\).

Su fórmula es:

\[p_x = a(k + k_{sat})^{-\gamma} exp(-\frac{k}{k_{sat}})\]

Cuando se traza la función p reescalada en \((k + k_{sat})\) la distribución de grados sigue una ley de potencia en todos los grados (gráfico b)

4.4 Preferential attachment

Modelo hecho por Barabási y Albert para generar redes libres de escala de manera aleatoria, similar al modelo Erdös-Rényi para redes aleatorias, pero para mantener esto. En este modelo crecimiento significa que tenemos una red que el número de nodos crecerá iterativamente en el tiempo hasta alcanzar el número de nodos deseado. Estos nodos se unirán anodos existentes, pero lo harán preferentemente a los más conectados.

El supuesto que está detrás lleva mucho tiempo siendo desarrollado pero con otros nombres (“Ventajas acumulativas”, “Mathew effect”, etc), que ondica que un nodo muy popular en un tiempo \(t\) acumulará más popularidad en un tiempo \(t + 1\).

Se parte con \(m0\) nodos, los enlaces entre los cuales se eligen arbitrariamente, siempre que cadaq nodo tenga al menos un enlace. Para \(N - m0\) iteraciones, agrege una nueva que se adjunte con \(m(< m0)\) enlaces a nodos preexistentes con probabilidad:

\[\prod(k_i) = \frac{K_i}{\sum_{j}k_i}\]

Las redes libres de escala aleatorias demuestran un mecanismo subyacente:

Crecimiento y apego preferencial: Se agregan nodos a la red con el tiempo, y estos nodos prefieren vincularse a los que están altamente conectados.

Ejemplo de “los ricos se hacen más ricos”.

Ventaja del primero: Los nodos que se agregan antes tienen grados más altos.

4.5 Modelos nulos

Estos modelos se utilizan para crear redes nuevas aleatorias preservando la cantidad de conexiones que tiene cada nodo. Esto se usa para destruir las razones por las cuales te conectas con otros nodos a nivel micro; por tanto todas las razones por las cuales tu te conectabas con dichos nodos ya no van. Acá se preserva la distribución de grado, no todos los grados de manera individual.

Por tanto lo que quiero saber es: ¿la forma de relacionarse entre nodos es por cuestiones de prerdisposiciones internas de cada uno o dependen de la combinación de nodos?.

Si lo que yo observo es igual a una red random, entonces es sólo la estructuras de las redes lo que está generando el fenómeno y no por las interacciones particulares de las personas.

La forma de realizarlo es en dos pasos: primero se considera el modelo de configuración, donde a cada nodo se le asigna una cantidad de “cabos” en bas ea la distribución de grados de la red. Luego cada nodo se reconecta en cada iteración haswta que todos se conecten. En este proceso iterativo puede que aparezcan nodos con bucles o con ciclos.

Los principios para poder conectarla se formulan en:

\[P_{ij} = \frac{k_i k_j}{2L-1}\]

Existe también el modelo de parámetro oculto, donde N nodos aislados y a cada uno se le agrega un parámetro oculto o \(\eta\) que es una probabilidad de conexión entra cada nodo. se obtiene algo bien similar al otro modelo.

¿Qué modelo usar?

Si hay secuencia de grados donde prohiba los múltiples links, es mejor usar un modelo de parámetro oculto.

Si tengo una distribuciónde grado que permita múltiples links, puedo usar un modelo de configuración.

4.5.1 Bootstrapping en redes bipartitas

4.6 Comunidades en redes

Varios algoritmos tienen como objetivo detectar grupos que consisten en nodos densamente conectados, sin embargo algunas comunidades de solapan. analizaremos algunos algoritmos para detectar estas comunidades.

La idea de la detección de comunidades es poder identificar a priori en una red las distintasd agrupaciones que se hacen sin tener que ir a preguntar directamente a qué comunidad perteneces. Ejercicio que se hizo en la famosa red del club de Karate de Zachary.

Para ello necesitamos introducir el concepto de modularidad

La función \(Q\) se describe como:

\[Q = \frac{1}{2L}\sum_{ij}\left[A_{ij}-\frac{k_ik_j}{2L}\right]\delta(c_i,c_j)\]

Donde \(A_{ij}\) es una matriz de adyacencia, \(\frac{k_ik_j}{2L}\) es la probabilida de un enlace entre dos nodos proporcional a sus grados, y \(delta(c_i,c_j)\) vale 1 si los nodos son de la misma comunidad. Mientras más grande es la matriz de adyacencia mejor será para crear grupos.

4.6.1 Algoritmo divisorio de Girvan y Newman

Este algoritmo usa el Link betweeness centrality, medida similar al betweeness centrality, para detectar los algoritmos que más conectan la red, y poco a poco los va “cortando” para ver la aparición de comunidades, como se explica en la siguiente imagen:

Como podemos ver, se calcula el link centrality una vez, se corta el link con el valor más alto, luego se vuelve a recalcular y se cortan los siguientes, y así sucesivamente hasta que todos los nodos quedan solos. Esto se registra en un gráfico de modularidad, y la cantidad de comunidades correcta es la que maximiza la modularidad

Ventajas y desventajas: es sencillo, intuitivo, pero lento.

Nota: Los límites de las comunidades nunca quedan perfectos, pero es útil de todas formas.

Utilizaremos la red no dirigida de ejemplo para mostrar el código de detección de comunidades:

# Detectar comunidades mediante el algoritmo de Girvan-Newman
ComGN <- edge.betweenness.community(red_no_dirigida)

# Imprimir número de comunidades detectadas
length(ComGN)

## [1] 4

plot(ComGN, red_no_dirigida)

4.6.2 Algoritmo de Fast-Greedy

Algoritmo que mejora mucho en velocidad. Los pasos del algoritmo son:

1. Asigna cada nodo a una comunidad propia. Empezamos con N comunidades

2. Inspecciona cada par de com,unidades que se conmectaban antes por al menos in enlace y calcula la variación de modularidad obtenida cuando se fusionan ambas

3. Identifica los pares de comunidades para los cuales \(\Delta M\) es más grande y fusionelos.

4. Repita el paso dos hasta que todos los nodos se fusionen en una sola comunidad

5. Registre para cada paso y seleccione la partición para la cual la modularidad es máxima.

El código para detectar comunidades es el siguiente:

# Detectar comunidades mediante el algoritmo Fast Greedy
ComFG <- fastgreedy.community(red_no_dirigida)

# Imprimir número de comunidades detectadas
length(ComFG)

## [1] 3

plot(ComFG, red_no_dirigida)

4.6.3 Algoritmo de Louvain

Algoritmo no supervisado (no requiere entrada de número de comunidaddes ni sus tamaños antes de ejecución) dividido en 2 fases: Optimización de la modularidad y agregación de la comunidad. Ambos pasos se ejecutarán hasta que no haya más cambios en la red y se consiga la máxima modularidad.

Este algoritmo este es el que más se usa porque es el de mejor calidad.

El código para detectar comunidades con este algoritmo es el siguiente:

# Detectar comunidades mediante el algoritmo de Louvain
ComLV<- cluster_louvain(red_no_dirigida)

# Imprimir número de comunidades detectadas
length(ComLV)

## [1] 3

plot(ComLV, red_no_dirigida)

Últimas notas sobre el concepto de modularidad

La modularidad es la calidad de una posible división de una red en comunidades. \(Q\) es un escalar entre -1 y 1, asociada con una red particular y una partición de la misma. Una particiòn optim a es 0.41 (gráfico a) donde con un sólo corte de nodo se obtienen dos comunidades claras, y una modularidad negativa (gráfico d) es que no se distinguen comunidades definidas. Pos otros lados una sola comunidad implicaría un valor de 09 y un subóptimo sería un valor positivo pero bajo (gráfico b).