Annalisa DE BONIS | Progetti

DINAMICHE IN RETI: ANALISI, ALGORITMI E SISTEMI

Il progetto di ricerca consta delle seguenti due linee di ricerca: 1. Studio della diffusione di influenza ed informazione in reti sociali, 2. Simulazione di modelli basati su Agenti.1. In questo ambito una rete sociale è vista come un grafo G in cui l'insieme dei vertici corrisponde a persone e gli archi corrispondono a relazioni tra individui. La diffusione di informazione in G avviene in successivi tempi, ed ogni nodo ha due stati:inattivo o attivo. Intuitivamente, possiamo vedere un nodo attivo come una persona che ha adottato una nuova idea o prodotto, cosi come essi si diffondono nella rete, mentre un nodo inattivo viene inteso come una persona che non ha ancora adottato la nuova idea, o prodotto. La transizione da inattivo ad attivo avviene mediante meccanismi di "pressione sociale", che possono essere differentemente modellati. L'obiettivo della ricerca consiste nel selezionare un (piccolo) sottoinsieme di vertici (da influenzare direttamente mediante incentivi di varia natura) che eventualmente influenzi l'intero grafo. I problemi specifici che si intendono studiare in questo progetto sono:a) studiare il problema nel caso in cui ad ogni persona è associato un costo, che rappresenti la spesa in cui incorre un agente esterno nello stabilire il meccanismo di incentivazione atto a influenzare inizialmente la persona in questione;b) studiare il problema nel caso in cui ad ogni arco (u,v) è associato un peso, che rappresenti la quantità di influenza che la persona u esercita sulla persona v;c) studiare il problema nel caso in cui si fissi un limite temporale entro il quale si desideri che il processo di diffusione abbia buon fine. Per ciascuno dei problemi su esposti si intendono progettare ed analizzare algoritmi efficienti che ritornino insiemi di nodi di "piccolo costo", che inizialmente influenzati mediante incentivi esterni, siano in grado di influenzare l'intera rete, a seconda del meccanismi di diffusione di informazione considerato. Quello su cui concentreremo la nostra attenzione postula che in ogni istante un nodo passi dallo stato inattivo a quello attivo se nell'istante precedente un numero sufficiente (quantificato da un valore "soglia") di suoi vicini è già nello stato attivo. la originalità ed innovatività del progetto è garantita dal fatto che non sono noti in letteratura studi che hanno considerato problemi di diffusione di informazioni sotto il modello generale che abbiamo sopra delineato.2. Le simulazioni di modelli basati su Agenti permettono la emulazione di processi complessi generati a partire da comportamenti semplici realizzati da agenti, che interagiscono tra di loro sulla base di una posizione nello spazio oppure attraverso connessioni indipendenti dallo spazio, modellate con un grafo. Per la esecuzione in parallelo di queste simulazioni è necessario provvedere ad un partizionamento su diversi nodi del carico di lavoro, preservando la località della comunicazione. In caso le interazioni vengano modellate su una topologia spaziale (2D o 3D) allora questo risulta agevolato dalla prossimità fisica, mentre maggiormente complesso è il problema che risulta dal partizionamento di grafi di arbitraria natura in modo da minimizzare il numero di archi tagliati (corrispondenti a comunicazione tra processori). In questa linea di progetto, ci ripromettiamo di analizzare strategie e algoritmi di partizionamento, verificandone la efficienza su noti esempi di grafi massivi corrispondenti a reti sociali, a strutture di network esistenti in realtà, etc. (come SNAP-Stanford Large Network Dataset Collection). Dalla valutazione teorica di efficienza, si passerà anche alla implementazione all'interno del framework D-Mason, che permette la simulazione distribuita di modelli basati ad agente su un cluster di nodi di calcolo. L'originalità ed innovatività di questa linea del progetto consiste nel tentativo di parallelizzare la simulazione di processi le cui interazioni sono arbitrarie, raramente fatto in letteratura.