IV124 Komplexní sítě
Jan Fousek, Eva Hladká
Fakulta informatiky, Masarykova univerzita
17. května 2018
Procesy na sítích: difúze
Podobné principy v různých kontextech:
• technické sítě: kaskádové selhání
• biologické sítě: epidemie
• sociální sítě: formování názoru, šíření informace Dnes: modely těchto procesů.
2 of 14
Difúze: základní pojmy a principy
Složky modelu
• předmět šíření: nákaza, informace, volba, ...
• moment rozšíření: změna volby, infekce, selhání, ...
• výsledek: nakažení, rozhodnutí, vyřazené uzly, ...
Časovou doménu uvažujeme diskréní- model se vyvíjí v iterativních krocích.
3 of 14
Kaskáda na síti
Konkrétní běh modelu na síti tvoří orientovaný graf-kaskádu.
i
ij-eskovec CS224W
Formy difuze/nákazy
Jednoduché šírení:
• každý uzel nakazí okolní s určitou pravděpodobností v každém kroku
Komplexní šírení
• k rozšírení dojde pouze pokud určitá čast sousedních uzluje „nakažená"
5 of 14
Koordinační hra na síti
Zadání:
• volba mezi A a B (např. VHS vs. BetaMax)
Odměny pro sousední uzly u s v:
• oba A: odměna a > 0
• oba B: odměna b > 0
• neshoda: bez odměny
Každý uzel hraje sám za sebe.
6 of 14
Práh pro změnu rozhodnutí
7 of 14
Práh pro změnu rozhodnutí
A je lepší volbou, pokud
pda > (1 - p)db
Tedy:
P>
a + b
= q
8 of 14
Koordinační hra - vlastnosti
Šírení je monotonické (uzly nemění rozhodnutí zpět).
Rovnovážne stavy:
• všichni zvolí A
• všichni zvolí B
• neúplná kaskáda
Spuštění kaskády záleží na topologii sítě, počátečních podmínkách a hodnotě q.
9 of 14
Spustení kaskády
Binární strom:
-i
• kaskáda nastane pro práh rozhodnuti q < k Mřížka:
-i
• kaskáda nastane pro práh rozhodnutí q < j
Obecně - kaskádová kapacita (nekonečného) grafu G:
• největší q takové, pro které konečná množina 5 spustí kaskádu.
• lze ukázat, že největší možná kapacita je \
10 of 14
Kaskády vs. klastry
Klastry představují pro kaskády překážku
• hustá vnitřní konektivita
• malé množství hran do zbytku grafu
Def: hustota p klastru C C G:
• každý uzel u G C má alespoň podíl p hran v C
Kaskády vs. hustota:
• do klastrů s p > (1 — q) se kaskáda nemůže rozšířit
• naopak: pokud se kaskáda zastaví, v grafu je klastr
sp>{l-q)
11 of 14
Kaskády vs. slabé vazby
Připomenutí: slabé vazby jsou mosty mezi komunitami Role při kaskádě:
• klíčové pro šíření informace (např. povědomí o inovaci)
• neprostupné projevy s vyšším prahem (vlastní přijetí inovace)
• např. rychlá globální dynamika sdílení na soc. sítích vs. pomalá a lokální dynamika politické mobilizace
12 of 14
Kozsireni
Obojetné (bilingvní) uzly:
• uzel může zvolit stav AB
• odměna AB-A: a
• odměna AB-B: b
• odměna AB-AB: max(a, b)
• uzly volící AB platí navíc fixní cenu c
Heterogenní prahy:
• umožňuje zahrnout rozdíly v ovlivnitelnosti
13 of 14
Netlogo ukázka
14 of 14