Algoritmi scalabili pentru analiza datelor și a rețelelor

Titlul original:

Scalable Algorithms for Data and Network Analysis

Conținutul cărții:

În era Big Data, algoritmii eficienți sunt mai solicitați ca niciodată. În timp ce Big Data ne duce în lumea asimptotică imaginată de pionierii noștri, aceasta pune la încercare și noțiunea clasică de algoritmi eficienți: Algoritmii care obișnuiau să fie considerați eficienți, conform caracterizării în timp polinomial, s-ar putea să nu mai fie adecvați pentru rezolvarea problemelor actuale.

Este nu doar de dorit, ci esențial ca algoritmii eficienți să fie scalabili. Cu alte cuvinte, complexitatea lor ar trebui să fie aproape liniară sau sub-lineară în raport cu dimensiunea problemei. Astfel, scalabilitatea, nu doar calculabilitatea în timp polinomial, ar trebui să devină noțiunea centrală de complexitate pentru caracterizarea calculului eficient.

Scalable Algorithms for Data and Network Analysis analizează o familie de tehnici algoritmice pentru proiectarea algoritmilor scalabili. Aceste tehnici includ explorarea rețelei locale, eșantionarea avansată, sparsificarea și partiționarea geometrică.

Acestea includ, de asemenea, metode spectrale de teorie a grafurilor, cum ar fi cele utilizate pentru calcularea fluxurilor electrice și eșantionarea din câmpuri aleatorii Markov gaussiene. Aceste metode exemplifică fuziunea gândirii combinatorii, numerice și statistice în analiza rețelelor.

Algoritmi scalabili pentru analiza datelor și a rețelelor ilustrează utilizarea acestor tehnici prin câteva probleme de bază care sunt fundamentale în analiza datelor de rețea, în special pentru identificarea nodurilor semnificative și a grupurilor/comunităților coerente în rețelele sociale și de informații. De asemenea, se discută câteva cadre dincolo de modelele graf-teoretice pentru studierea întrebărilor conceptuale care apar în analiza rețelelor și a influențelor sociale.