Introducción

El grafo out.ego-twitter almacena información acerca de usuarios de Twitter. En concreto, se trata de un grafo dirigido no ponderado donde cada vértice representa a un usuario, mientras que una arista (v, u) indica que el usuario v sigue al usuario u. El objetivo de esta hoja de ejercicios es analizar la estructura de este grafo y extraer diferentes características estructurales del mismo.

library(igraph)
library(magrittr)
library(knitr)
library(dplyr)
  1. Carga el grafo en memoria. Las funciones read_table y graph.data.frame facilitan la tarea de cargar grafos en un formato aceptado por igraph. Busca en la documentación de igraph y R su descripción y uso.
g <- read.table('./out.ego-twitter', sep=' ') %>%
                graph_from_data_frame(directed=TRUE)
  1. Muestra el grafo por pantalla e indica qué tipo de grafo es. ¿Es de ayuda la visualización del grafo para identificar su tipo?
plot(g, layout=layout.kamada.kawai, edge.arrow.size=0.5, edge.arrow.width=0.5, vertex.size=0.5, vertex.label.cex=0.5, vertex.label=NA) 

cat('¿Es el grafo conexo?: ',is.connected(g))
## ¿Es el grafo conexo?:  FALSE
cat('¿Es el grafo dirigido?: ', is.directed(g))
## ¿Es el grafo dirigido?:  TRUE
cat('¿Es el grafo ponderado?: ', is.weighted(g))
## ¿Es el grafo ponderado?:  FALSE
cat('¿Es el grafo bipartido?: ', is.bipartite(g))
## ¿Es el grafo bipartido?:  FALSE

La información que nos muestra la salida sobre el grafo es la siguiente: se trata de un grafo que no es conexo, sí es dirigido, no es un grafo ponderado ni tampoco bipartido.

Mostrar el grafo por pantalla no ha servido de mucho ya que el número de vértices es tal que no permite observar con claridad las características del grafo.

  1. ¿Qué representa, en este grafo, el grado de un vértice? Analiza y comenta la distribución del grado de este grafo.

El grado de un vértice representa el número de seguidores (followers) y perfiles que sigue (follows) de un usuario.

Al tratarse de un grafo dirigido, es interesante ver el grado de entrada (seguidores) y de salida (seguidos) de cada nodo (usuario).

g.degree.in <- degree(g, mode='in')

hist(g.degree.in, labels=TRUE, ylim=c(0, 24000))

En este caso estamos viendo la frecuencia de seguidores. Se puede apreciar que hay muchos usuarios con 5 o menos seguidores en comparación con el resto.

g.degree.out <- degree(g, mode='out')

hist(g.degree.out, labels=TRUE, ylim=c(0, 24000))

En este caso estamos viendo la frecuencia de perfiles seguidos. Se puede apreciar que hay muchos usuarios que siguen a 20 o menos perfiles en comparación con el resto.

  1. Si seleccionamos la comunidad formada por los usuarios 190, 191, 192, 193, 194 y 13167, ¿podemos considerar que los usuarios que la forman están fuertemente conectados? ¿qué tipo de conexión tienen?
community <- induced_subgraph(g, c('190', '191', '192', '193', '193', '194', '13167'))

plot(community)

cat('¿Es el grafo fuertemente conexo?: ', is_connected(community, mode='strong'))
## ¿Es el grafo fuertemente conexo?:  FALSE
cat('¿Es el grafo débilmente conexo?: ', is_connected(community, mode='weak'))
## ¿Es el grafo débilmente conexo?:  TRUE
cat('Densidad del grafo: ', graph.density(g)*100, '%')
## Densidad del grafo:  0.006060972 %
cat('Reciprocidad del grafo: ', reciprocity(g, mode="default")*100, '%')
## Reciprocidad del grafo:  1.631371 %

La comunidad no forma un grafo fuertemente conexo, por lo que no es posible visitar todos los perfiles a partir del conjunto de perfiles que sigue (follows) cada usuario. No están fuertemente conectados los miembros de la comunidad.

Sin embargo, sí tienen una conexión débil: Es decir, si no se tuviera en cuenta el sentido de las aristas, se podrían visitar todos los perfiles a partir del conjunto de perfiles que sigue (follows) cada usuario.

Además no es prácticamente nada denso, y como se puede apreciar la reciprocidad tampoco es alta (a penas del 1.63%).

  1. ¿Qué usuario tiene más seguidores? ¿Qué usuario sigue a un mayor número de usuarios?
#Aclaración: se podría usar la función max pero utilizo sort a propósito para ver también el identificador

cat('Usuario con más seguidores:')
## Usuario con más seguidores:
sort(g.degree.in, decreasing=TRUE)[1]
## 36 
## 57
cat('Usuario que más perfiles sigue:')
## Usuario que más perfiles sigue:
sort(g.degree.out, decreasing=TRUE)[1]
## 11824 
##   238

El usuario con más seguidores es el 36, con 57 followers.

El usuario que más perfiles sigue es el 11824, con 238 follows.

  1. Indica quiénes son los seguidores del usuario 1305.
in_node <- '1305'

in_neighbors <- neighbors(g, in_node, mode='in')

in_neighbors
## + 4/23370 vertices, named:
## [1] 1301  7331  13200 16843
in_neighbors %>%
  as_ids(.) %>%
  c(., in_node) %>%
  induced_subgraph(g, .) %>%
  plot(.)

Los seguidores del usuario 1305 son los usuarios 1301, 7331, 13200 y 16843.

  1. Indica a quién sigue el usuario 1373.
out_node <- '1373'

out_neighbors <- neighbors(g, out_node, mode='out')

cat('Lista de perfiles que sigue el usuario 1373:')
## Lista de perfiles que sigue el usuario 1373:
out_neighbors
## + 57/23370 vertices, named:
##  [1] 537   2050  8968  5289  16332 501   920   1872  1880  2048  2051 
## [12] 2055  2089  2092  3687  3816  6279  6280  6281  6291  6292  6294 
## [23] 6297  6303  6304  6305  6307  6312  6319  6320  6321  6322  6325 
## [34] 10635 16309 16310 16311 16312 16313 16314 16315 16316 16317 16318
## [45] 16319 16320 16321 16322 16323 16324 16325 16326 16327 16328 16329
## [56] 16330 16331
out_neighbors %>%
  as_ids(.) %>%
  c(., out_node) %>%
  induced_subgraph(g, .) %>%
  plot(., edge.arrow.size=0.5, edge.arrow.width=0.5)

Los seguidores del usuario 1373 son los que se indican en la lista anterior.

  1. ¿Cuál es el ratio seguidores/siguiendo del usuario 13815? ¿se puede considerar que es un usuario influyente?
ex_8_node <- '13815'

followers <- length(neighbors(g, ex_8_node, mode='in'))
follows <- length(neighbors(g, ex_8_node, mode='out'))

cat('Followers: ', followers)
## Followers:  1
cat('Follows: ', follows)
## Follows:  9
followers/follows
## [1] 0.1111111
#sort(authority_score(g, scale = TRUE)$vector, decreasing = TRUE)[ex_8_node]
authority_score(g, scale = TRUE)$vector[ex_8_node]
##       13815 
## 0.003540245

El ratio es de 1 seguidor por 9 perfiles seguidos. No parece que sea un usuario influyente porque sigue a mucha más gente de la que a él le sigue.

Además, el authority score del usuario es muy bajo incluso comparándolo con el score de otros perfiles (ejecutar línea comentada).

  1. ¿Podemos decir que el grafo representa una gran comunidad? ¿O existen comunidades aisladas? Indica la comunidad o comunidades que encuentras en el grafo.
count_components(g, mode = 'weak')
## [1] 72
clusters_obj <- clusters(g)

kable(
  data.frame(size=clusters_obj$csize, cluster_id=c(1:clusters_obj$no)) %>% 
    arrange(desc(size))
  )
size cluster_id
22322 1
74 59
72 55
40 37
36 8
35 5
34 12
33 56
31 66
30 25
30 28
28 18
28 44
28 52
27 65
26 33
24 38
24 63
22 42
21 71
18 14
17 26
17 29
15 22
15 53
15 54
14 27
14 48
14 57
13 32
12 15
12 23
12 36
11 9
11 13
10 21
10 31
10 35
10 49
10 62
9 50
9 51
8 19
8 41
7 4
7 11
7 45
6 2
6 6
6 61
6 68
6 69
5 16
5 46
5 58
4 24
4 34
4 64
3 20
3 40
3 47
3 60
3 67
2 3
2 7
2 10
2 17
2 30
2 39
2 43
2 70
2 72

Podemos ver el número de comunidades que hay calculando el número de componentes conexas débiles (sin tener en cuenta las direcciones de las aristas) que existen.

Si los conjuntos de vértices y aristas formasen una única componente conexa, hablaríamos de una sóla comunidad, pero en este caso no es así, ya que encontramos 72 comunidades (72 componentes conexas).

En la tabla anterior se puede apreciar el tamaño de cada clúster con su identificador, ordenados por tamaño. Llama la atención que hay un grupo mucho más grande que los demás: 22.322 usuarios frente al siguiente más grande de 74 usuarios. Sería interesante ver si se trata de una componente gigante, ya que en ese caso deberíamos centrar nuestro estudio en el clúster 1 (aquel que tiene 22.322 usuarios).

  1. Si tenemos en cuenta la comunidad de 35 usuarios del grafo, ¿cuál es el usuario menos importante? ¿Por qué?

La comunidad con 35 usuarios es la comunidad con id 5.

community_5 <- induced.subgraph(g, which(clusters_obj$membership == which(clusters_obj$csize == 35)))

plot(community_5)

cat('Importancia en cuanto a popularidad')
## Importancia en cuanto a popularidad
degree(community_5, mode='in')
## 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 
##    0    1    1    1    1    1    1    1    1    1    1    1    1    1    1 
## 1460 1461 1462 1463 1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 
##    1    1    1    1    1    1    1    1    1    1    1    1    1    1    1 
## 1475 1476 1477 1478 1479 
##    1    1    1    1    1
cat('Importancia en cuanto a la estructura de la comunidad')
## Importancia en cuanto a la estructura de la comunidad
closeness(community_5)
##         1445         1446         1447         1448         1449 
## 0.0294117647 0.0008403361 0.0008403361 0.0008403361 0.0008403361 
##         1450         1451         1452         1453         1454 
## 0.0008403361 0.0008403361 0.0008403361 0.0008403361 0.0008403361 
##         1455         1456         1457         1458         1459 
## 0.0008403361 0.0008403361 0.0008403361 0.0008403361 0.0008403361 
##         1460         1461         1462         1463         1464 
## 0.0008403361 0.0008403361 0.0008403361 0.0008403361 0.0008403361 
##         1465         1466         1467         1468         1469 
## 0.0008403361 0.0008403361 0.0008403361 0.0008403361 0.0008403361 
##         1470         1471         1472         1473         1474 
## 0.0008403361 0.0008403361 0.0008403361 0.0008403361 0.0008403361 
##         1475         1476         1477         1478         1479 
## 0.0008403361 0.0008403361 0.0008403361 0.0008403361 0.0008403361

Depende de lo que uno entienda por importancia: Si entendemos por importancia popularidad, el usuario menos importantes es el 1445, ya que mientras el resto tienen un seguidor (el usuario 1445), él no tiene ninguno. Sin embargo, el usuario 1445 es el más importante en el sentido de que gracias a él la comunidad existe.

Por el gráfico podríamos decir que es una comunidad muy cerrada: hay un único usuario que consume los tweets del resto de usuarios y además este usuario no tiene ningún seguidor.

  1. Si ahora analizamos la comunidad más grande del grafo
  1. ¿Cuál es el vértice más cercano al resto?
  2. ¿Qué vértice es el que controla un mayor flujo de información?
biggest_community <- induced.subgraph(g, which(clusters_obj$membership == which.max(clusters_obj$csize)))

head(sort(closeness(biggest_community), decreasing=TRUE), col.names=c('Usuario y closeness centrality'))
##         7045         8598        16618        14957        14954 
## 2.348708e-09 2.328648e-09 2.321799e-09 2.320979e-09 2.320973e-09 
##        14947 
## 2.320973e-09
head(sort(betweenness(biggest_community), decreasing=TRUE), col.names=c('Usuario y betweeness centrality'))
##     1368     2501     3266     3211     2488    15100 
## 61233.13 56850.05 50432.01 49911.58 45408.60 41146.43

Para calcular el vértice maś cercano al resto, usamos la medida closeness centrality. En este caso, el usuario más cercano al resto es el 7045.

Para calcular el vértice que controla el mayor flujo de información, usamos la medida betweenes centrality. En este caso, el usuario que controla el mayor flujo de información es el 1368.