Misure per la struttura topologico-temporale

La struttura topologica di una rete statica può essere caratterizzata da un ampio numero di misure basate sulle connessioni tra nodi o tra insiemi di nodi. Come visto al termine della sezione precedente, quando aggiungiamo la dimensione temporale alla rete, molte di tali misure devono essere rivalutate o riviste. L’esempio più banale di ciò è il fatto che qualsiasi cammino sulla rete deve seguire una sequenza di contatti ordinati tem- poralmente. Per semplicità di notazione nel seguito considereremo reti rappresentate

Figura 2.3: Un grafo temporale e il corrispondente grafo statico aggregato

attraverso sequenze di contatti, ma le definizioni date possono essere estese in modo del tutto intuitivo al caso dei grafi a intervalli.

Time-respecting paths

Definiamo time-respecting path una sequenza di contatti con tempi di contatto non de- crescenti. Nell’esempio di Fig.2.3 (A, B, 0), (B, D, 2) è un time-respecting path mentre (B, C, 2), (C, E, 1) non lo è. La differenza principale tra i cammini nelle reti statiche e i time-respecting path è il fatto che questi ultimi non sono transitivi: l’esistenza di

time-respecting path tra i e j e tra j e k non assicura l’esistenza di un time-respecting path tra i e k.

I time-respecting path definiscono quindi quali vertici possono essere raggiunti dagli altri nodi all’interno di una determinata finestra di osservazione t ∈ [t0, T ]. In aggiunta è

possibile aggiungere dei vincoli sul tempo che i cammini possono trascorrere nei vertici, ovvero sui tempi tra due contatti consecutivi in un cammino. Questo ad esempio può essere utile per studiare il verificarsi di interazioni tipiche tra nodi. Consideriamo ad esempio uno studio sulle chiamate fatte tra gli utenti di una compagnia telefonica. Vo- gliamo sapere quanto frequentemente a una chiamata di un utente x a un utente y segue una chiamata “di risposta” dell’utente y all’utente x. È ovvio che se la chiamata avviene oltre una certa soglia temporale essa non è più da considerarsi come “di risposta” alla precedente, ma come un ulteriore successivo contatto tra gli utenti in questione.

Distanze, latenze e cammini minimi

Per le reti statiche si definisce la geodesic distance tra due vertici come la lunghezza del cammino minimo che li collega. Per le reti temporali è possibile definire il concetto di

cammino minimo sia in termini di numero di hop (o di archi di peso minimo) in modo analogo al caso statico, sia in termini di lunghezza temporale del cammino, definita come la differenza temporale tra l’ultimo e il primo contatto del cammino. Il tempo minimo in cui un nodo i può raggiungere un nodo j è detta la loro latenza (o distanza temporale). Tuttavia anche la latenza è dipendente dal tempo e in particolare essa può variare in base al tempo in cui si inizia a percorrere il cammino. Consideriamo quindi un nodo i al tempo t in una rete temporale su cui si diffondono informazioni. Denotiamo con φi,t(j)

l’ultimo istante di tempo precedente a t in cui l’informazione può essere partita da j per raggiungere i entro il tempo t. Chiamiamo tale misura la vista di i dell’informazione di j al tempo t e chiamiamo latenza dell’informazione di j rispetto a i al tempo t il valore λi,t(j) = t − φi,t(j). Questa esprime quanto vecchia è la misura di i proveniente

da j al tempo t. Un’altra misura a cui siamo interessati, detta latenza media, è una media del tempo impiegato da un nodo i per raggiungere un nodo j, che può essere calcolata come una media di tutti i time-respecting path minimi tra due nodi in funzione del tempo. Tuttavia una tale misura può essere difficile da calcolare perché verso la fine della finestra di osservazione la latenza diviene infinita, dato che i cammini non hanno tempo sufficiente per essere completati entro il termine della finestra temporale. In ogni modo si definisce latenza caratteristica la distanza temporale (latenza) media tra ogni coppia di nodi del grafo, ovvero:

L = 1 N (N − 1)

X

ij

dij

dove con d_ij indichiamo le distanze temporali.

Temporal motifs

Introduciamo brevemente anche il framework dei temporal motif per studiare la struttura topologico-temporale di reti dinamiche in cui gli eventi dei singoli nodi non si sovrap- pongono nel tempo. I temporal motif, presentati da Kovanen et al. in [29], sono classi di sequenze di eventi simili, dove la similarità si riferisce non solo alla topologia ma anche all’ordine temporale degli eventi.

Molte reti di grandi dimensioni presentano proprietà simili su scala globale, come distribuzioni caratteristiche dei gradi dei nodi, lunghezza ridotta dei cammini tra coppie di nodi o alto numero di triangoli. A livello mesoscopico tali reti presentano una mag- giore varietà ma presentano comunque motif particolarmente significativi, ovvero piccoli sottografi topologicamente equivalenti che possono rappresentare interazioni sociali di

particolare rilevanza. Formalmente i motif sono definiti come classi di grafi isomorfi in cui i nodi sono tutti temporalmente connessi. Due eventi sono detti ∆t−connessi se esiste una sequenza di eventi e_i = e_k0ek1...ekn = ej tale che tutte le coppie di eventi

consecutivi sono ∆t−adiacenti, dove due eventi vengono detti ∆t−adiacenti se hanno almeno un nodo in comune e la differenza di tempo tra la fine del primo evento e l’inizio del secondo è al più ∆t. In [29] gli autori propongono un algoritmo per il riconoscimento di temporal motif a partire da sottografi massimali connessi.

Cerchiamo di spiegare meglio con un esempio cosa siano questi motif. Utilizziamo un dataset contenente le chiamate di un singolo operatore di telefonia mobile in un periodo di 120 giorni. Vogliamo scoprire i motivi ricorrenti che coinvolgono 3 eventi consecutivi, considerando una finestra temporale di ∆t = 10min. I motivi più ricorrenti sono, come mostrato in Fig.2.4 (adattata da [29]), quelli più semplici, che coinvolgono nella conversazione solo due utenti, mentre quelli meno comuni sono motif triangolari. Tramite i temporal motif è quindi possibile studiare interazioni sociali tipiche di un certo sistema, studiando in questo modo il comportamento caratteristico degli utenti che ne fanno parte.

Figura 2.4: I quattro motif formati da 3 eventi più comuni (a sinistra) e meno comuni (a destra) riscontrati nei dati