Algoritmi scalabili per l'analisi di dati e reti

Titolo originale:

Scalable Algorithms for Data and Network Analysis

Contenuto del libro:

Nell'era dei Big Data, gli algoritmi efficienti sono più che mai richiesti. Se da un lato i Big Data ci portano nel mondo asintotico immaginato dai nostri pionieri, dall'altro mettono in discussione la nozione classica di algoritmi efficienti: Gli algoritmi che un tempo erano considerati efficienti, secondo una caratterizzazione in tempo polinomiale, potrebbero non essere più adeguati per risolvere i problemi di oggi.

È non solo auspicabile ma essenziale che gli algoritmi efficienti siano scalabili. In altre parole, la loro complessità dovrebbe essere quasi lineare o sub-lineare rispetto alle dimensioni del problema. Pertanto, la scalabilità, e non solo la calcolabilità in tempo polinomiale, dovrebbe essere elevata a nozione centrale di complessità per caratterizzare la computazione efficiente.

Scalable Algorithms for Data and Network Analysis esamina una famiglia di tecniche algoritmiche per la progettazione di algoritmi scalabili. Queste tecniche includono l'esplorazione locale della rete, il campionamento avanzato, la sparsificazione e il partizionamento geometrico.

Comprendono anche metodi spettrali di teoria dei grafi, come quelli utilizzati per il calcolo dei flussi elettrici e il campionamento da campi casuali gaussiani di Markov. Questi metodi esemplificano la fusione di pensiero combinatorio, numerico e statistico nell'analisi delle reti.

Scalable Algorithms for Data and Network Analysis illustra l'uso di queste tecniche con alcuni problemi di base che sono fondamentali nell'analisi dei dati di rete, in particolare per l'identificazione di nodi significativi e di cluster/comunità coerenti nelle reti sociali e di informazione. Vengono inoltre discussi alcuni quadri di riferimento al di là dei modelli grafo-teorici per lo studio di questioni concettuali che sorgono nell'analisi delle reti e delle influenze sociali.