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 $latex 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 $latex a_i$ sus alumnos. Sea $latex 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 $latex P( y_{ij} = 1 | y_{ji} = 1 )$ es mucho mayor que $latex 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.

Una de las principales objeciones que se le pueden hacer a mi entrada de ayer es que puede estar confundiendo la causa con efecto: puede que parte de la radialidad de la red que obtuve tenga que ver con el tamaño desproporcionado de Madrid que, a su vez, podría haber sido causado por la radialidad de la red tradicional de las comunicaciones españolas.

Así que enviemos una partida de pescado en malas condiciones a Mercamadrid, convidemos a toda la provincia, veámosla fenecer víctima de contumaces diarreas y rehagamos la simulación suponiendo que