IV124 Komplexní sítě
Eva Výtvarová, Jan Fousek, Eva Hladká
Fakulta informatiky, Masarykova univerzita
3. dubna 2019
Úvod
náhodná síť: binomická distribuce stupně, ER model
Máme něco podobného pro bezškálovou síť?
2 of 16
Generování sítí s daným pk
obecnější přístup:
• na základě dané distribuce stupně Pk vygenerujeme síť
• umožňuje vytvořit surogátní data k reálné síti
• neříká nic o původu struktury samotné sítě Tři hlavní varianty:
• konfigurační model
• randomizace zachovávající stupeň
• model se skrytým parametrem
3of 16
Konfigurační model
Postup:
• zadána sekvence stupňů uzlů
• hrany vygenerovány náhodně: dvojice pahýlků
Vlastnosti
• pravděpodobnost hrany mezi uzly / a y: 2ffi i ==> upřednostňuje propojení uzlů s vysokým stupněm
• vede ke vzniku smyček a multihran
4 of 16
Randomizace zachovávající stupeň
Postup:
• na vstupu je již existující síť
• iterativně vybíráme náhodnou dvojici hran, které prohodíme
• {(/,y),(/c,/)}^{(/,/),(/c,y)}
Vlastnosti:
• zachovává velikost a hustotu sítě, Pk
• vlastnosti závislé na jiných parametrech se ztratí
5of16 _
Model se skrytým parametrem
Postup:
• začneme s izolovanými uzly
• každému uzlu přiřadíme hodnotu parametru 77/ z distribuce p(r])
• hranu (/',/) přidáme s pravděpodobností
• např. pro bezškálovou síť: 77/ = c//a, / = 1,..., N
o výsledkem síť s Pk ~ /c~(1+«)
Vlastnosti:
• nevytváří multihrany a smyčky
• flexibilní vůči požadavku na výsledné Pk
6 of 16 _
Růstové modely
Motivace
• zajímají nás principy stojící za bezškálovým charakterem sítí sdíleným napříč velmi rozdílnými systémy
Pozorování:
• reálné sítě často vznikají postupným vývojem (připojováním uzlů)
• citační síť, WWW, ...
7of 16
Uprednostnené pripojení
Intuice:
• nově příchozí jsou s větší pravděpodobností představeni „populárním" uzlům s vysokým k,
• jich get richer" Obecný postup
• iterativně přidáváme uzel s daným počtem hran
• pravděpodobnost navázání na existující uzel j závisí na k.
8of 16
Model Barabási-Albert
Postup
• každý nový uzel přichází s m hranami
• pravděpodobnost připojení k uzlu / je dána:
Výsledná distribuce:
p(k) « 2/7?2/c"3
9 of 16
Netlogo demo
10 of 16
Nelineární upřednostněné připojení
Obecně U(k) ~ ka
sublineární (a < 1)
• nestačí na vznik hubů: náhodná síť
lineární (a « 1)
• bezškálová síť
superlineární (a > 1)
• tendence „bohatnutí bohatých" dominuje
• vítěz bere vše: topologie hvězda
11 of 16 ľ g _
Sublinear
Superlinear
a=2
0.5
1.5
a
. .   Stretched Hub-and-spoke Pk      Exponential _ .  Power law      x .
exponential topology
max
Int (In t)1/(1 "q)   - t1/(7-l) ^ f
Network Random
nQ No preferential
Random Scale-free
nw ~ *" ~£szr subiinear
Linear
(a = 0)      (0 < a < 1)     (a = 1)
m winners take all
Superlinear
(q>1)
12o1f^arabasi: Network Science Book
Model Bianconi-Barabási
Motivace:
• BA model zvýhodňuje dříve příchozí
• v reálných sítích tomu tak není: Friendster -Myspace - Facebook - ?
• „schopné" uzly mohou předběhnout stávající dominující huby - do modelu přidáme parametr zdatnost (f itness)
13 of 16
Model Bianconi-Barabási
Postup
• v každém kroku přidáme uzel s m hranami a zdatností rj z dané distribuce p{rj)
• pravděpodobnost připojení nově příchozího uzlu k uzlu / je dána jako:
Model Bianconi-Barabási
Vlastnosti:
• i malý rozdíl ve zdatnosti uzlu vede k velkým rozdílům ve stupni (limitně)
• pokud je zdatnost 77 identická pro všechny uzly, model se redukuje na BA
= pro uniformní p{rf) dostaneme bezškálovou síť
• čas příchodu uzlu není hlavním určujícím prvkem pro výsledný stupeň
15 of 16
NetworkX demo
16 of 16