useR, grafy i rekomendacje filmów

Minął już ponad tydzień od (fantastycznie zorganizowanej) konferencji useR 2015. Dopiero teraz znalazłem trochę czasu by zebrać garść wrażeń. Przegląd wybranych wystąpień z krótkimi komentarzami znaleźć można w agregacie blogów rbloggers. Ograniczę się więc wrażenia do kilku tematów, ale napiszę o nich ciut więcej. Dziś będzie o tutorialu ,,Statistical Analysis of Network Data’’, który poprowadził Gábor Csárdi (Harvard). Link do materiałów: http://igraph.github.io/netuser15/user-2015.html.

Tutorial w znakomitej większości był poświęcony bibliotece igraph (http://igraph.org/) do której dostępne są łączniki z poziomu R i Pythona. Łącznik dla R to pakiet o nazwie igraph. Zgodnie z nazwą tutoriala nacisk położono na analizę danych sieciowych, ale nie zabrakło przykładów wizualizacji grafów. Zarówno statycznych, zaimplementowanych w igraph jak i dynamicznych zaimplementowanych w pakiecie networkD3 (skądinąd autorstwa Christopher Gandrud & JJ Allaire z RStudio). Obie biblioteki są przedstawione w świetnym wprowadzenie do wizualizacji sieci http://kateto.net/network-visualization autorstwa Katherine Ognyanova.

Poniżej przedstawię wybrane funkcje z tego pakietu, ale zanim to zrobię małe wprowadzenie do danych, które użyjemy.

Niedawno pisałem o studenckich projektach systemu rekomendującego filmy. Używając pakietu networkD3 można sieci podobieństwa pomiędzy filmami ciekawie wizualizować, zobacz prototyp: tutaj lub tutaj lub poniżej.

Wracamy do tutoriala.

Pakiet igraph poza wizualizacją pozwala na (względnie) łatwe operacje na grafach, takie jak stworzenie grafu, dodanie/usunięcie wierzchołków, krawędzi, konwersje pomiędzy różnymi reprezentacjami grafu (macierz sąsiedztwa / reprezentacja listowa). Pracować można na grafach skierowanych i nie skierowanych, z wagami na krawędzie lub bez wag, z prostymi grafami lub multi-grafami. Do operacji na wierzchołkach i krawędziach można wykorzystać przeciążone operatory [ i [[ oraz funkcje E() i V() (odpowiednio, do operacji na krawędziach / wierzchołkach).

Przykłady zamieszczone w tutorialu dotyczą połączeń pomiędzy lotniskami w stanach zjednoczonych, a więc nudy na pudy. Pobierzmy dane o podobieństwach pomiędzy filmami, zbudujmy z nich graf oraz pokażmy kilka przykładowych operacji.

# aby pobrać dane potrzebujesz najnowszej wersji pakietu archivist
library(archivist)
graf <- aread("pbiecek/graphGallery/2701ac7")
 
# powyższe dane to dwukolumnowy opis sąsiedztwa
# tworzymy z niej graf nieskierowany
library(igraph)
igraf <- graph_from_edgelist(graf, directed = FALSE)
igraf <- simplify(igraf)

Wierzchołki możemy wybierać nie tylko przez nazwy czy indeksy, ale również przez ich właściwości, np. sąsiedztwo z określonym wierzchołkiem, czy stopień w sieci.

Jak sprawdzić co sąsiaduje z filmem 'Lego: Przygoda’? Które wierzchołki mają więcej niż 16 krawędzi?

# operator [[ wyłapuje wierzchołki
igraf[["Lego: Przygoda"]]
## $`Lego: Przygoda`
## + 9/1992 vertices, named:
## [1] 21 Jump Street                    22 Jump Street                   
## [3] Klopsiki i inne zjawiska pogodowe Kochankowie z Ksiezyca           
## [5] Simpsonowie: Wersja kinowa        Uniwersytet Potworny             
## [7] Bracie, gdzie jestes?             Jak wytresowac smoka 2           
## [9] Zaplatani  
 
# ale można też odwołać się do nich przez funkcję V
V(igraf)[degree(igraf) > 16]
## + 7/1992 vertices, named:
## [1] 28 dni                       Poznasz przystojnego bruneta
## [3] Single od dziecka            Cos nowego                  
## [5] Dobry rok                    Chlopiec z latawcem         
## [7] Zakochani w Rzymie

Poza podstawowymi operacjami na grafach, dostępne są również funkcje analityczne, takie jak funkcje do wyznaczania najkrótszej ścieżki, macierzy odległości, rozmaite funkcje wyznaczające centralność wierzchołków.

Jaka najkrótsza ścieżka łączy Lego: Przygoda i Whiplash?

# najkrótszą ścieżkę wyznacza funkcja shortest_paths
sp <- shortest_paths(igraf, "Lego: Przygoda", "Whiplash")
sp$vpath[[1]]
## + 5/1992 vertices, named:
## [1] Lego: Przygoda         Kochankowie z Ksiezyca 
## [3] 3:10 do Yumy           Spacer po linie        
## [5] Whiplash

Narysujmy ten graf z zaznaczoną ścieżką. Aby określić parametry rysowanego grafu wystarczy modyfikować właściwości takie jak color czy size.

# krawędzie na szaro, najkrótsza ścieżka na czerwono
E(igraf)$color = 'grey'
E(igraf, path=sp$vpath[[1]])$color = 'red'
 
# wierzchołki małe, te na najkrótszej ścieżce na czerwono i powiększone
V(igraf)$size = 1
V(igraf)[sp$vpath[[1]]]$size = 5
V(igraf)[sp$vpath[[1]]]$color = 'red'
 
# rysujemy
plot(igraf, vertex.label=NA)

Dla dużych grafów przydatne mogą być funkcje służące do grupowania wierzchołków (czyli tzw. clustering). Mając wyznaczone klastry możemy pracować na podsieciach zawierających tylko wierzchołki z danego klastra jak też pracować na meta-sieci w której wierzchołki są klastrami oryginalnej sieci.

Zróbmy proste klastrowanie i zaznaczmy je na grafie.

# to tylko pokaz możliwości, więc bierzemy pierwszą lepszą funkcję z półki 
res <- cluster_fast_greedy(igraf)
 
# co to za grupowanie?
res
## IGRAPH clustering fast greedy, groups: 7, mod: 0.64
## + groups:
##   $`1`
##     [1] "G.I. Joe: Odwet"                                  
##     [2] "Akwamaryna"                                       
##     [3] "Jak upolowac faceta"                              
##     [4] "Niebianska plaza"                                 
##     [5] "Szefowie wrogowie"   
 
# i rysujemy
plot(res, igraf, vertex.label=NA, vertex.size=2)

Nic nie widać 😉

Tak zazwyczaj jest gdy klastruje się przy domyślnych ustawieniach.

Mam nadzieję, że te kilka przykładowych instrukcji pokazuje jak prosto można pracować z grafami. Więcej funkcji znaleźć można w dołączonych materiałach lub w dokumentacji. Dane o filmach dotyczą podzbioru 2000 filmów, niedługo będzie ich więcej będzie można pobawić się z większym podzbiorem i tworzyć inne ciekawe sieci.