Grafos

[Abundando en ¿Qué puede colgar de un árbol?] ¡Grafos!

Son los enteros del 1 al 35 ordenados de forma que dos consecutivos en la serie suman un cuadrado perfecto. Los he obtenido así: library(adagio) foo <- function(n){ desde <- 1:n hasta <- 1:n todos <- expand.grid(desde, hasta) todos <- todos[todos$Var1 < todos$Var2,] todos$sqrt <- sqrt(todos$Var1 + todos$Var2) todos <- todos[todos$sqrt == round(todos$sqrt),] todos$sqrt <- NULL vertices <- as.vector(t(todos)) hamiltonian(vertices) } foo(35) Notas: Esta entrada está inspirada en algo que he visto en Twitter (pero cuya referencia he olvidado guardar). Puedes probar con otros números, aunque no siempre existe un ciclo hamiltoniano.

Me vais a permitir que escriba una entrada sin mayores pretensiones, inspirada en y adaptada de aquí y que sirva solo de que para representar correlaciones entre variables podemos recurrir a los grafos como en library(qgraph) wine.quality <- read.csv("https://goo.gl/0Fz1S8", sep = ";") qgraph(cor(wine.quality), shape= "circle", posCol = "darkgreen", negCol= "darkred", layout = "groups", vsize=13) que pinta mostrando resumidamente cómo se relacionan entre sí determinadas características de los vinos y cómo en última instancia influyen en su calidad (qlt).

CartoDB (ahora Carto a secas) lo hizo con mapas. Onodo lo quiere hacer con grafos. Onodo acaba de salir a la luz de mano de Civio y quiere convertirse en una herramienta para crear muy fácilmente visualizaciones interactivas de redes y nodos, y poder contar historias con ellas. Viene a ser un Gephi digamos que al alcance de (casi) todos, sin el aparataje matemático y orientado a la publicación en la web. ...

Tengo un grafo, g cuyas aristas pueden ser cualquier cosa susceptible de contaminarse. Me pregunto si la contaminación puede contagiarse a través del grafo. Es decir, si A y B están unidos por una arista y A está contaminado, la probabilidad de que B también lo esté es superior a la normal. Se me ocurre probar esa hipótesis así: library(igraph) # mi grafo g <- erdos.renyi.game(10000, p.or.m = 0.001, type="gnp") min.mean.dist <- function(n){ # contaminación al azar contaminados <- sample(V(g), n) # distancias entre aristas contaminadas res <- shortest.paths(g, v = contaminados, to = contaminados) diag(res) <- Inf # distancia al contaminado más próximo min.dist <- apply(res, 1, min, na.rm = T) # y su media mean(min.dist) } # histograma bajo la hipótesis nula res <- replicate(100, min.mean.dist(100)) El resto son detalles que el lector atento sabrá completar por su cuenta.

Dando vueltas (infructuosas) al asunto de los cartogramas he dado con un subproducto con el que, por hoy, me conformo: crear un grafo a partir de relaciones de vecindad entre polígonos. La magia, obra de [spdep::poly2nb](http://www.inside-r.org/packages/cran/spdep/docs/poly2nb); el código, library(maptools) library(spdep) library(igraph) # fichero descargado del INE aragon <- readShapePoly("ccaa00c02.shp") plot(aragon) aragon.nb <- poly2nb(aragon) # vértices vertices <- aragon@data vertices$id <- 1:nrow(aragon@data) vertices <- vertices[, c("id", setdiff(colnames(vertices), "id"))] # coordenadas aproximadas de los vértices my.layout.orig <- do.call(rbind, lapply(vertices$id, function(i) aragon@polygons[[i]]@Polygons[[1]]@labpt)) # aristas aristas <- do.call(rbind, lapply(1:length(aragon.nb), function(x) data.frame(from = x, to = aragon.nb[[x]]))) aristas <- aristas[aristas$from < aristas$to,] aristas <- aristas[aristas$from %in% vertices$id,] aristas <- aristas[aristas$to %in% vertices$id,] # grafo g <- graph.data.frame(aristas, directed = FALSE, vertices) plot(g, layout = my.layout.orig, vertex.label = NA, vertex.size = 0.1)

Uno de mis últimos pet projects tiene que ver con el análisis de las componentes conexas de unos grafos muy grandes. Como aquí pero con datos de un tamaño muchos órdenes de magnitud mayores. Usando Spark, claro. Y ya que lo cito, aprovecho la ocasión para regalar un consejo a mis lectores más jóvenes: no esperéis a los cuarenta para aprender Scala y Spark. Voy a limitarme a copiar el código para referencia mía y de otros. Creo que se autoexplica: ...

Tú eres un conjunto de cardinalidad 1. Tú y tus padres conformáis un conjunto de cardinalidad 3. Añade a tus abuelos y tendrás un conjunto de cardinalidad 7. Aplica la inducción y tendrás conjuntos de cardinalidad $2^n -1$. Esto viene a cuenta de lo que me contó un colega el otro día: que en Corea tiene un libro en el que aparecen sus ancestros desde 54 generaciones atrás. Yo le pregunté cómo almacenaba esos 18014398509481983 nombres. A razón de 20 caracteres por nombre, eso son unos 350 millones de GB. ...

Ayer dejamos abierto el problema de la inferencia en grafos. La idea fundamental es la de suponer que un grafo determinado no es tanto un grafo en sí como una realización de un proceso aleatorio de generación de aristas entre un determinado número de nodos. El planteamiento es análogo al que se hace con las series temporales: no es tan importante la serie en sí como el hecho de que pueda probarse que obedece a un modelo autorregresivo, ARIMA, etc. ...

Sea un colegio y $a_i$ sus alumnos. Sea $y_{ij} \in {0,1}$ el indicador de que el alumno i es amigo del alumno j. Con eso tenemos montado un grafo (o, si se prefiere, una red social). Muchos análisis que se hacen sobre este tipo de redes son meramente descriptivos pero, ¿es posible la inferencia sobre este tipo de conjunto de datos? Por ejemplo, en el grafo que describo más arriba, cabría preguntarse si hay reciprocidad, es decir, si $P( y_{ij} = 1 | y_{ji} = 1 )$ es mucho mayor que $P( y_{ij} = 1 | y_{ji} = 0)$. O dicho de otro modo, si el que Juan sea amigo de Pedro incrementa notablemente la probabilidad de que Pedro también se considere amigo de Juan. ...