UNIVERSIDAD NACIONAL DE COLOMBIA

Facultad de Ciencias

Maestría en Ciencias - Estadística

Relatoría: Conceptos fundamentales de teoría de grafos

Juan Felipe Moreno

Curso: Análisis Estadístico de Redes

Profesor: Juan Sosa, Ph.D.

Bogotá D.C., Colombia

13 de September de 2026

Introducción

La presente relatoría presenta un compendio de las clases del curso Análisis Estadístico de Redes Sociales, correspondiente al período académico 2026-II de la Maestría en Ciencias Estadísticas. Su objetivo es detallar algunos de los conceptos fundamentales de la teoría de grafos abordados durante las clases y presentes en el material del curso, disponible en El material del curso se encuentra disponible en Conceptos fundamentales de la teoría de grafos,elaborado por el profesor Juan Camilo Sosa. Estos contenidos se complementan con ejemplos y bibliografía adicional con el propósito de facilitar la comprensión de los conceptos estudiados.

En esta relatoría se abordará el tercer capítulo del curso, en el cual se presentan y desarrollan conceptos fundamentales de la teoría de grafos que serán necesarios para comprender los temas que se estudiarán posteriormente en el curso. Se hará énfasis en las definiciones, propiedades y representaciones de los grafos, acompañadas de ejemplos que permitan ilustrar su aplicación en el contexto del análisis de redes.

Grafos y Subgrafos

Un \(\textbf{grafo}\) es un par \(G=(V,E)\) formado por dos conjuntos, donde \(E\subseteq [V]^2\). Esto significa que los elementos de \(E\) son subconjuntos de \(V\) que contienen exactamente dos elementos. Para evitar ambigüedades en la notación, se supone siempre que \(V\cap E=\varnothing\) (Diestel 2017).

Los elementos de \(V\) se denominan \(\textbf{vértices}\) (también llamados nodos o puntos) del grafo \(G\).

Los elementos de \(E\) se conocen como \(\textbf{aristas}\) (o enlaces).

Una forma habitual de representar gráficamente un grafo consiste en dibujar un punto por cada vértice y conectar mediante una línea aquellos pares de puntos cuyos vértices correspondientes forman una arista. Lo fundamental es determinar \(\textbf{qué pares de vértices están conectados por una arista y cuáles no}\).

Ejemplo

Ejemplo tomado de Diestel, Graph Theory, quinta edición, 2017. pg.2

En este ejemplo podemos observar un grafo con 7 vértices, cuyo conjunto de vértices está dado por \(V=\{1,2,3,4,5,6,7\}.\)

El conjunto de aristas corresponde a los siguientes enlaces: \(E=\{\{1,2\},\{1,5\},\{2,5\},\{3,4\},\{5,7\}\}.\)

Subgrafo y Supergrafo

• Sea \(G'=(V',E')\). Decimos que \(G'\) es un \(\textbf{subgrafo}\) de \(G\) si, para \(G=(V,E)\), se cumple que \(V'\subseteq V\) y, al mismo tiempo, \(E'\subseteq E\)

• De manera equivalente podemos deinir la noción de \(\textbf{supergrafo}\), donde \(G\) es un super grafo de \(G'\) por el hecho de que \(V'\subseteq V\) y \(E'\subseteq E\)

Nota: Por facilidad de notación se usa \(G′ \subset G\) para indicar que \(G′\) es un subgrafo de \(G\).

Subgrafo inducido

Sea \(S\subset V\) un subconjunto de vértices. El \(\textbf{subgrafo inducido}\) por \(S\) es el grafo \(G_S=(S,E_S)\) que contiene exactamente los vértices de \(S\) y todas y solo las aristas del grafo original cuyos extremos pertenecen a \(S\) Formalmente, \[E_S=\{\{u,v\}\in E:u\in S,v\in S\}.\]

En otras palabras, un subgrafo inducido se obtiene al seleccionar un subconjunto de vértices \(S\subseteq V\) y conservar $$. Por lo tanto, una vez seleccionado el conjunto de vértices, el conjunto de aristas queda completamente determinado.

Ejemplo tomado de Diestel, Graph Theory, quinta edición, 2017. pg.4

En este ejemplo \(G\) es supergrafo de \(G'\) y \(G''\) (lo que es equivalente a decir que \(G′\) and \(G′′\) son subgrafos de \(G\) ) Tenemos que \(G′\) es un grafo inducido de \(G\), pero \(G′′\) no lo es.

Ejemplo

Vamos a usar la librería igraph (Csardi and Nepusz 2006) para todos los ejemplos a utilizar.

#Carga de librerias
suppressMessages(suppressWarnings(library(sand)))
suppressMessages(suppressWarnings(library(igraph)))
suppressMessages(suppressWarnings(library(RColorBrewer)))
suppressMessages(suppressWarnings(library(corrplot)))
suppressMessages(suppressWarnings(library(dplyr)))
suppressMessages(suppressWarnings(library(jsonlite)))
suppressMessages(suppressWarnings(library(readxl)))
suppressMessages(suppressWarnings(library(igraphdata)))

Vamos a crear un grafo binario no dirigido simple, desce cero con vértices \(V=\{1,2,3,4,5,6,7\}\) y aristas \(E= \left\{ \{1,2\}, \{1,3\},\{2,3\}, \{2,4\}, \{3,5\}, \{4,5\},\{3,4\}, \{3,6\}, \{4,6\}, \{4,7\}, \{5,6\}, \{6,7\} \right\}\)

Este grafo fue usado en el libro guía: Statistical Analysis of Network Data (Kolaczyk and Csárdi 2020)

# Grafo G
g <- graph_from_literal(
  1-2, 1-3, 2-3, 2-4, 3-5, 4-5,
  3-4, 3-6, 4-6, 4-7, 5-6, 6-7
)

# Subgrafo inducido H por los vértices 1,...,5
h <- induced_subgraph(g, 1:5)

# Configuración de la figura
par(mfrow = c(1, 2), mar = c(1, 1, 3, 1))

# Graficar G
set.seed(123)
plot(
  g,
  layout = layout_with_fr(g),
  vertex.color = "#4C78A8",
  vertex.frame.color = "white",
  vertex.frame.width = 2,
  vertex.size = 30,
  vertex.label.color = "white",
  vertex.label.cex = 1.2,
  edge.color = "#777777",
  edge.width = 2,
  main = "Grafo G"
)

# Graficar H
set.seed(123)
plot(
  h,
  layout = layout_with_fr(h),
  vertex.color = "#F58518",
  vertex.frame.color = "white",
  vertex.frame.width = 2,
  vertex.size = 30,
  vertex.label.color = "white",
  vertex.label.cex = 1.2,
  edge.color = "#777777",
  edge.width = 2,
  main = "Subgrafo inducido H"
)

# Restaurar configuración
par(mfrow = c(1, 1))

Propiedades de los grafos

Sean \(u,v \in V\)

• Adyacencia Se dice que dos vértices son adyacentes (denotado como \(u \sim v\)), si estan unidos por alguna arista de \(E\), es decir si \(\{u,v\} \in E\) (relación vértice - vértice)

• Incidencia Un vértice \(v\) es incidente con una arista \(e \in E\) si \(e=\{u,v\}\) para algún \(u\in V.\)

• Vecindad: Es el conjunto de vértices adyacentes a \(v\) , se denota como \(N_v= \{u \in V : u\sim v\}.\)

• El grado de un vértice \(v\) es el número de aristas incidentes en \(v\) y coincide con la cardinalidad de su vecindad: \(d_v = |N_v|.\) Es una medida de centralidad de la red que permite definir una noción de importancia de los vértices: los nodos más importantes de la red serán aquellos que tengan un mayor grado.

• Un vértice \(v\in V\) se llama aislado si \(v\nsim u \hspace{0.1cm} \forall_{u\in V}\). Note que esto es equivalente a que \(d_v=0\).

• Sea \(G=(V,E)\) podemos definir \(\delta_G := \min \{d_v | v \in V \}\) así como \(\Delta_G := \max \{d_v | v \in V \}\), que corresponden al grado mínimo y al grado máximo de \(G\), respectivamente. Estas medidas permiten identificar los vértices menos conectados y más conectados de la red.

• Otra cantidad de interés es el grado promedio de \(G\), denotado por \(\bar{d}_G:= \frac{1}{|V|} \sum_{v \in V} d_v\)

Mientras que el grado de un vértice describe su nivel de conectividad (lo veremos en un momento) de manera local, el grado promedio resume esta información a nivel global para todo el grafo.

• En un digrafo, podemos distinguir entre la vecindad de entrada y la vecindad de salida de un vértice \(v \in V\). La vecindad de entrada de \(v\) es el conjunto de vértices que tienen una arista dirigida hacia \(v\): \(N_v^{in}=\{u\in V:(u,v)\in E\}.\)

• A partir de este conjunto, se define el grado de entrada de \(v\) como : \(d_v^{in}=|N_v^{in}|,\) que corresponde al número de aristas que llegan a \(v\). Decimos que un nodo es popular si su grado de entrada es, en promedio, mayor que el de los demás nodos de la red.

• De manera análoga, la vecindad de salida de \(v\) es el conjunto de vértices hacia los cuales \(v\) tiene una arista dirigida:\(N_v^{out}=\{u\in V:(v,u)\in E\}.\)

• El grado de salida de \(v\) se define como \(d_v^{out}=|N_v^{out}|\) y corresponde al número de aristas que salen de \(v\).Decimos que un nodo es social si su grado de salida es, en promedio, mayor que el de los demás nodos de la red.

Ejemplos

Considérese el siguiente digrafo:

dg <- graph_from_literal(
  1-+2, 1-+3, 1-+4,
  2-+3, 2-+5,
  3-+5,
  4-+2,
  6-+3,
  7
)

# Tamaño , Orden , Tipo de red
cat(
  "Orden (número de nodos):", vcount(dg), "\n",
  "Tamaño (número de aristas):", ecount(dg), "\n",
  "¿Es dirigida?:", is_directed(dg), "\n",
  "¿Es ponderada?:", is_weighted(dg), "\n",
  "¿Es simple?:", is_simple(dg), "\n")

## Orden (número de nodos): 7 
##  Tamaño (número de aristas): 8 
##  ¿Es dirigida?: TRUE 
##  ¿Es ponderada?: FALSE 
##  ¿Es simple?: TRUE

par(mfrow = c(1,1), mar = c(1, 1, 2, 1))
set.seed(123)
plot(
  dg,
  vertex.color = "skyblue",
  vertex.size = 30,
  vertex.label.cex = 1.2,
  edge.arrow.size = 0.4,
  main = "Digrafo"
)

# Grado de entrada
degree(dg, mode = "in")

## 1 2 3 4 5 6 7 
## 0 2 3 1 2 0 0

# Grado de salida
degree(dg, mode = "out")

## 1 2 3 4 5 6 7 
## 3 2 1 1 0 1 0

#Grado Maximo y Promedio:
cat("Grado promedio:",mean_degree(dg),"\n", "Grado maximo:", max_degree(dg))

## Grado promedio: 1.142857 
##  Grado maximo: 4

par(mfrow = c(1,2))

#Distribución de grados de entrada vs grados de salida en dg

hist(
  degree(dg, mode = "in"),
  breaks = seq(-0.5, max(degree(dg, mode="in"))+0.5, 1),
  col = "#F58518",
  main = "Grado de entrada",
  xlab = "d_in"
)

hist(
  degree(dg, mode = "out"),
  breaks = seq(-0.5, max(degree(dg, mode="out"))+0.5, 1),
  col = "#4C78A8",
  main = "Grado de salida",
  xlab = "d_out"
)

Ahora vamos a convertir a ese grafo dirigido en uno no-dirigido:

g_ud <- as_undirected(dg)

Encontremos entonces vértices adyacentes, aislados y aristas incidentes

# Vértices aislados
V(g_ud)[degree(g_ud) == 0]

## + 1/7 vertex, named, from 123b596:
## [1] 7

# Vértices adyacentes a 2
(nb2 <- neighbors(g_ud, v = 2))

## + 4/7 vertices, named, from 123b596:
## [1] 1 3 4 5

# Aristas incidentes en el vértice 2
(ic2 <- incident(g_ud, v = 2, mode = "all"))

## + 4/8 edges from 123b596 (vertex names):
## [1] 1--2 2--3 2--4 2--5

# Colores de vértices
v_col <- rep("lightblue", vcount(g_ud))
v_col[2] <- "khaki"
v_col[as.numeric(nb2)] <- "khaki"

# Colores de aristas
e_col <- rep("grey70", ecount(g_ud))
e_col[ic2] <- "khaki"

# Visualización
par(mfrow = c(1,1), mar = c(1,1,2,1))

par(mfrow = c(1,1), mar = c(1, 1, 2, 1))
set.seed(123)
plot(
  g_ud,
  layout = layout_with_fr(g_ud),
  vertex.color = v_col,
  vertex.size = 30,
  vertex.label.cex = 1.2,
  vertex.frame.color = "white",
  edge.color = e_col,
  edge.width = ifelse(e_col == "khaki", 3, 1),
  main = "Vecindad del vértice 2"
)

Movimiento

Una caminata (walk) de \(v_0\) a \(v_\ell\) de longitud \(\ell\) es una secuencia alternante de vértices y aristas \(\{v_0,e_1,v_1,e_2,v_2,\ldots,v_{\ell-1},e_\ell,v_\ell\}\) tal que, para cada \(i = 1,\ldots,\ell\), los extremos de \(e_i\) son \(\{v_{i-1},v_i\}\). En una caminata se permiten vértices y aristas repetidos. Notemos que el orden de una caminata de longitud \(\ell\) coincide con el número de aristas en la caminata.

• Una caminata cerrada es aquella en la que el vértice inicial coincide con el vértice final, es decir, \(v_0=v_{\ell}\), por ejemplo: \[1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 2 \rightarrow 1\] .

• En caso contrario decimos que es una caminata abierta, por ejemplo: \[1 \rightarrow 2 \rightarrow 3 \rightarrow 2 \rightarrow 4\].

Un Recorrido (trail) es una caminata abierta en la que no se repite ninguna arista (aunque si pueden repetirse vértices).

Un Camino (path) es un recorrido en el que no se repite ningún vértice. (Es equivalente a una caminata abierta en la que No se pueden repetir vértices ni aristas)

Conectividad

• Se dice que un vértice \(v\) es accesible (reachable) desde otro vértice \(u\) si existe al menos una caminata desde \(u\) hasta \(v\).(Kolaczyk and Csárdi 2020)

• Se dice que un grafo está conectado (connected) si cada vértice es accesible desde cualquier otro. (Kolaczyk and Csárdi 2020), es decir si entre cada par de vértices \(u,v\), existe una caminata que los une.

• Un dígrafo está débilmente conectado (weakly connected) si su grafo subyacente, obtenido al ignorar la dirección de las aristas, es conectado.

• Un dígrafo está fuertemente conectado (strongly connected) si, para todo par de vértices \(u,v\) existe una caminata dirigida de \(u\) a \(v\) (\(u\) → \(v\)) y de \(v\) a \(u\) (\(v\) → \(u\)). Es decir, si cada vértice es accesible desde cualquier otro mediante aristas dirigidas.

• Una componente conexa (connected component) o simplemente componente de un grafo es un subgrafo conexo maximal, es decir, un subgrafo conexo al que no se le puede añadir ningún otro vértice del grafo sin perder la conectividad (o, equivalentemente, sin dejar de ser conexo). Que un subgrafo sea conexo máximal no implica que todos los vértices esten conectados entre todos.

Un grafo con tres componentes conexas, Ejemplo tomado de Diestel, Graph Theory, quinta edición, 2017. pg.11

• La componente gigante (giant component) de un grafo es la componente conexa de mayor tamaño, es decir, la componente que contiene el mayor número de vértices. En otras palabras La componente gigante es el subgrafo más grande de una red, en el que todos los nodos son accesibles desde cualquier otro mediante algún camino. En grafos grandes, suele ser la componente que agrupa una fracción significativa del total de vértices y concentra la mayor parte de los caminos del grafo.

• Las Asignaciones (Memberships) de las componentes indican la pertenencia de cada nodo a una componente. En particular, \(\xi_i=k\) significa que el (i)-ésimo nodo pertenece a la componente \(k\), donde \(i=1,2,\ldots,n=|V|\) y \(\quad k=1,2,\ldots,K\), siendo \(K\) el número total de componentes.

\[ \boldsymbol{\xi} = \begin{pmatrix} \xi_1\\ \xi_2\\ \vdots\\ \xi_n \end{pmatrix} \]

De manera equivalente, la componente \(C_k\) se puede definir como el conjunto de nodos cuya asignación es \(k\) :\(\quad C_k= \left\{i \in V: \xi_i =k \right\}\)

Ejemplo

library(igraph)

# 1. Red
set.seed(123)
g <- graph_from_literal(
  A--B, A--C, A--D, B--C, B--E, B--F,
  C--D, C--F, D--F, D--G, E--F, E--H,
  F--G, F--H, G--H, G--I, H--I, H--J,
  I--J, I--K, J--K, J--L, K--L, K--M,
  L--M, M--N, M--O,
  
  P--Q, P--R, Q--R, Q--S, R--S, S--T,
  
  U,
  V
)

is_connected(g)

## [1] FALSE

# 2. Encontrar la componente gigante
comp <- components(g)
comp

## $membership
## A B C D E F G H I J K L M N O P Q R S T U V 
## 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 3 4 
## 
## $csize
## [1] 15  5  1  1
## 
## $no
## [1] 4

giant_id <- which.max(comp$csize)
set.seed(123)
g_giant <- induced_subgraph(
  g,
  vids = V(g)[comp$membership == giant_id]
)

# 3. Calcular layouts

set.seed(123)
lay_g <- layout_with_fr(g)
set.seed(123)
lay_giant <- layout_with_fr(g_giant)

# 4. Comparar la red completa y la componente gigante

par(
  mfrow = c(1, 2),
  mar = c(1, 1, 3, 1)
)
set.seed(123)
plot(
  g,
  layout = lay_g,
  vertex.size = 10,
  vertex.color = "steelblue",
  vertex.frame.color = "white",
  vertex.label = NA,
  edge.color = "grey60",
  edge.width = 1.5,
  main = "Red completa"
)
set.seed(123)
plot(
  g_giant,
  layout = lay_giant,
  vertex.size = 10,
  vertex.color = "firebrick2",
  vertex.frame.color = "white",
  vertex.label = NA,
  edge.color = "grey60",
  edge.width = 1.5,
  main = "Componente gigante"
)

Ejemplo 2 Red de Citación VIH

La red representa el patrón de citación entre 146 blogs relacionados con el VIH/sida, los pacientes y sus redes de apoyo, recopilados por Suchi Gopal (Gopal 2007) durante un período de tres días seleccionado aleatoriamente en agosto de 2005. Los vértices representan los blogs y las aristas dirigidas representan las relaciones de referencia entre ellos: una arista desde un blog hacia otro indica que el primero incluye un enlace al segundo en su página web, específicamente dentro de su lista de enlaces o blogroll.

data(aidsblog)
g <- aidsblog
g$name <- "AIDS Blog Network"

## This graph was created by an old(er) igraph version.
## ℹ Call `igraph::upgrade_graph()` on it to use with the current igraph version.
## For now we convert it on the fly...

# Tamaño , Orden , Tipo de red
cat(
  "Orden (número de nodos):", vcount(g), "\n",
  "Tamaño (número de aristas):", ecount(g), "\n",
  "¿Es dirigida?:", is_directed(g), "\n",
  "¿Es ponderada?:", is_weighted(g), "\n",
  "¿Es simple?:", is_simple(g), "\n")

## Orden (número de nodos): 146 
##  Tamaño (número de aristas): 187 
##  ¿Es dirigida?: TRUE 
##  ¿Es ponderada?: FALSE 
##  ¿Es simple?: FALSE

cat("Red Conectada débilmente?:", is_connected(graph = g, mode = "weak"), "\n",
"Red Conectada fuertemente?:", is_connected(graph = g, mode = "strong"))

## Red Conectada débilmente?: TRUE 
##  Red Conectada fuertemente?: FALSE

set.seed(123)
lay <- layout_with_fr(g)

plot(
  g,
  layout = lay,
  vertex.size = 7,
  vertex.label = NA,
  vertex.color = V(g)$color,
  vertex.frame.color = "white",
  edge.color = "gray70",
  edge.arrow.size = 0.15,
  edge.width = 1,
  main = "Red de Blogs sobre VIH/SIDA"
)

# Componentes débilmente conectadas
components(g, mode = "weak")

## $membership
##   [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [38] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [75] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [112] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## 
## $csize
## [1] 146
## 
## $no
## [1] 1

# Componentes débilmente conectadas
components(g, mode = "strong")

## $membership
##   [1] 143 142 141 140 139 138  28  65  27 137  26  78 136 135  64  25  37  63
##  [19] 134  24  62  23  77  76 133 132 100 131 130  61  75  60  74  99  73  22
##  [37]   1  98 129 128  97 127  72  10  59  21 126  71 125  70 124   9  58  20
##  [55]  96  69  95 123  68  67  19  57  18 122  17  66   8  94  93  16  92  36
##  [73]  50  91 121  90  89 120  35 119 118  88  87  49  56  48   7   6  15  34
##  [91]  33 117  47  55  54  46 116 115  86   5  14  85  32 114  84  45 113  83
## [109]  82  81  80  13 112 111  12  44  11   2   4 110   3  53  43 109  52 108
## [127] 107 106 105  42  41  40  39  28  38 104  51 103 102  31 101  28  28  79
## [145]  30  29
## 
## $csize
##   [1] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 1
##  [38] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
##  [75] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## [112] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
## 
## $no
## [1] 143

Distancia

• Una noción común de distancia entre dos vértices \(u\) y \(v\) de un grafo, denotada por \(d(u,v)\), se define como la longitud del camino más corto entre ellos. Si no existe ningún camino que conecte los dos vértices, la distancia se define como infinita, es decir, \(d(u,v) = \infty\). A menudo, esta distancia se denomina distancia geodésica, y geodésico es el término utilizado para referirse a un camino más corto (Kolaczyk and Csárdi 2020).

• El diámetro de un grafo \(G=(V,E)\), denotado por \(\operatorname{diam}(G)\), es la mayor distancia geodésica finita entre cualquier par de vértices \(u,v\in V\): \(\operatorname{diam}(G)=\max_{u,v\in V}d(u,v)\).

• La distancia geodésica promedioes el promedio de las distancias geodésicas entre pares de vértices conectados y proporciona una medida del grado de separación global de los vértices del grafo.

• La excentricidad de un vértice \(v\) se define como \(\epsilon(v) = \operatorname{max}_u d(u,v)\) , y el diámetro es el máximo de las excentricidades.

Ejemplos

Ejemplo French Political Blogs

El conjunto de datos French Political Blogs corresponde a una subred de blogs políticos franceses extraída de una recopilación superior a 1.100 blogs observados durante octubre de 2006.

Los blogs fueron clasificados según su afiliación política por el proyecto Observatoire Présidentielle. La red contiene:

• 192 blogs (nodos).
• 1.431 relaciones (aristas).
• Diversos partidos políticos representados mediante atributos de los nodos.

summary(fblog)

## This graph was created by an old(er) igraph version.
## ℹ Call `igraph::upgrade_graph()` on it to use with the current igraph version.
## For now we convert it on the fly...

## IGRAPH 3e87bca UN-- 192 1431 -- 
## + attr: name (v/c), PolParty (v/c)

V(fblog)$PolParty <- trimws(V(fblog)$PolParty)
party.names <- unique(V(fblog)$PolParty)
head(party.names)

## [1] "Les Verts"               "UMP"                    
## [3] "UDF"                     "PS"                     
## [5] "Parti Radical de Gauche" "PCF - LCR"

La variable PolParty contiene la afiliación política de cada blog y será utilizada para diferenciar visualmente los nodos mediante colores.

Para generar una representación adecuada de la red se utiliza el algoritmo de distribución de Kamada-Kawai, ampliamente empleado en análisis de redes por su capacidad para ubicar nodos relacionados en posiciones cercanas.

Visualización de la red política

La Visualización muestra la estructura relacional de los blogs políticos franceses. Cada color representa una afiliación política distinta.

Veamos la componente gigante de G

#Componente de g
comp <- components(fblog)
#Componente gigante
giant_id <- which.max(comp$csize)

g_giant <- induced_subgraph(
  fblog,
  vids = V(fblog)[comp$membership == giant_id]
)

# Tamaño , Orden , Tipo de red
cat(
  "Orden (número de nodos):", vcount(g_giant), "\n",
  "Tamaño (número de aristas):", ecount(g_giant), "\n",
    "Diametro componente gigante:",diameter(g_giant, directed = TRUE), "\n",
    "Distancia promedio componente gigante:",mean_distance(g_giant, directed = TRUE), "\n",
  "Conectada componente gigante?:", is_connected(g_giant)
  )

## Orden (número de nodos): 192 
##  Tamaño (número de aristas): 1431 
##  Diametro componente gigante: 5 
##  Distancia promedio componente gigante: 2.538667 
##  Conectada componente gigante?: TRUE

# Partidos políticos y colores asociados
party_colors <- c(
  "Les Verts"               = "forestgreen",
  "UMP"                     = "royalblue",
  "UDF"                     = "deepskyblue3",
  "PS"                      = "red3",
  "Parti Radical de Gauche" = "deeppink",
  "PCF - LCR"               = "darkred",
  "liberaux"                = "steelblue",
  "Commentateurs Analystes" = "gray50",
  "Cap21"                   = "darkorange"
)
# Asignar color a cada nodo según su partido
V(g_giant)$color <- party_colors[V(g_giant)$PolParty]

set.seed(42)

# Layout
lg <- layout_with_kk(g_giant)

plot(
  g_giant,
  layout = lg,
  vertex.label = NA,
  vertex.color = V(g_giant)$color,
  vertex.size = 8,
  edge.color = "gray70",
  edge.width = 0.5,
  main = "Red de Blogs Políticos Franceses"
)

# Leyenda
legend(
  "topleft",
  legend = names(party_colors),
  fill = party_colors,
  bty = "n",
  cex = 0.7,
  y.intersp = 0.8
)

Red de Blogs Políticos Franceses

Red de Interacción de Twitter en el Congreso de Estados Unidos

Esta red representa las interacciones en Twitter entre los miembros del 117.º Congreso de los Estados Unidos, incluyendo tanto la Cámara de Representantes como el Senado. Los datos fueron recopilados mediante la API de Twitter y se utilizaron para estimar las probabilidades empíricas de transmisión entre congresistas, calculadas a partir de la frecuencia con la que un miembro retuiteó, citó, respondió o mencionó las publicaciones de otro. Para conocer más detalles sobre la metodología empleada y el análisis realizado, se recomienda consultar la publicación original. (Fink et al. 2023)

edges <- read.table(
  "/cloud/project/Relatoria 2/congress.edgelist",
  header = FALSE
)
edges[,4] <- gsub("}", "", edges[,4])


g <- graph_from_data_frame(
  d = edges[,1:2],
  directed = TRUE
)

E(g)$weight <- as.numeric(edges[,4])

Sin embargo no hay suficiente información nodal de interés, con la ayuda de la inteligencia artificial Gemini 3.6 Flash (Google DeepMind 2026)y la lista de miembros del 117 congreso:Lista de Miembros del 117 Congreso de USA vamos a agregar información nodal como el probable partido politico de pertenencia, recordemos que nuestros nodos son cuentas de Twitter (ahora X).

nodal_info_joined<-read_excel("/cloud/project/Relatoria 2/usuarios_congreso_actualizado.xlsx")

tail(nodal_info_joined)

Añadiendo esta información adicional a nuestra red:

#añadiendo info del partido
V(g)$party <- trimws(nodal_info_joined$partido)
#añadiendo info de la camara (senate or house of representatives)
V(g)$chamber<-trimws(nodal_info_joined$camara)
#añadiendo nombres de congresistas
V(g)$congressperson<-trimws(nodal_info_joined$congresista)

# Tamaño , Orden , Tipo de red, Diametro, Distancia promedio
cat(
  "Orden (número de nodos):", vcount(g), "\n",
  "Tamaño (número de aristas):", ecount(g), "\n",
  "¿Es dirigida?:", is_directed(g), "\n",
  "¿Es ponderada?:", is_weighted(g), "\n",
  "¿Es simple?:", is_simple(g), "\n",
"Diametro",round(diameter(g, directed = TRUE),3), "\n",
    "Distancia promedio", round(mean_distance(g, directed = TRUE),3), "\n")

## Orden (número de nodos): 475 
##  Tamaño (número de aristas): 13289 
##  ¿Es dirigida?: TRUE 
##  ¿Es ponderada?: TRUE 
##  ¿Es simple?: TRUE 
##  Diametro 0.031 
##  Distancia promedio 0.006

set.seed(123)

# ============================================================
# 1. Seleccionar el 10% de nodos con mayor grado
# ============================================================

deg <- degree(g, mode = "all")

umbral <- quantile(deg, 0.90)

g_top <- induced_subgraph(
  g,
  vids = which(deg >= umbral)
)


# ============================================================
# 2. Atributos visuales de los nodos
# ============================================================

# 1. Atributos visuales de los nodos
# ============================================================

# Colores según partido político
party_colors <- c(
  "Demócrata" = "dodgerblue3",
  "Republicano" = "firebrick2",
  "Independiente" = "gold"
)


V(g_top)$color <- party_colors[V(g_top)$party]

V(g_top)$color[is.na(V(g_top)$color)] <- "grey70"


# Forma según cámara
V(g_top)$shape <- ifelse(
  V(g_top)$chamber == "Senado",
  "square",
  "circle"
)


# Tamaño según grado
deg_top <- degree(g_top)

V(g_top)$size <- 3 * sqrt(deg_top)


# ============================================================
# 3. Escalar los pesos de las aristas DE g_top
# ============================================================



w <- E(g_top)$weight

# Evitar problemas si todos los pesos son iguales
if (max(w, na.rm = TRUE) == min(w, na.rm = TRUE)) {
w_scaled <- rep(0.5, length(w))
} else {
  w_scaled <- (w - min(w, na.rm = TRUE)) /
    (max(w, na.rm = TRUE) - min(w, na.rm = TRUE))}


# ============================================================
# 4. Color de las aristas
# ============================================================

edge_cols <- colorRampPalette(
  c("grey90", "grey75", "grey50")
)(100)

edge_color_base <- edge_cols[
  pmax(
    1,
    pmin(
      100,
      round(1 + 99 * w_scaled)
    )
  )
]

edge_rgb <- col2rgb(edge_color_base) / 255


# Transparencia
edge_alpha <- 0.05 + 0.22 * w_scaled

edge_color <- rgb(
  edge_rgb[1, ],
  edge_rgb[2, ],
  edge_rgb[3, ],
  alpha = edge_alpha
)


# ============================================================
# 5. Etiquetar solo los 2 nodos más importantes
# ============================================================

top2 <- order(
  deg_top,
  decreasing = TRUE
)[1:min(2, length(deg_top))]

labels <- rep(
  "",
  vcount(g_top)
)

labels[top2] <- V(g_top)$congressperson[top2]


# ============================================================
# 6. Layout
# ============================================================

set.seed(123)

lay <- layout_with_fr(g_top)


# ============================================================
# 7. Gráfico
# ============================================================

par(
  mfrow = c(1, 1),
  mar = c(0, 0, 2, 0)
)

plot(
  g_top,
  layout = lay,

  # -------------------------
  # Nodos
  # -------------------------
  vertex.color = V(g_top)$color,
  vertex.shape = V(g_top)$shape,
  vertex.size = V(g_top)$size,

  vertex.label = labels,
  vertex.label.cex = 0.9,
  vertex.label.color = "black",
  vertex.frame.color = "white",

  # -------------------------
  # Aristas
  # -------------------------
  edge.width = 0.3 + 4 * w_scaled,
  edge.color = edge_color,

  # Flechas
  edge.arrow.size = 0.15 + 0.45 * w_scaled,

  # Curvatura
  edge.curved = 0.08,

  # -------------------------
  # Título
  # -------------------------
  main = "Congresistas más influyentes en Twitter\n(Top 10% por grado)"
)


# 8. Leyenda 
legend( "topleft", legend = c("Demócrata", "Republicano", "Independiente"), col = c("dodgerblue3", "firebrick2", "gold"), pch = 19, pt.cex = 1.5, bty = "n", title = "Partido" ) 

legend( "topright", legend = c("Cámara", "Senado"), pch = c(21, 22), pt.bg = "black", pt.cex = 1.5, bty = "n", title = "Corporación" )

cat( "Conectado débilmente?",
is_connected(graph = g_top, mode = "weak") , "\n",
 "Conectado fuertemente?",
is_connected(graph = g_top, mode = "strong"))

## Conectado débilmente? TRUE 
##  Conectado fuertemente? TRUE

Supongamos que tenemos interés por un nodo particular, en este caso los tuits del Senador Bernie Sanders uno de los pocos Senadores Independientes, del congreso de Estados Unidos.

# Matriz de distancias
d <- distances(g)
d[!is.finite(d)] <- NA

# Mayores distancias desde Sanders
x <- which(
  d[V(g)$congressperson == "SenSanders", ] ==
    max(d[V(g)$congressperson == "SenSanders", ], na.rm = TRUE)
)

data.frame(
  Node = x,
  Congressperson = V(g)$congressperson[x],
  Distance = d[V(g)$congressperson == "SenSanders", x]
)

Dentro de la lista de vértices con mayor distancia geodésica respecto a Sanders encontramos al representante John Wilson, republicano por Carolina del Sur. Analizar la relación entre ambos dentro del grafo resulta de interés debido a la marcada diferencia entre sus posiciones políticas. Wilson se identifica con posiciones cercanas al movimiento MAGA, mientras que Sanders es una de las figuras más representativas del ala progresista. Esta diferencia permite explorar cómo la distancia ideológica entre ambos se refleja en la estructura de la red y qué actores permiten conectar sus respectivos sectores políticos.

from <- which(V(g)$congressperson == "SenSanders")
to <- which(V(g)$congressperson == "RepWilson")
# Caminata
walk<-shortest_paths(
  g,
  from = from,
  to = to,
  weights = NA
)$vpath[[1]]

paste0(
  as.numeric(walk),
  " - ",
  V(g)$congressperson[as.numeric(walk)]
)

## [1] "71 - SenSanders"   "145 - JudgeCarter" "399 - RepSarbanes"
## [4] "470 - RepWilson"

La relación entre Wilson y Sanders resulta de interés debido a la marcada distancia ideológica que representan dentro del espectro político estadounidense. Analizar la distancia geodésica entre ambos permite explorar hasta qué punto esta separación ideológica se refleja en la estructura de la red. Además, los nodos que aparecen en el camino geodésico más corto pueden proporcionar información sobre los actores que conectan comunidades políticas estructuralmente diferenciadas.

En este caso, el camino más corto está compuesto por Bernie Sanders (D) → John Carter (R) → John Sarbanes (D) → Wilson (R). John Carter aparece en la red como JudgeCarter, correspondiente a su cuenta de Twitter, mientras que John Sarbanes aparece como RepSarbanes. Resulta particularmente llamativa la alternancia entre representantes demócratas y republicanos (D–R–D–R) a lo largo del camino. Esta estructura sugiere que, a pesar de la distancia ideológica entre los extremos del camino, la red presenta conexiones que atraviesan distintas comunidades partidistas. Los actores intermediarios, en particular Carter y Sarbanes, pueden ser analizados como posibles puentes estructurales entre estos sectores de la red.

# Caminos
all_shortest_paths(graph = g, from = from, to = to)$res

## [[1]]
## + 5/475 vertices, named, from 6a6792d:
## [1] 111 215 195 264 395

# Distribución de las distancias
distance_table(g)

## $res
## [1]  13289 119441  86580   2883    112      1
## 
## $unconnected
## [1] 2844

# Gráfico de distancias geodésicas
caminos <- distance_table(g_top)$res
distancias <- 1:length(caminos)

barplot(
  prop.table(caminos),
  names.arg = distancias,
  xlab = "Distancia geodésica",
  ylab = "Frecuencia relativa",
  main = "Distribución de distancias geodésicas",
  col = "steelblue",
  border = NA,
  ylim = c(0, max(prop.table(caminos)) * 1.1)
)

Referencias

Csardi, Gabor, and Tamas Nepusz. 2006. “The Igraph Software Package for Complex Network Research.” InterJournal, Complex Systems 1695.

Diestel, Reinhard. 2017. Graph Theory. 5th ed. Vol. 173. Graduate Texts in Mathematics. Springer. https://doi.org/10.1007/978-3-662-53622-3.

Fink, Christian G, Nathan Omodt, Sydney Zinnecker, and Gina Sprint. 2023. “A Congressional Twitter Network Dataset Quantifying Pairwise Probability of Influence.” Data in Brief.

Google DeepMind. 2026. Gemini 3.6 Flash: AI Assistant. Https://gemini.google.com.

Gopal, Suchi. 2007. “The Evolving Social Geography of Blogs.” In Societies and Cities in the Age of Instant Access, edited by H. Miller. Springer.

Kolaczyk, Eric D., and Gábor Csárdi. 2020. Statistical Analysis of Network Data with r. 2nd ed. Use r! Springer. https://doi.org/10.1007/978-3-030-44129-6.