Kam dál?
Grafové algoritmy
ISKM89 Organizace dat - sémantický web | podzim 2023
Zuzana Nevěřilová | Centrum zpracování přirozeného jazyka
formálně: Graf G = (V, E), V(G) - uzly (vertex, vertices), E(G) - hrany (edge)
E ⊆ V⨉V, což znamená, že ei
= (vk
, vl
)
orientovaný, s pojmenovanými hranami
Stupeň (degree) uzlu: počet hran, se kterými je uzel spojen (in-degree, out-degree)
Orientovaná cesta (directed path): sekvence vrcholů a hran (v0
, e1
, v1
, …, et
, vt
),
kde platí ei
= {vi-1
, vi
} ∈ E(G)
Souvislý graf - pokud pro každé dva vrcholy existuje cesta
https://teorie-grafu.cz/
Znalostní grafy jsou grafy
Grafové algoritmy:
● zjistit, zda je graf spojitý
● najít cestu
● najít nejkratší cestu (co mají společné X a Y?)
● najít uzel s největším stupněm
Znalostní grafy jsou grafy
● topologie (modul, skupina, komunita, klastr)
● sociogramy (30. léta 20. stol.), dynamika skupiny
Cílem je najít nejdůležitější uzly (centralita)
● počet uzlů, počet hran, max. stupeň - absolutní veličiny
● mezilehlost (betweenness) - propojení jinak málo propojených částí
● blízkost (closeness) - cesty k ostatním uzlům
● eigencentralita - důležitost sousedních uzlů
● page rank - jak “hodnotný” je uzel v závislosti na svých sousedech
● hustota - kolik uzlů je propojeno (sociální sítě jsou poměrně řídké)
● excentricita - maximální vzdálenost od ostatních uzlů; maximální průměr
Síťová analýza
●
Síťová analýza
https://towardsdatascience.com/notes-on-graph-theory-centrality-measurements-e37d2e49550a
Gephi, Gephi Lite
Python + NetworkX
Síťová analýza - software