A FRAMEWORK FOR NETWORK EVOLUTION

La trasformazione digitale ha rivoluzionato le strategie organizzative, generando un flusso di dati senza precedenti. Con il mercato della trasformazione digitale proiettato a 3,4 trilioni di dollari entro il 2026, sfruttare questi dati è cruciale. La network science offre strumenti per analizzare sistemi complessi modellando nodi e archi. Ha applicazioni in diversi ambiti: nelle scienze sociali analizza social media, polarizzazione e migrazioni; in finanza studia stabilità dei mercati e frodi; in biologia e medicina svela interazioni proteiche e meccanismi patologici; in ecologia esplora dinamiche tra specie ed ecosistemi. Mentre la ricerca inizialmente si concentrava su reti statiche, l'attenzione si è spostata recentemente verso le reti temporali che incorporano relazioni variabili nel tempo. Questa evoluzione riflette la natura intrinsecamente dinamica della maggior parte dei sistemi complessi. Ad esempio, le reti di mobilità urbana catturano i mutevoli modelli di traffico durante il giorno. Le reti sociali tracciano la diffusione di informazioni e tendenze nel tempo mentre quelle finanziarie rivelano modelli nella tempistica delle transazioni e nelle risposte del mercato. Le reti di trasmissione delle malattie evidenziano gli aspetti temporali dei modelli di diffusione. La ricerca attuale si è concentrata principalmente sulla descrizione dei cambiamenti della rete nel tempo da una prospettiva macroscopica, lasciando una lacuna significativa nella comprensione dei meccanismi sottostanti che guidano questi modelli evolutivi. Estraendo i meccanismi evolutivi, altresì detti regole, da un grafo temporale, possiamo rivelare i meccanismi mesoscopici generali che governano le dinamiche della rete. Ciò significa comprendere come le strutture microscopiche e mesoscopiche della rete evolvono nel tempo. Questa tesi affronta questa lacuna della letteratura sviluppando un framework, detto GERANIO, per la modellazione, l'estrazione e l'analisi delle graph evolution rules. L'estrazione delle graph evolution rules (GER) è un metodo di pattern mining basato sulla frequenza di occorrenza di tali pattern. Le GER hanno lo scopo di identificare cambiamenti locali ricorrenti durante l'evoluzione della rete. In modo simile alle association rules nel contesto del data mining, le GER sono composte da due elementi (sottografi): una precondizione e un insieme di postcondizioni. Queste regole indicano che un sottografo che corrisponde (è isomorfo) alla precondizione è probabile che evolva in una delle configurazioni rappresentate dalle postcondizioni, con la probabilità corrispondente. Nonostante il loro potenziale, gli approcci esistenti affrontano sfide significative, in particolare nella complessità dell'identificazione e dell'analisi delle GER e nelle difficoltà associate all'isomorfismo tra grafi. Il framework GERANIO fornisce diversi contributi chiave per affrontare questi problemi. Innanzitutto, introduce una tassonomia universale per la modellazione delle reti evolutive, applicabile a vari domini. In secondo luogo, fornisce un metodo di categorizzazione per sottografi isomorfi attraverso un canonical coding, garantendo l'applicabilità universale dei risultati. In terzo luogo, propone modelli nulli ad hoc per estrarre regole statisticamente significative. In quarto luogo, introduce l'algoritmo TULIP, che estrae regole di evoluzione dei grafi da una prospettiva più ampia rispetto agli approcci esistenti. Infine, sviluppa il concetto di profili evolutivi – distribuzioni di probabilità delle frequenze delle regole che consentono un feedback visivo immediato sul comportamento della rete in evoluzione e sul confronto tra reti. Il framework fa una distinzione tra stand-alone rules e graph evolution rules generali. Le stand-alone rules eccellono nell'identificazione di processi evolutivi specifici, come i cicli nelle reti finanziarie, mentre le regole generali catturano il comportamento evolutivo completo di una rete. Ad entrambi gli approcci é possible applicate il canonica coding del framework, che fornisce una rappresentazione unica dei grafi per un facile confronto e analisi. Questa tesi è strutturata in quattro parti principali: un background completo sulla modellazione delle reti temporali e i concetti teorici; un'esplorazione della componente del framework GERANIO dedicata alle stand-alone rules; e un'introduzione all'algoritmo TULIP che consente di estrarre le graph evolution rules generali. Infine, questa tesi esplora un aspetto evolutivo tipico delle reti Web3 che non può essere completamente catturato dalle sole graph evolution rules: la user migration. Questo fenomeno è particolarmente rilevante nel contesto delle blockchain-based online social networks (BOSN). Attraverso questi contributi, questa tesi ha lo scopo di migliorare la nostra comprensione delle dinamiche delle reti e fornire strumenti per confrontare diverse reti e analizzarne i cambiamenti nel tempo.

Grantor dc:publisher

Università degli Studi di Milano

Year dc:date

2024

Author dc:creator

• GALDEMAN, ALESSIA

Contributors dc:contributor

• tutor: S. Gaito ; co-relatore: M. Zignani ; coordinatore: R. Sassi
• A. Galdeman
• GAITO, SABRINA TIZIANA
• SASSI, ROBERTO

• network science
• temporal network
• network evolution
• graph mining
• multilayer network
• machine learning
• cryptocurrency
• social network
• financial network
• nft
• web3
• Settore INFO-01/A - Informatica

Statement dc:rights

• info:eu-repo/semantics/openAccess

Language dc:language

eng

Identifier

http://dx.doi.org/10.13130/galdeman-alessia_phd2024-12-05
10.13130/galdeman-alessia_phd2024-12-05

OAI identifier oai:identifier

oai:air.unimi.it:2434/1120937