Cosa accomuna lo stilare la top list dei blog più aggiornati e la scoperta di una contaminazione in un acquedotto? Questi due problemi hanno la stessa soluzione: un algoritmo ideato da Carlos Guestrin, professore di scienze informatiche alla Carnegie Mellon University, e dai suoi studenti di dottorato.
Un algoritmo è, per l’informatico, un po’ come una ricetta per il cuoco: la successione univoca delle operazioni che portano al risultato. È la base teorica che viene tradotta nella pratica in un programma software. E, proprio a livello teorico, i due problemi sono molto simili: come le notizie si diffondono “a cascata” da un blog ad altri linkati, spandendosi nella blogosfera, così un agente inquinante invade rapidamente tutta la rete acquifera. Il punto è trovare l’origine, l’“Outbreak”.
“L’obiettivo del nostro sistema per quanto riguarda i blog è individuare le notizie più importanti, da dove partono e le altre casse di risonanza il più vicino possibile alla fonte” spiega Guestrin, che ha presentato il suo “Algoritmo delle Cascate” (Celf) in occasione del Convegno Internazionale su “Knowledge Discovery and Data Mining” dell’Association for Computing Machinery. “La soluzione più intuitiva sarebbe scegliere i blog più importanti e famosi” continua Guestrin. “In realtà dalla nostra analisi risultano nei primi cento posti sia siti conosciuti, come Instapundit, sia meno noti, come Don Surber”.
I ricercatori hanno analizzato 45mila blog e i tempi con cui una nuova notizia compariva su ciascuno, cominciando a lavorare all’algoritmo nel 2004 nell’ambito del lavoro “Cost-Effective Outbreak Detection in Networks”. Inizialmente avevano affrontato il problema sviluppando dei sensori wireless, una tecnologia in grado potenzialmente di monitorare alcune condizioni, come la presenza di inquinanti nell’acqua o di alghe nei laghi. In tutti questi casi, però, un numero troppo piccolo di sensori o la scelta di luoghi sbagliati in cui posizionarli porta a informazioni non corrette e parziali. L’algoritmo permette invece di individuare i luoghi principali dove guardare, tanto per la diffusione di inquinanti, quanto per il fluire delle notizie nella Rete.
Il criterio di Celf, circa 700 volte più veloce dei normali programmi, è la ‘sub-modularità’: leggere, per esempio, il terzo blog di una serie fornisce più informazioni nuove che leggere il centesimo. L’algoritmo tiene anche conto della “località”: sensori isolati dagli altri danno informazioni indipendenti. Prossime applicazioni, la ricerca di inquinanti in fiumi e laghi e il perfezionamento delle reti Wi-Fi che copriranno le grandi città. (mi.m)
