Škálovateľné algoritmy pre analýzu údajov a sietí

Pôvodný názov:

Scalable Algorithms for Data and Network Analysis

Obsah knihy:

V dobe veľkých dát sú efektívne algoritmy žiadanejšie ako kedykoľvek predtým. Hoci nás Big Data zavedú do asymptotického sveta, ktorý si predstavovali naši priekopníci, zároveň spochybňujú klasickú predstavu o efektívnych algoritmoch: Algoritmy, ktoré sa kedysi považovali za efektívne podľa charakteristiky polynomiálneho času, už nemusia byť adekvátne na riešenie dnešných problémov.

Je nielen žiaduce, ale aj nevyhnutné, aby boli efektívne algoritmy škálovateľné. Inými slovami, ich zložitosť by mala byť takmer lineárna alebo sublineárna vzhľadom na veľkosť problému. Preto by sa škálovateľnosť, nielen polynomiálna časová vypočítateľnosť, mala povýšiť na ústredný pojem zložitosti na charakterizovanie efektívneho výpočtu.

Škálovateľné algoritmy pre analýzu údajov a sietí skúmajú rodinu algoritmických techník na návrh škálovateľných algoritmov. Tieto techniky zahŕňajú lokálny prieskum siete, pokročilé vzorkovanie, sparsifikáciu a geometrické rozdelenie.

Zahŕňajú aj spektrálne grafovo-teoretické metódy, ktoré sa používajú na výpočet elektrických tokov a vzorkovanie z Gaussových Markovových náhodných polí. Tieto metódy sú príkladom spojenia kombinatorického, numerického a štatistického myslenia v analýze sietí.

Škálovateľné algoritmy pre analýzu údajov a sietí ilustrujú použitie týchto techník na niekoľkých základných problémoch, ktoré sú zásadné pri analýze sieťových údajov, najmä pri identifikácii významných uzlov a ucelených zhlukov/spoločností v sociálnych a informačných sieťach. Rozoberá aj niektoré rámce nad rámec grafovo-teoretických modelov na štúdium koncepčných otázok, ktoré sa objavujú pri analýze sietí a sociálnych vplyvov.