Skalowalne algorytmy analizy danych i sieci

Oryginalny tytuł:

Scalable Algorithms for Data and Network Analysis

Zawartość książki:

W erze Big Data wydajne algorytmy są poszukiwane bardziej niż kiedykolwiek wcześniej. Podczas gdy Big Data przenosi nas do asymptotycznego świata przewidzianego przez naszych pionierów, rzuca również wyzwanie klasycznemu pojęciu wydajnych algorytmów: Algorytmy, które kiedyś były uważane za wydajne, zgodnie z wielomianową charakterystyką czasu, mogą już nie być odpowiednie do rozwiązywania dzisiejszych problemów.

Efektywne algorytmy powinny być skalowalne, co jest nie tylko pożądane, ale wręcz niezbędne. Innymi słowy, ich złożoność powinna być prawie liniowa lub podliniowa w odniesieniu do rozmiaru problemu. Dlatego też skalowalność, a nie tylko obliczalność w czasie wielomianowym, powinna stać się głównym pojęciem złożoności charakteryzującym wydajne obliczenia.

Książka Scalable Algorithms for Data and Network Analysis zawiera przegląd rodziny technik algorytmicznych służących do projektowania skalowalnych algorytmów. Techniki te obejmują lokalną eksplorację sieci, zaawansowane próbkowanie, sparsyfikację i partycjonowanie geometryczne.

Obejmują one również spektralne metody teorii grafów, takie jak stosowane do obliczania przepływów elektrycznych i próbkowania z gaussowskich pól losowych Markowa. Metody te stanowią przykład połączenia myślenia kombinatorycznego, numerycznego i statystycznego w analizie sieci.

Książka Scalable Algorithms for Data and Network Analysis ilustruje zastosowanie tych technik w kilku podstawowych problemach, które mają fundamentalne znaczenie w analizie danych sieciowych, w szczególności w identyfikacji znaczących węzłów i spójnych klastrów/społeczności w sieciach społecznych i informacyjnych. Omówiono także niektóre ramy wykraczające poza modele grafowo-teoretyczne do badania kwestii koncepcyjnych, które pojawiają się w analizie sieci i wpływów społecznych.