Capítulo 2 - Manipulando datos de una red

Manipulación de datos

1.    Introducción

Hemos visto que el término "red" se refiere a una colección de elementos y sus interrelaciones, el concepto matemático de un grafo da precisión a esta noción, como representación de un sistema complejo, un grafo por sí solo suele ser insuficiente.

También puede ser conveniente asociar vértices o aristas con grupos, podemos imaginar potencialmente equipar vértices y aristas con varias variables de interés.

Al usar grafos para representar datos de la red con conceptos básicos de teoría de grafos, así como la habilidad de evaluar ciertas propiedades básicas de grafos, igraph es particularmente útil para crear, decorar y evaluar las propiedades básicas de los grafos, igraph es una biblioteca y un paquete de R para análisis de redes, contiene un conjunto de tipos de datos y funciones para una implementación sencilla y rápida creación de prototipos de algoritmos de grafos y permite el manejo rápido de grafos grandes.

2.    Creación de los grafos

2.1.    Grafos no dirigidos y dirigidos

Formalmente, un grafo $G=(V,E)$ es una estructura matemática que consta de un conjunto $V$ de $V$ vértices y un conjunto $E$ de aristas, donde los elementos de $E$ son pares desordenados ${u,v}$ de vértices distintos ${u,v} \in V$.

En igraph hay una clase "igraph" para grafos, a continuación, veremos:

• Formas de crear un objeto de la clase igraph en R.

• Formas de extraer y resumir la información en ese objeto.

Para grafos de “juguete pequeños”, se puede utilizar la función $graph.formula$, para asignar un nombre al grafo por ejemplo $G$, y definir las aristas y los vértices de este. 

• library(igraph)
• g<-graph.formula("1-2,1-3,2-3,2-4,3-5,4-5,4-6,4-7,5-6,6-7")
• $V(G)$, ver los vértices del grafo $G$.
• $E(G)$, ver las aristas del grafo $G$.
• str(G), ver los vértices y reconocer con que vértices está conectado.
  
• plot(G), representación visual del grafo.
  

Las aristas dirigidas en graph.formula se indican mediante una convención menos y más.

• dg <- graph.formula("1-+2,1-+3,2++3" )

Al definir el grafo anterior se utilizó la convención estándar de etiquetar los vértices con los números del 1 al $N_v$, que también es el predeterminado en igraph. Se puede usar etiquetas personalizadas en lugar de la opción predeterminada generando el grafo con ellas de forma explícita.

• dg <- graph.formula("Sam-+Mary,Sam-+Tom,Mary++Tom")

También es posible cambiar las etiquetas de vértice desde las predeterminadas después de crear inicialmente el grafo

• V(dg)$name <- c("Sam","Mary","Tom"")

2.2.    Representaciones para Grafos

La información para construir un grafo normalmente se almacenará en un archivo de datos, hay tres formatos básicos: listas de adyacencia, listas de aristas y matrices de adyacencia.

Lista de adyacencia de un grafo $G$ es una matriz de tamaño $N_v$, ordenada con respecto al orden de los vértices en $V$, esta es la representación predeterminada que usa igraph, al imprimir la salida mediante el comando str(G).

Lista de aristas, es una lista simple de dos columnas de todos los pares de vértices que están unidos por una arista. En igraph, las listas de aristas se imprimen en el conjunto de aristas $E$, get.edgelist devuelve una lista de aristas como una matriz R de dos columnas.

La matriz de adyacencia $N_v×N_v$ para un grafo $G=(V,E)$, digamos $A$, se define de la siguiente  forma

\[ A = \begin{cases} 1, & \text{si {i,j}} ∈E;\\ 0, & \text{sino}. \end{cases} \]

Es posible ver el resultado con el comando get.adjacency(G) 

En igraph, se pueden generar grafos usando las funciones graph.adjlist, graph.edgelist y graph.adjacency.

• read.graph, leer datos almacenados en un archivo. 
• write.graph, se puede guardar grafos en varios formatos.

2.3.    Operaciones sobre Grafos

Es posible que los grafos que podamos cargar en R no sean las que queremos, puede incluso ser necesario aplicar varias operaciones en ellos:

• Extracción de parte de un grafo.
• Eliminación de vértices.
• Adición de aristas. 
• Combinación de varios grafos.

A menudo estamos interesados en un subgrafo inducido de un grafo $G$, es decir, un subgrafo $G = (V,E)$. Por ejemplo: 

• h <- induced.subgraph("g,1:5")

Exclusión de vértices o aristas en un grafo $G = (V,E)$, Por ejemplo:

• h <- g - vertices("c(6,7)")

$G$ puede restaurarse a partir de h agregando los vértices y las aristas apropiados.

• h <-h+ vertices("c(6,7)")
• g <- h + edges("c(4,6),c(4,7),c(5,6),c(6,7)")

La unión de dos grafos, $H1$ y $H2$, da un grafo $G$ en el que incluyen vértices y aristas si y solo si se encuentra en al menos uno de $H1$ o $H2$. Por ejemplo:

• h1<-h  
• h2<-graph.formula("4-6,4-7,5-6,6-7")
• g<x-graph.union("h1,h2")

3.    Decoración de grafos

3.1.    Atributos de vértice, arista y grafo

En el corazón de una representación basada en la red de datos de un sistema complejo habrá un grafo, también se pueden obtener otros datos relevantes, estos se pueden considerar como atributos: valores asociados con el grafo correspondiente y equipar un grafo con estos atributos se denomina decoración del grafo, los vértices o las aristas de un grafo están decorados con atributos, aunque el grafo en su conjunto también puede estar decorado. 
En igraph, los elementos de los objetos grafos pueden equiparse con atributos solo usando el operador "$".
Los atributos de vértice son variables indexadas por vértices y pueden ser de tipo discreto o continuo. Por ejemplo, los nombres de los tres actores en el grafo $dg$ son:

• V(dg)$name
• [1] "Sam" "Mary" "Tom"

Se agrega el género a dg como:

• V(dg)$gender <- c("M","F","M")

Hay que tener en cuenta que la noción de atributos de vértice puede usarse para equipar los vértices con propiedades durante el curso de un análisis, Por ejemplo, asociar el color rojo con los vértices que se utilizará para trazar el grafo

• V(g)$color <− "red"

De manera similar, los atributos de arista son valores de variables indexadas por pares de vértices adyacentes y, al igual que con los atributos de vértice, pueden ser tanto de tipo discreto como continuo.

A menudo, los atributos de las aristas se pueden considerar de manera útil, para los propósitos de varios análisis, como pesos, estos generalmente no son negativos, a menudo se escalan para caer entre cero y uno. 

Un grafo cuyas aristas están equipadas con pesos, se denomina grafo ponderado.

• is.weighted(g) [1] FALSE, Se retorna falso por no hallar una ponderación en el grafo.
• wg <- g
• E(wg)$weight<_runif(ecount(wg))
• is.weighted(wg) [1] TRUE Como se le dio un valor al atributo $𝑤𝑒𝑖𝑔ℎ𝑡 ya existe una ponderación, por eso da como resultado verdadero.

Los atributos de arista se pueden usar para equipar las aristas con propiedades que se usarán en llamadas a otras funciones de R, como la función de trazado.

Un grafo en sí mismo puede estar decorado con un atributo y es posible equipar objetos grafos con atributos en igraph.

• g$name<-Toy Graph"

3.2.    Usando marcos de datos

En R, un grafo y todos los atributos de vértice y arista pueden representarse utilizando dos marcos de datos, uno con información de vértice y otro de arista. 

• Marco de datos de vértice

1. La primera columna contiene los nombres de los vértices.
2. El resto contienen los valores de un atributo de vértice dado.

• Marco de datos de arista

1. Las 2 primeras columnas contienen una lista de aristas que definen el grafo.
2. Cada una de las otras columnas contiene los valores de un atributo de arista dado.

• library(sand)
• g.lazega<-graph.data.frame(elist.lazega,directed="FALSE", vertices=v.attr.lazega)
• g.lazega$<-Lazega Lawyers

Nuestro conjunto completo de información de red sobre estos

• vcount(g.lazega)
• 136

Para ver el listado de atributos de los vértices de un grafo

• list.vertex.attributes(g.lazega)
• [1] "name" "Seniority" "Status" "Gender"
• [5] "Office" "Years" "Age" "Practice"
• [9] "School"

4.    Hablando acerca de grafos

4.1.    Conceptos básicos de grafos

Un grafo no tiene aristas en las que ambos extremos se conecten a un solo vértice (bucles) ni pares de vértices con más de una arista entre ellos (aristas múltiples). Un objeto con cualquiera de estas propiedades se llama multígrafo, un grafo que no es un grafo múltiple se denomina grafo simple 

• is.simple(g)
• [1] TRUE, Retorna verdadero si el grafo es simple, sino será falso.
• mg<-g+edge(2,3), en $G$ ya existía una arista entre los vértices 2 y 3
• is.simple(mg) [1] FALSE

Verificar si un grafo es simple o no es un paso para realizar un análisis de red típico, muchos modelos y métodos asumen que el grafo de entrada es simple.

Tenga en cuenta que es sencillo, y de hecho no infrecuente en la práctica, transformar un grafo múltiple en un grafo ponderado, por ejemplo, convertir el multígrafo $mg$ un grafo ponderado da como resultado un grafo simple.

• E(mg)$weight <- 1, al grafo mg se le da una ponderación de 1.
• wg2 <- simplify(mg, Elimina posibles bucles.
• is.simple(wg2) [1] TRUE 
• Después de asignarse con otro nombre se confirma que un multígrafo puede convertirse en un grafo simple.

El grafo $wg2$ a pesar de ser simple comparado con el grafo $G$, que también es simple, varían en su ponderación, en la arista que conecta los vértices 2 y 3,el grafo $wg2$ tendrá una ponderación de 2, pero la del grafo $G$ será de $1$.

La noción más básica de conectividad es la de adyacencia. Se dice que dos vértices $u,v \in V$ son adyacentes si están unidos por una arista en $E$. Por ejemplo, los vecinos del vértice 5 en el grafo $G$.

• neighbors(g,5)

De manera similar, dos aristas $e_1,e_2 \in E$ son adyacentes si están unidas por un punto final común en $V$, el grado de un vértice $v$, digamos $d_v$, definido como el número de aristas incidentes en $v$.

• degree(g)

Para los dígrafos, el grado del vértice se reemplaza por el grado de entrada $(d_v^{in})$ y el grado de salida $(d_v^{out})$, que cuentan el número de aristas que apuntan hacia dentro y hacia fuera de un vértice, respectivamente.

• degree(dg,mode="in")
• degree(dg,mode="out")

También es útil poder discutir el concepto de movimiento en un grafo.

Un camino en el que los vértices inicial y final son iguales se llama circuito, un camino de al menos tres de longitud, para la cual los vértices inicial y final son los mismos, pero para la cual todos los demás vértices son distintos entre sí, se llama ciclo y los grafos que no contienen ciclos se denominan acíclicos. 

Se dice que un vértice $v$ en un grafo $G$ es accesible desde otro vértice $u$ sí existe un camino desde $u$ hasta $v$ y también se dice que el grafo $G$ está conectado si cada vértice es accesible desde todos los demás. 

Un subgrafo conectado de $G$ para el cual la adición de cualquier otro vértice restante en $V$ arruinaría la propiedad de conectividad.

• is.connected(g)

Por lo tanto, consta de un solo componente

• clusters(g)
• $membership [1] 1 1 1 1 1 1 1
• $csize [1] 7
• $no [1] 1

Un dígrafo $G$ está débilmente conectado si su grafo subyacente está conectado. Se llama fuertemente conectado si cada vértice 𝑣 es accesible desde cada 𝑢 mediante un camino dirigido. 

• is.connected(dg,mode="weak")
• is.connected(dg,mode="strong")

La distancia entre vértices en un grafo se define como la longitud de la ruta más corta entre los vértices (es infinito si no existe la ruta), esta distancia se conoce también como distancia geodésica, siendo "geodésico", nombre para las rutas más cortas, el valor de la distancia más larga en un grafo se llama diámetro del grafo.

• diameter(g, weights=NA)

4.2.    Tipos especiales de grafos

Hay una serie de familias de grafos, se los puede graficar mediante los comandos

 

1. g.full<-graph.full(7),Grafo completo
2. g.ring<-graph.ring(7),Grafo en forma de heptagono
3. g.tree<-graph.tree(7, children=2, mode="undirected"),,Grafo en forma de arbol
4. g.star<-graph.star(7, mode="undirected"),Grafo en forma de estrella

Árbol, es un grafo conectado sin ciclos: 

• La unión disjunta de tales grafos se llama bosque. 
• Los árboles son de fundamental importancia en el análisis de redes. 
• Sirven como una estructura de datos clave en el diseño eficiente de muchos algoritmos computacionales. 
• Un dígrafo cuyo grafo subyacente es un árbol se llama árbol dirigido. 
• Estos árboles tienen asociado un vértice especial llamado raíz.
• Un vértice que precede a otro en un camino desde la raíz se llama antepasado, mientras que un vértice que sigue a otro se llama descendiente.
• Los antepasados inmediatos se denominan padres y los descendientes inmediatos hijos. 
• Un vértice sin hijos se le llama hoja. 
• La distancia desde la raíz hasta la hoja más lejana se llama profundidad del árbol.
• Esta representación de un árbol se muestra en la figura 3

Estrella k es un caso especial de un árbol, que consta solo de una raíz y k hojas.

• Son útiles para conceptualizar un vértice y sus vecinos inmediatos, en la figura 4 se muestra un ejemplo de una estrella de 6.

Un DAG (grafo acíclico dirigido), es un grafo que está dirigido y que no tiene ciclos dirigidos, su grafo subyacente no es necesariamente un árbol, ya que reemplazar los arcos con aristas no dirigidas puede dejar un grafo que contiene ciclos.

• is.dag(dg)

Grafo bipartito, es tal que el conjunto de vértices $V$ puede dividirse en dos conjuntos disjuntos, y cada arista en tiene un punto final en $V1$ y el otro en $V2$, estos grafos se utilizan normalmente para representar redes de "miembros".

• g.bip<-graph.formula(actor1:actor2:actor3,movie1:movie2,
• actor1:actor2 - movie1, Primero se definen los grupos.
• actor2:actor3 - movie2), Después se definen las relaciones entre ambos grupos.

Cada uno de estos gráficos se denomina proyección sobre su subconjunto de vértices correspondiente.

• proj <- bipartite.projection(g.bip)
• str(proj[[1]]) [1] actor1--actor2 actor2--actor3
• str(proj[[2]]) [1] movie1--movie2

Dentro de la red de actores:

• Actor 2 es adyacente tanto a actor1 como a actor3. 
• El primer actor estaba en películas con cada uno de los últimos actores, 
• Estos últimos no estaban juntos en ninguna película, por lo tanto, no comparten una ventaja. 

Dentro de la red de películas: 

• Consiste en una sola arista definida entre movie1 y movie2.
• Ambas películas tenían actores en común.