IV124 Komplexní sítě
Eva Výtvarová, Jan Fousek, Eva Hladká
Fakulta informatiky, Masarykova univerzita
25. dubna 2019
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ů.
2of 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.
3of 14
Kaskáda na síti
Konkrétní běh modelu na síti tvoří orientovaný graf - kaskádu.
^eskovec CS224W
Formy difuze/nákazy
Jednoduché šíření:
• každý uzel nakazí okolní s určitou pravděpodobností v každém kroku
Komplexní šíření
• k rozšíření dojde pouze pokud určitá čast sousedních uzlů je „nakažená"
5of 14
Koordinační hra na síti
Zadání:
• volba mezi A a B (např. VHS vs. BetaMax, iPhone vs. Samsung)
Odměny pro sousední uzly u a 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.
6of 14
Práh pro změnu rozhodnutí
Práh pro změnu rozhodnutí
A je lepší volbou, pokud
pda > (1 - p)db
Tedy:
b
P >-z = Q
a + b
8of 14
Koordinační hra - vlastnosti
Síření je monotonické (uzly nemění rozhodnutí zpět).
Rovnovážné 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.
Spuštění kaskády
Binární strom:
• kaskáda nastane pro práh rozhodnutí q <\ Mřížka:
• kaskáda nastane pro práh rozhodnutí q < \
Obecně - kaskádová kapacita (nekonečného) grafu G:
• největší q takové, pro které konečná množina S spustí kaskádu.
• lze ukázat, že největší možná kapacita je \
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 e C má alespoň podíl p hran v C
Kaskády vs. hustota:
• do klastrů s p > (1 - q) se kaskáda nemůže rozsirit
• naopak: pokud se kaskáda zastaví, v grafu je klastr s p > (1 - q)
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é pro jevy 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
Rozšíření
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