Negli ultimi anni, numerosi studi hanno messo in luce come, analizzando reti complesse create a partire da legami sociali, sia possibile osservare, caratterizzare e prevedere molteplici aspetti delle attività umane (ad esempio calcolare la probabilità che si creino nuove connessioni tra gli utenti di un social network [1] così come stimare l'utilizzo di un servizio di comunicazione online [2]). La costante crescita delle informazioni raccolte a partire da attività quotidiane (dati di traffico online, telecomunicazioni, tracce di mobilità...) ha inoltre reso necessario rivalutare l'importanza della dimensione temporale sia nella modellazione che per l'analisi di tutti quei fenomeni che possono essere studiati tramite l'adozione di reti complesse. Al fine di far fronte alla necessità di un'analisi più accurata che tenga conto della continua evoluzione dei fenomeni sociali, nel corso degli ultimi anni, al laboratorio Knowledge Discovery e Data Mining Laboratory (KDD Lab) dell'ISTI-CNR abbiamo deciso di focalizzare la nostra attenzione sullo studio delle reti dinamiche.
Tra tutte le attività relative all'analisi di reti il problema di Community Discovery è universalmente considerato come uno dei più sfidanti. Nel corso dell'ultimo decennio, sono stati proposti molti algoritmi finalizzati ad identificare le comunità nascoste nelle complesse strutture modellate tramite reti "statiche", ovvero reti la cui topologia non muta nel tempo (un esempio è il nostro approccio DEMON [3]), tuttavia, i fenomeni sociali che si sviluppano nel mondo reale sono spesso dinamici (immaginiamoci ad esempio log estratti da chiamate telefoniche o anche le interazioni che avvengono ogni giorno su online/offline social network). Quando si analizzano tali scenari, gli algoritmi classici di Community Discovery descritti per realtà statiche non sono in grado di identificare partizioni del grafo analizzato che siano semanticamente coerenti con l'informazione temporale espressa dai dati.
Per far fronte a questa limitazione abbiamo definito un nuovo approccio TILES [4] il quale, lavorando su un modello completamente dinamico di reti sociali - descritte come flussi di interazioni tra utenti in cui i nodi e gli archi possono crearsi così come cessare di esistere con il passare del tempo - consente l'identificazione sia di comunità che dei diversi eventi da esse vissuti durante il loro ciclo di vita (nascita/fusione/divisione/scomparsa).
Il nostro algoritmo, in modo diverso da quanto realizzato da quelli proposti sino ad oggi (per i quali abbiamo fornito prima una classificazione e review in [5]), non riduce il problema di analisi di un entità dinamica ad una sequenza ordinata di sotto problemi definiti su grafi statici ottenuti a tramite discretizzazione temporale: al contrario TILES è progettato per sfruttare le perturbazioni locali descriventi le dinamiche di base di una rete complessa (i.e. la comparsa/scomparsa di nodi/archi) al fine di aggiornare in modo continuo, fluido, le comunità individuate. Tale scelta progettuale risolve due problemi principali introdotti da approcci precedenti: (i) evita la necessità di individuare un partizionamento temporale della rete dinamica che sia "significativo" (problema dipendente dal contesto analizzato), e (ii) permette di monitorare in modo continuo l'evoluzione di ciascuna comunità senza dover passare da una fase di matching che identifichi ad ogni istante la versione precendete della struttura analizzata. Nel nostro lavoro abbiamo mostrato come TILES sia in grado di superare gli approcci considerati lo "stato dell'arte" nell'identificare e tracciare comunità dinamiche facilmente interpretabili su casi di studio reali costruiti a partire da reti di comunicazione di differente natura (call graphs, commenti tra utenti di Facebook, messaggi diretti tra utenti della piattaforma Sina Weibo).
Sino ad oggi una delle strategie principali per valutare l'operato di algoritmi di Community Discovery ha coinvolto il confronto delle sotto-strutture di rete identificate con quelle offerte da una ground truth esterna. Data la quasi assenza di dataset annotati con partizioni ground truth, negli ultimi decenni sono stati proposti molteplici generatori di reti sintetiche che consentissero di costruire ambienti controllati per scopi di valutazione.
Poiché il problema di Community Discovery su reti dinamiche rappresenta un task relativamente nuovo per cui l'interesse della comunità scientifica è in continua crescita, si è inoltre sentita la necessità di progettare un benchmark su misura finalizzato alla valutazione della qualità delle partizioni identificate. In [6,7] abbiamo proposto il nostro generatore, RDyn: tale approccio è in grado di sintetizzare grafi dinamici capaci di emulare le principale caratteristiche di reti reali (distribuzione power law per il grado e la dimensione delle comuntà, ridotta lunghezza dei cammini minimi, alto coefficiente di clustering locale) così come generare comunità dinamiche simulandone i principali eventi. Quest'ultima peculiarità rende RDyn, al meglio delle nostre conoscenze, uno dei primi modelli generativi esplicitamente progettati per valutare approcci di Community Discovery pensati per contesti dinamici.
[1] Rossetti, Giulio; Guidotti, Riccardo; Miliou, Ioanna; Pedreschi, Dino; Giannotti, Fosca
"A Supervised Approach for Intra-/Inter-Community Interaction Prediction in Dynamic Social Networks", Social Network Analysis and Mining, 2016. (Open Access)
[2] Rossetti, Giulio; Pappalardo, Luca; Kikas, Riivo; Pedreschi, Dino; Giannotti, Fosca; Dumas, Marlon "Homophilic network decomposition: a community-centric analysis of online social services", Social Network Analysis and Mining, 2016. (Open Access)
[3] Coscia, Michele; Rossetti, Giulio; Giannotti, Fosca; Pedreschi, Dino "Uncovering Hierarchical and Overlapping Communities with a Local-First Approach" ACM Transactions on Knowledge Discovery from Data (TKDD), 9 (1), 2014.
[4] Rossetti, Giulio; Pappalardo, Luca; Pedreschi, Dino; Giannotti, Fosca "Tiles: an online algorithm for community discovery in dynamic social networks" Machine Learning Journal, 2016. (Open Access)
[5] Rossetti, Giulio; Cazabet, Rémy "Community Discovery in Dynamic Networks: A Survey" ACM Computing Surveys (submitted)
[6] Rossetti, Giulio; Pappalardo, Luca; Rinzivillo, Salvatore "A novel approach to evaluate community detection algorithms on ground truth" 7th Workshop on Complex Networks, Springer-Verlag, 2016.
[7] Rossetti, Giulio "RDyn: Graph Benchmark handling Community Dynamics" Journal of Complex Networks (submitted)
Focus