Analiza sieciowa: wprowadzenie i przykłady zastosowania z R
Michał Bojanowski (ICM UW)
m.bojanowski@uw.edu.pl
Data Science Warsaw
10 listopada, 2015
Pytanie 1
Co sprawia, że ludzie kupują telefon komórkowy X?
- X jest najczęściej kupowany przez kobiety-singielki z dużych miast.
- X jest najczęściej kupowany przez osoby, których znajomi posiadają X.
- Ludzie kupują X ponieważ potrzebują telefon z dobrym aparatem. X posiada jeden z najlepszych aparatów na rynku.
Pytanie 2
W pewnym kraju A wirus HIV rozprzestrzenia się szybciej niż w kraju B. Dlaczego?
- W kraju B ludzie rzadziej uprawiają seks (średnia liczba partnerów jest niższa niż w A) więc jest mniej okazji do zarażenia wirusem.
- W kraju A, w odróżnieniu od B, popularne jest posiadanie kilku partnerów seksualnych jednocześnie.
- W kraju A częściej się używa prezerwatyw niż w B. Używanie prezerwatyw obniża ryzyko zarażenia HIV.
Co to jest analiza sieciowa?
Analiza sieciowa to metoda analizowania zbiorowości (np. ludzi lub organizacji) poprzez analizę relacji pomiędzy nimi składających się w złożone sieci. Celem jest poznanie procesów zachodzących w tej zbiorowości poprzez badanie struktury relacji pomiędzy nimi.
- W analizie danych przeważnie analizujemy obiekty i ich atrybuty.
| 1 |
0.7533110 |
1 |
| 2 |
2.0143547 |
0 |
| 3 |
-0.3551345 |
0 |
| 4 |
2.0281678 |
0 |
| 5 |
-2.2168745 |
0 |
- W analizie sieciowej analizujemy relacje pomiędzy obiektami (relacje i obiekty też mogą mieć atrybuty),
R & CRAN: Pakiety wykorzystujące sieci
Obecnie jest ok. 270 pakietów wykorzystujących dane sieciowe/grafowe.
Sieci i pakiet igraph
Pakiet igraph (Csardi & Nepusz, 2006) dostarcza klasę obiektów reprezentujących dane sieciowe oraz zestaw podstawowych algorytmów do analizy i wizualizacji.
Etapy analizy sieci z igraph:
- Dane np. w postaci
- macierzy sąsiedztwa: macierz \([a_{ij}]_{N \times N}\), w której \(a_{ij} = 1\) jeżeli istnieje relacja i -> j
- listy relacji: ramka danych z kolumnami
id_nadawca, id_odbiorca
- Stworzenie obiektu sieciowego
- Funkcje operujące na obiektach sieciowych
Przykład: kto kogo lubi w klasie
Dzieci:
## name female isei
## 1 1003 FALSE 25.71
## 2 1006 TRUE 14.64
## 3 1009 TRUE 28.48
## 4 1012 TRUE 25.23
## 5 1015 TRUE 21.24
Relacje:
## from to
## 1 1003 1018
## 2 1003 1051
## 3 1003 1072
## 4 1006 1009
## 5 1006 1042
Obiekt:
siec <- graph.data.frame(relacje, vertices = dzieci)
summary(siec)
## IGRAPH DN-- 26 88 --
## + attr: name (v/c), female (v/l), isei (v/n), question (e/c)
Wizualizacja
plot(siec, vertex.color=ifelse(V(siec)$female, "pink", "lightskyblue"),
vertex.label=NA, edge.arrow.size=0.5, edge.curved=0.2)
legend("topleft", title="Płeć", pt.bg=c("pink", "lightskyblue"), bty="n", pch=21,
legend=c("Dziewczynki", "Chłopcy") )
Wizualizacja: layout
Wizualizacje sieci to nie wykresy statystyczne
Gęstość, odwzajemnienie i stopień
- Gęstość to proporcja istniejących relacji w stosunku do liczby wszystkich możliwych
graph.density(siec)
## [1] 0.1353846
- Odwzajemnienie (reciprocity) to proprocja relacji odwzajemnionych
reciprocity(siec, mode="ratio")
## [1] 0.3333333
- Stopień (degree) to liczba relacji. Możemy liczyć oddzielnie relacje przychodzące (in-degree) i wychodzące (out-degree):
degree(siec)
## 1003 1006 1009 1012 1015 1018 1021 1024 1027 1030 1033 1036 1039 1042 1045
## 5 11 10 5 4 14 7 0 8 2 2 3 4 13 4
## 1048 1051 1054 1057 1060 1063 1066 1069 1072 1075 1078
## 9 15 7 8 5 6 6 5 6 6 11
degree(siec, mode="in")
## 1003 1006 1009 1012 1015 1018 1021 1024 1027 1030 1033 1036 1039 1042 1045
## 2 7 7 2 1 9 2 0 2 0 1 0 2 9 2
## 1048 1051 1054 1057 1060 1063 1066 1069 1072 1075 1078
## 4 10 2 6 1 2 2 2 3 2 8
Relacje przychodzące i wychodzące
Indeksowanie V() i E()
- W R m.in. macierze i ramki danych możemy indeksować za pomocą
[].
- W danych sieciowych chcemy móc indeksować
- węzły
- relacje
- odnajdywać relacje łączące określone węzły
- odnajdywać węzły połączone określonymi relacjami
W pakiecie igraph służą do tego funkcje E() i V().
Indeksowanie węzłów funkcją V()
V(g)[ i ]
g to obiekt “igraph”i wektor
Na przykład:
V(siec)$female
## [1] FALSE TRUE TRUE TRUE TRUE FALSE TRUE FALSE TRUE TRUE FALSE
## [12] FALSE FALSE FALSE FALSE FALSE FALSE FALSE TRUE FALSE TRUE TRUE
## [23] TRUE FALSE TRUE TRUE
V(siec)[female]$isei # ISEI dziewczynek
## [1] 14.64 28.48 25.23 21.24 21.24 25.95 25.71 51.50 24.98 24.93 24.93
## [12] 11.74 28.48
V(siec)[nei(2)]$isei # ISEI sąsiadów węzła 2
## [1] 28.48 21.24 25.95 25.71 54.54 51.50 24.98 28.48
W podobny sposób działa E()
Ścieżki
Ścieżka od węzła A do węzła B to sekwencja relacji które trzeba odwiedzić aby dojść od A do B taka, że:
- Nie odwiedzamy żadnego węzła więcej niż raz
- Podróżujemy zgodnie z kierunkiem relacji
Krótka ścieżka od A do B: najkrótsza możliwa ściezka od A do B.
Centralność
Miary centralności charakteryzują pozycję / znaczenie indywidualnego węzła w danej sieci. Na przykład:
- closeness centrality węzła A: na ile A ma daleko (w sensie krótkich ścieżek) do pozostałych węzłów
- betweenness centrality węzła A: proporcja wszystkich krótkich ścieżek, do których należy A. Na ile A zapośrednicza relacje pomiędzy innymi węzłami w sieci.
Spójność
Spójne składowe
Składowa silnie spójna: każdą parę węzłów możemy połączyć ścieżką
Inne zastosowania: współpraca między firmami
Inne zastosowania: współpraca wewnątrz firm
Inne zastosowania: prawo i sądownictwo
System Analizy Orzeczeń Sądowych (SAOS)
