IV124 Komplexní sítě
Jan Fousek, Eva Hladká
Fakulta informatiky, Masarykova univerzita
8. března 2018
Dnešní plán
Začneme s kvantifikací síťové struktury:
• stupně uzlů v náhodném grafu
• délky cest a klastrovací koeficient
• co znamenají konkrétní hodnoty pro danou síť
V návaznosti
• jednoduchý nulový model náhodné sítě
2 of 14
Stupeň uzlu
Stupeň uzlu
• počet hran spojující uzel s ostatními
• počet nenulových prvků v řádku (sloupci) matice sousednosti
• u orientovaných grafů rozlišujeme vstupní/výstupní Interpretace
• počet přátel
• počet chemických reakcí
3 of 14
Průměrný stupeň uzlu
Pro neorientovaný graf
• každá hrana „přispívá" dvěma uzlům Distribuce stupně P(k)
• pravděpodobnost, že náhodný uzel má stupeň k
• zavádíme, protože v reálných sítích si s průměrem nevystačíme (ukážeme si později)
4 of 14
Cesty a vzdálenosti
Cesta v grafu
• posloupnost hran spojující dva uzly
• délka cesty: počet hran
• u ohodnocených hran záleží na sémantice
Vzdálenost uzlů d
• délka nejkratší cesty (také geodetická vzdálenost)
• nej kratších cest mezi uzly může být více
• d = oo pokud uzly nejsou spojené
5 of 14
Výpočet vzdálenosti
Neohodnocený graf
• prohledávání do sirky Ohodnocený graf
• Dijkstrův alg. Průměrná délka cesty
• all-to-all
• Floyd-Warshallův alg.
6 of 14
Cesty a vzdálenosti
Ve souvislých komponentách grafu sledujeme:
• diametr sítě
o maximální vzdálenost mezi libovolným párem uzlů
• průměrnou délku cesty d
Co vzdálenosti vypovídají o síti
• efektivita šíření např. informace
• okruhy důvěry v sociálních sítích
7 of 14
Klastrovací koeficient
Klastrovací koeficient C, uzlu /:
• jak jsou mezi sebou propojeni sousedé uzlu /?
8 of 14
Klastrovací koeficient
Průměrný klastrovací koeficient C
. r - i vw r
• lze též číst jako pravděpodobnost, že dva sousedé náhodného uzlu jsou propojeni
Co vypovídá o síti
• /o/ca/n/tranzitivita: přátelé mých přátel jsou moji přátelé
• pravidelnost ve struktuře sítě: trojúhelníky
9 of 14
Príklady reálných sítí
sít
www
E. Coli metab. citace kvasinky proteiny distrib. síť
_v__ 192K
1K 450K
2K 4.9K
609K 5.8K 4.7M 2.9K 6.5K
6.34 5.84 10.47 5.84 2.67
6.98 2.98 11.21 2.98 18.99
Jaký mají ale konkrétní hodnoty význam?
10 of 14
Model náhodného grafu
Proč modelovat náhodný graf:
• vlastnosti lze matematicky odvodit
• užitečný pro srovnání s reálnou sítí:
o cim se hsi ŕ
o co nám to o síti říká?
Model náhodného grafu Erdós-Rényi:
• G(/V, p), kde N je počet uzlů a p pravděpodobnost spojení dvou uzlů
11 of 14
Erdós-Rényi model: vlastnosti
Počet hran \E
• binomiálnř distribuce
P(\E\) = (^)p"E"(l
• kde Emax = N(N - 1)
Ern3 v E
-p)
12 je maximální počet hran
Stupeň uzlu
• binomiální distribuce: P(k)
N-l-k
o
(V) Wběr k o pk\ pravděpodobnost vzniku k hran o (1 — p)N~ľ~k: nepřítomnost zbylých hran k = p{n-l)
O
12 of 14
Erdós-Rényi model: vlastnosti
Klastrovací koeficient
_ Li
• C'< - ki(ki-l)
• za Lj dosadíme - pravděpodobnost hrany mezi sousedy
• tedv c - ^fcll - D
Pro reálné řídké sítě je tedy C velmi malé.
13 of 14
Erdos-Rényi model: vlastnosti
Odvození
uvažujme síť s daným k
uzel má v průměru kd sousedů ve vzdálenosti d tedy počet uzlů ve vzdálenosti d je N(d) = T
K J.
ale N (d) < N a tedy ť™ ^A/aC = «
pro většinu sítí zároveň dobrá aproximace pro průměrnou délku cesty d «
14 of 14