2-EFM-155 Analýza sociálnych sietí 2020/2021
Domáca úloha 2: Hľadanie komunít v sieťach
Pokyny:
- Úlohu je možné vypracovať samostatne alebo v dvojiciach.
- Každý, resp. každá dvojica pracuje samostatne, otázky treba adresovať mne.
Odovzdávanie:
- mailom na adresu beata.ulohy@gmail.com, predmet: siete 2021 – DÚ 2 – meno/mená
- odovzdáva sa kód v R-ku a spísané výsledky v pdf (alebo všetko spolu v html výstupe z R markdown-u)
- termín: 28. apríl 2021 (teda polnoc zo stredy 28. 4. na štvrtok 29. 4)
Zadanie:
Videli sme, že existujú rôzne algoritmy na hľadanie komunít v sociálnych sieťach, niektoré sú deterministické, iné sú náhodné. Medzi tie náhodné patrí aj label propagtion algoritmus, o ktorom sme tiež hovorili.
Z náhodnosti vyplýva, že ak ho spustíme niekoľkokrát pre tú istú sieť, nemusíme dostať vždy ten istý výsledok. Vyskúšame si to na známej sieti karate klubu.
library(igraph)
library(igraphdata)
data(karate)
set.seed(1)
lay <- layout_nicely(karate)
set.seed(12)
com <- cluster_label_prop(karate)
plot(com, karate, layout = lay)
Niekoľkokrát zopakujeme:
com <- cluster_label_prop(karate)
plot(com, karate, layout = lay)
com <- cluster_label_prop(karate)
plot(com, karate, layout = lay)
com <- cluster_label_prop(karate)
plot(com, karate, layout = lay)
Vidíme, že jedno rozdelenie do komunít sa nám zopakovalo dvakrát, ďalšie dve sa vyskytli len raz a v jednom prípade sme mali aj iný počet komunít ako v ostatných.
Zadanie 1 (2 body). Spravte štatistiku toho, koľko komunít vznikne, keď algoritmus zbehneme viackrát (napríklad 1000 alebo iný dostatočne veľký počet)
Teraz nás bude zaujímať, ktoré vrcholy sa dostali do spoločného zhluku, pomocou čoho potom budeme schopní analyzovať, koľkokrát sa v simuláciách dané vrcholy nachádzali v tej istej komunite.
Vytvoríme maticu A, ktorej prvok A[i,j] bude označovať, či sa vrcholy i a j nachádzajú v tej istej komunite. To dosiahneme porovnaním com$membership[i] == com$membership[j] (vo vektore com je aktuálne posledný výsledok zhlukovania), efektívne je tu použiť funkciu outer namiesto dvojitého for cyklu.
A <- outer(com$membership, com$membership, FUN = "==") # TRUE/FALSE
A <- outer(com$membership, com$membership, FUN = "==") + 0 # 1/0
rownames(A) <- V(karate)$name
colnames(A) <- V(karate)$nameKvôli veľkosti matice si zobrazíme len jej časť:
A[1:9, 1:9] ## Mr Hi Actor 2 Actor 3 Actor 4 Actor 5 Actor 6 Actor 7 Actor 8 Actor 9
## Mr Hi 1 1 1 1 0 0 0 1 0
## Actor 2 1 1 1 1 0 0 0 1 0
## Actor 3 1 1 1 1 0 0 0 1 0
## Actor 4 1 1 1 1 0 0 0 1 0
## Actor 5 0 0 0 0 1 1 1 0 0
## Actor 6 0 0 0 0 1 1 1 0 0
## Actor 7 0 0 0 0 1 1 1 0 0
## Actor 8 1 1 1 1 0 0 0 1 0
## Actor 9 0 0 0 0 0 0 0 0 1Zadanie 2 (3 body). Spočítajte, koľkokrát sa v týchto štyroch zbehnutiach algoritmu (resp. v štyroch vašich zbehnutiach, môžete si nastaviť iný seed) jednotlivé vrcholy dostali do rovnakej komunity.
Pre horeuvedené zhlukovania vrcholov:
A4[1:9, 1:9]## Mr Hi Actor 2 Actor 3 Actor 4 Actor 5 Actor 6 Actor 7 Actor 8 Actor 9
## Mr Hi 4 4 4 4 1 0 0 4 0
## Actor 2 4 4 4 4 1 0 0 4 0
## Actor 3 4 4 4 4 1 0 0 4 0
## Actor 4 4 4 4 4 1 0 0 4 0
## Actor 5 1 1 1 1 4 2 2 1 0
## Actor 6 0 0 0 0 2 4 4 0 0
## Actor 7 0 0 0 0 2 4 4 0 0
## Actor 8 4 4 4 4 1 0 0 4 0
## Actor 9 0 0 0 0 0 0 0 0 4Ak zopakujeme dostatočne veľa krát, z výsledkov sa dá robiť štastistika. Ukážka matice počtu zhôd pre 1000 zbehnutí:
A1000[1:9, 1:9]## Mr Hi Actor 2 Actor 3 Actor 4 Actor 5 Actor 6 Actor 7 Actor 8 Actor 9
## Mr Hi 1000 994 994 994 379 51 51 994 45
## Actor 2 994 1000 1000 1000 373 45 45 1000 45
## Actor 3 994 1000 1000 1000 373 45 45 1000 45
## Actor 4 994 1000 1000 1000 373 45 45 1000 45
## Actor 5 379 373 373 373 1000 622 622 373 13
## Actor 6 51 45 45 45 622 1000 1000 45 1
## Actor 7 51 45 45 45 622 1000 1000 45 1
## Actor 8 994 1000 1000 1000 373 45 45 1000 45
## Actor 9 45 45 45 45 13 1 1 45 1000Zadanie 3 (5 bodov). Spravte takúto simuláciu a nájdite spôsob, ako z danej matice vyťažiť nejakú informáciu o komunitách v sieti a o správaní sa tohto algoritmu. Interpretujte získané výsledky.