Quantificare l'incertezza nelle previsioni dei grafi

Negli ultimi anni, analizzare dati rappresentati come grafi è diventato un argomento popolare. I grafi si possono trovare in molte aree, come i social network, i sistemi di trasporto e le reti biologiche. Anche se esistono vari metodi per prevedere i grafi, ci sono meno approcci che permettono di valutare l'incertezza di queste previsioni. Questo articolo introduce un metodo per quantificare l'incertezza nelle previsioni dei grafi, utilizzando una tecnica chiamata previsione conforme.

#Comprendere i Grafi

Un grafo è composto da nodi (o vertici) ed archi, che collegano coppie di nodi. Ad esempio, in un grafo di un social network, i nodi potrebbero rappresentare persone, mentre gli archi rappresentano interazioni tra di loro, come amicizie o comunicazioni. I grafi possono essere etichettati o non etichettati. I grafi etichettati hanno una corrispondenza chiara tra i nodi in diverse osservazioni. Al contrario, i grafi non etichettati non hanno un modo chiaro per abbinare i nodi tra i grafi.

#La Necessità della Quantificazione dell'Incertezza

Man mano che i grafi diventano più complessi, diventa essenziale sviluppare metodi efficaci per analizzarli. La quantificazione dell'incertezza è cruciale in vari compiti applicativi, poiché aiuta i ricercatori e i praticanti a valutare l'affidabilità delle loro previsioni. Ad esempio, nel contesto del calcio, la quantificazione dell'incertezza può far luce sulle prestazioni delle squadre analizzando le reti di passaggi dei giocatori durante le partite.

#Cos'è la Previsione Conforme?

La previsione conforme (CP) è un metodo relativamente nuovo progettato per fornire una quantificazione dell'incertezza per i modelli statistici. La CP funziona assegnando un livello di fiducia alle previsioni, consentendo così agli utenti di creare insiemi di previsioni. Questi insiemi indicano dove ci aspettiamo che cadano le osservazioni future, basandoci sui dati passati. Una caratteristica importante della CP è che non richiede assunzioni specifiche sulla distribuzione dei dati.

La CP utilizza misure di conformità per determinare quanto un nuovo punto dati sia simile ai punti esistenti in un dataset. Questa somiglianza aiuta a creare regioni di previsione con solide proprietà probabilistiche. Queste regioni rimangono valide anche considerando solo un numero limitato di osservazioni.

#Panoramica della Metodologia

In questo articolo, presentiamo una metodologia che estende la previsione conforme per gestire popolazioni di grafi. Il nostro metodo può essere utilizzato sia per grafi etichettati che per grafi non etichettati. Per i grafi non etichettati, costruiamo insiemi di previsioni all'interno di un framework chiamato spazio quoziente. Questo approccio ci permette di lavorare con grafi che non hanno nodi chiaramente definiti tra le osservazioni.

Il metodo proposto è privo di modelli e raggiunge validità in campioni finiti. Aiuta a generare insiemi di previsioni che sono interpretabili e facili da comprendere. Esploreremo le caratteristiche del metodo conducendo studi di simulazione sia per grafi etichettati che non etichettati, con esempi tratti dal mondo delle reti di passaggi nel calcio.

#Lavorare con i Grafi

Per lavorare con popolazioni di grafi, iniziamo definendo come rappresentiamo questi grafi matematicamente. Ogni grafo è rappresentato come una Matrice di Adiacenza, che indica come i nodi sono collegati. La distanza tra due matrici di adiacenza viene calcolata utilizzando un metodo specifico che considera le caratteristiche di nodi e archi.

Quando si confrontano più grafi, è essenziale abbinare correttamente i nodi. Per i grafi etichettati, questo può essere fatto in modo semplice poiché i nodi corrispondono direttamente tra le osservazioni. Tuttavia, i grafi non etichettati richiedono un approccio più complesso, poiché i nodi possono rappresentare ruoli intercambiabili senza significati unici.

#Spazio Grafico

Un modo naturale per rappresentare grafi non etichettati è espandere il concetto da una singola matrice di adiacenza a un insieme di matrici di adiacenza permutate. Questo approccio ci permette di considerare tutti i possibili grafi che possiamo ottenere riorganizzando i nodi in un grafo originale.

La struttura che risulta da questo approccio è nota come spazio grafico, dove possiamo parlare di classi di equivalenza di grafi. Ogni classe rappresenta tutti i modi diversi in cui possiamo permutare i nodi in un grafo specifico.

#Sviluppare Insiemi di Previsioni nello Spazio Grafico

L'obiettivo principale del nostro lavoro è creare una quantificazione dell'incertezza per popolazioni di grafi inseriti nello spazio grafico. Utilizziamo l'approccio di previsione conforme per raggiungere questo obiettivo, adattandolo alla natura dei dati grafici.

Per i grafi etichettati, adattiamo il framework generale della CP per lavorare nel contesto dello spazio euclideo multidimensionale formato dalle matrici di adiacenza. Una volta stabilita questa base, possiamo passare al caso più complesso dei grafi non etichettati.

#Insiemi di Previsioni per Grafi Etichettati

Nel caso dei grafi etichettati, possiamo definire insiemi di previsioni che rappresentano l'intervallo delle possibili osservazioni future. Questi insiemi di previsioni assumono la forma di parallelepipedi, offrendo chiarezza e interpretabilità quando si analizzano i dati.

Per formare questi insiemi di previsioni, utilizziamo un dataset di addestramento per costruire un modello che ci consente di calcolare punteggi di non conformità per i dati. Questi punteggi servono come misura di quanto bene le nostre previsioni si allineano con le osservazioni reali.

#Affrontare la Variabilità negli Insiemi di Previsioni

Una sfida con l'approccio iniziale è che gli insiemi di previsioni identificati possono avere lunghezze costanti in tutte le dimensioni. Questo può essere problematico, poiché diversi archi o nodi possono avere livelli di variabilità significativamente diversi. Per tenerne conto, introduciamo un metodo per regolare le lunghezze degli intervalli di previsione in base alla variabilità locale.

Stimando la variabilità locale delle caratteristiche, possiamo modificare le lunghezze degli insiemi di previsioni per riflettere più accuratamente la vera natura dei dati. Questo ci consente di creare insiemi di previsioni più flessibili e informativi, meglio allineati con la struttura sottostante dei grafi.

#Estendere a Grafi Non Etichettati

Ora estendiamo il nostro framework per gestire efficacemente i grafi non etichettati. La transizione ai grafi non etichettati è possibile grazie alle caratteristiche uniche dello spazio grafico, dove possiamo applicare azioni di gruppo per creare classi di equivalenza.

L'insieme di intervalli di previsione per i grafi non etichettati può essere formulato proiettando le nostre previsioni nello spazio grafico. Questo ci consente di definire un insieme di intervalli che seguono le permutazioni degli elementi nello spazio grafico, migliorando notevolmente la flessibilità del nostro modello.

#Implementare la Metodologia

Per dimostrare l'efficacia del nostro approccio, conduciamo studi di simulazione sia per casi etichettati che non etichettati. In questi studi, generiamo grafi con proprietà specifiche e analizziamo quanto bene la nostra metodologia cattura le relazioni sottostanti nei dati.

Nel caso etichettato, confrontiamo le prestazioni dei nostri insiemi di previsioni conformi con vari intervalli di previsione standard. Nel caso non etichettato, ci concentriamo su quanto bene il nostro metodo si allinea con le caratteristiche dei grafi analizzati.

#Applicazione nel Mondo Reale nel Calcio

Una applicazione pratica della nostra metodologia è nell'analisi delle reti di passaggio dei giocatori durante la Coppa del Mondo FIFA 2018. Esaminando le reti di passaggi di diverse squadre, possiamo ottenere preziose informazioni sulle prestazioni e le strategie delle squadre. Le squadre ad alte prestazioni, ad esempio, tendono ad avere reti di passaggi più strutturate, mentre le squadre a bassa prestazione possono mostrare una rete di passaggi più centralizzata e meno varia.

Analizzando le reti di passaggi, allenatori e analisti possono comprendere meglio i punti di forza e di debolezza delle loro squadre. Questo consente loro di prendere decisioni informate sui ruoli dei giocatori e sulle tattiche, migliorando infine le prestazioni complessive della squadra.

#Caso Studio: Analisi della Mobilità durante il COVID-19

La nostra metodologia può essere applicata anche per comprendere i modelli di mobilità durante l'epidemia di COVID-19 in Lombardia, Italia. Analizzando i movimenti delle persone prima e dopo le misure di lockdown, possiamo ottenere informazioni su come le restrizioni abbiano impattato la mobilità nella regione.

Utilizzando dati sulla posizione GPS anonimizzati, possiamo creare grafi che rappresentano i viaggi tra diverse località geografiche. Applicando intervalli di previsione conformi a questi dataset, possiamo quantificare gli effetti del lockdown sui modelli di mobilità, fornendo informazioni preziose a decisori e funzionari della sanità pubblica.

#Conclusione

Prevedere strutture di dati complesse come popolazioni di grafi con incertezza è essenziale in vari campi. In questo articolo, abbiamo presentato una metodologia priva di modelli, computazionalmente efficiente, basata sulla previsione conforme, affrontando sia grafi etichettati che non etichettati.

Esplorando le proprietà uniche dello spazio grafico e sviluppando insiemi di previsioni flessibili, poniamo le basi per ulteriori avanzamenti nell'analisi di dati complessi. I lavori futuri possono espandere questo framework per considerare forme ancora più complesse nei dati grafici, così come altri tipi di dati inseriti in spazi quoziente.

Man mano che continuiamo a esplorare le applicazioni pratiche della nostra metodologia, speriamo di contribuire a nuove scoperte in vari domini, dall'analisi sportiva alla sanità pubblica. In definitiva, comprendere l'incertezza nelle previsioni dei grafi giocherà un ruolo cruciale nel prendere decisioni informate in un mondo sempre più complesso.