Una cascata informativa

Equiparare un sistema di acquedotti e di condutture idriche con il Web non è così bislacco come può apparire in un primo momento. Entrambi hanno un’architettura reticolare ed in entrambi fluisce qualcosa: acqua nel primo caso, informazioni nel secondo.

Vengo a scoprire da quest’articolo di Galileo una ricerca condotta da Carlos Guestrin, professore di Scienze Informatiche alla Carnegie Mellon University e dai suoi giovani collaboratori.
Il team di ricercatori si è posto due domande:

In una rete idrica, in quali nodi dobbiamo piazzare i sensori per rilevare efficacemente eventuali contaminazioni?

Nel Web quali blog dovrebbero essere letti per avere una rassegna il più completa possibile degli argomenti principali che circolano nella blogosfera?

I due problemi condividono una struttura comune che può essere rivelata da questo problema più generale:

Dato un processo dinamico di diffusione all’interno di una rete, selezionare un insieme di nodi (sensori, blog) che permetta la rilevazione di un’epidemia (di virus, di informazioni) e del suo punto di origine nel minor tempo possibile.

Per quanto riguarda i blog possiamo riformulare ancora una volta il problema:

Ogni blog, con un suo post, può essere una sorgente informativa che genera una cascata informativa (quando la notizia originale viene ripresa direttamente o indirettamente da altri blog). Si vuole individuare quel piccolo insieme di blog investiti dalla maggior parte delle cascate.


Rispolverando le mie nozioni di Ricerca Operativa e leggendo il paper della ricerca non è stato difficile comprendere come questo genere di problemi viene formalizzato scegliendo una funzione obiettivo che dovrà essere massimizzata o minimizzata considerando anche eventuali vincoli. Nel nostro caso l’obbiettivo potrebbe essere, per esempio, minimizzare il tempo di rilevazione del meme che si va diffondendo, considerando che leggere i blog più popolari (alla ricerca della notizia che ci interessa) richiede più tempo, avendo essi generalmente un gran numero di post.

Ora, trovare una soluzione ottima è “difficile” (si tratta di problemi NP-hard, cioè “almeno difficili quanto i più difficili problemi NP-completi ). I ricercatori hanno però dimostrato che questo genere di problemi sono sub- modulari: nel caso dei blog si può esprimere questa proprietà dicendo che più blog abbiamo letto, meno nuove informazioni traiamo dalla lettura di un nuovo blog. Forti di questa proprietà il team di ricerca ha sviluppato un algoritmo, denominato CELF, che permette di ottenere in maniera efficace e veloce soluzioni che sono certamente vicine a quella ottima.

Una volta determinato l’algoritmo, come è stato affrontato il case study relativo ai blog?

E’ stato scelto di monitorare per un anno un dataset di 45.000 blog (americani), per un totale di 10,5 milioni di post ed un milione di link all’interno dei blog considerati. Cito dal paper:

I post hanno molti metadati, come il time stamp, che ci permettono di individuare le cascate informative ovvero i sub grafici che rappresentano il flusso temporale dell’informazione. Abbiamo adottato la seguente definizione di cascata: ogni cascata ha un singolo post d’origine, e gli altri post si uniscono ricorsivamente linkando i post all’interno della cascata, seguendo un ordine cronologico. Abbiamo rilevato le cascate identificando il post di partenza e quindi seguendo i link entranti.

Sono stati sviluppati due modelli, uno in cui ogni blog ha lo stesso “costo” ed un altro in cui una parte del costo è variabile (più post, più costo). Il primo modello premia i blog più grandi (quelli politici), con un maggior numero di post e più “veloci” nell’inserirsi nella cascata, il secondo predilige blog-sommario, che raccolgono le notizie principali anche se con un certo ritardo.

Quali sono i risultati ottenuti con il CELF?

Questo algoritmo ha permesso di scoprire i blog più rilevanti e di arrivare alla conclusione che non sempre la lettura dei blog più popolari sia la strada migliore per tenersi aggiornati sui temi caldi che attraversano la blogosfera, ma spesso risulti più utile la lettura di blog più piccoli ma di alta qualità, blog che l’algoritmo è in grado di trovare.

Si è anche giunti alla conclusione che è sufficiente leggere un big blog una sola volta alla settimana (preferibilmente di venerdì…), catturando in un’unica “passata” tutto il suo flusso informativo.

Utilizzando l’algoritmo CELF è stato inoltre possibile stabilire quali siano i migliori criteri per stabilire la “qualità” di un blog: abbastanza intuitivamente (vedi grafico) la scelta migliore è considerare il numero di link in entrata. Un blog coon molti link in entrata è una sorgente di cascate informative.

bheurtr-hist-unit-z2-fixed-web.png

I migliori blog, secondo i vari modelli utilizzati durante la ricerca, sono elencati in questo sito.

10 thoughts on “Una cascata informativa

  1. Federico, due post interessantissimi: questo e l’altro su Sylvie (spero di avere scritto bene il nome! Non ho il tempo di controllare).

    Vado a segnalarli sul mio blog e a salvarli sul mio tumblr per poterli leggere con calma in seguito.
    Vi sono contenuti dei tesori di informazioni.

    Grazie, grazie, grazie:)

  2. Complimenti per questo post e per il blog..
    il mio interesse per i sistemi complessi mi ha portato fino a qui… e qui vedo altrettanta passione per complessità ed affini..

    ciao
    Luca

  3. Ciao Luca e grazie. E’ bello ogni tanto “incontrare” (anche per caso) gli autori dei libri che leggo…🙂

    E’ un tema, quello dei sistemi complessi, che mi sarebbe piaciuto molto approfondire, non solo come lettore attento ma anche da un punto di vista più “professionale”. Temo sia un po’ tardi…

  4. non è tardi, figurati…
    anche perchè è un tema talmente multidisciplinare che sicuramente ti verranno in aiuto tante altre esperienze che hai fatto in altri campi..

  5. Post molto interessante.
    Mi fa pensare a cosa potrebbe creare un team transdisciplinare di esperti di matematica della complessità, interaction design, psicologia, comunicazione, ecc. insieme …. mmmm …. facciamo un elenco e ci incontriamo?🙂

  6. buttata lì, però non è una cattiva idea..
    se poi siamo tutti “giovani” potremmo contribuire a stimolare questa gerontocrazia con qualche novità.. e un approccio un po’ + complesso…

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...