LARUS
Published in

LARUS

The definitive guide to time modeling with graphs

“La cattiva notizia è che il tempo vola. La buona notizia è che sei il pilota” (Michael Althsuler)

E se vi parlassi di come “pilotare” il tempo?! E di come farlo attraverso i grafi?

Questa guida racchiude in modo semplice ma chiaro lo studio delle diverse tecniche di modellazione del tempo nei database a grafi; in particolare con Neo4J.

Perchè vogliamo modellare il tempo?

L’analisi della modellazione del tempo è importante per due aspetti chiave:

  1. Storico dei dati: Studio dell’evoluzione del grafo nel tempo, ossia la cronologia della variazione dei dati
  2. Analisi What-if: Studio predittivo in base all’andamento del grafo nel tempo

Bene, ecco le tecniche che approfondiremo in seguito:

  • Time Bound Data
  • Time-Based Versioned Graph
  • Snapshot System
  • Space-Time Varying Graph

Sarà anche illustrato un caso di studio specifico, modellato attraverso la tecnica del Time Varying Graph, tecnica che risulta ad oggi la più utilizzata.

Ok, iniziamo!

Tecnica semplice e basilare: definiamo un attributo temporale nel tipo di relazione. Ad esempio, si pensi di dover modellare dei voli delle compagnie aeree in questo modo:

Considero due aeroporti, rispettivamente X e Y, connessi ad un volo se e solo se esistono uno o più voli da X a Y (nodo sorgente e nodo destinazione).

I nodi “Airport” avranno gli attributi inerenti all’aeroporto mentre il nodo “Flight” avrà gli attributi temporali ‘arrival’ e ‘distance’.

Posso considerare anche i passeggeri e il personale di volo che andranno da X a Y con un volo in un determinato giorno e saranno associati al volo.

  • Time-Based Versioned Graphs

Simile al modello descritto sopra, il tipo di relazione temporale può essere inoltre usato per il controllo delle versioni basato sul tempo.
In questo caso vogliamo memorizzare sia il valore attuale sia i valori passati attraverso il tipo di relazione “data”. In fase di interrogazione sarà necessario filtrare utilizzando la data più recente per recuperare il valore attuale (relazione più recente).

Il controllo delle versioni generalmente anche detto “versioning”, ci consente di tener traccia dei cambiamenti (lo storico) e permette di effettuare analisi di tipo what-if. Si tratta di formulare scenari predittivi attraverso l’analisi dei dati storici, con lo scopo di valutare il comportamento di un sistema reale.

C’è già una soluzione pronta all’uso?

Come con altri database, anche in Neo4j non esiste una soluzione pronta all’uso. Sarà necessario integrare il controllo delle versioni come parte del processo di modellazione dei dati.
Il controllo delle versioni porta necessariamente la creazione di molti più dati, nodi e relazioni. Le query potranno essere molto complesse e lente, in quanto si deve tener conto di una o più versioni.

2.1 Il controllo delle versioni in Neo4j

I principi alla base del controllo delle versioni basato sul tempo sono piuttosto semplici:
- separare l’oggetto dallo stato, collegati da una relazione

  • catturare i tempi di modifica all’interno della proprietà della relazione che collega queste due entità.

    Da qui, la nuova terminologia.

    Nodi Identità: Questi nodi identificano l’identità dell’oggetto.
    Relazioni Strutturali: Collegano i nodi di identità con data e ora. Sono simili alle generiche relazioni per grafi senza strutture temporali, con l’aggiunta di due proprietà “From” e “To”, rispettivamente dei timestamp.
    Nodi e Relazioni Di Stato: Ad ogni nodo identità sono collegati uno o più nodi di stato. Ogni nodo di stato rappresenta un’istantanea immutabile dello stato di un’entità.
    I nodi di stato sono connessi ai nodi identità attraverso le relazioni di stato con data e ora.

Sembra complesso? Vediamo un esempio:

I nodi blu rappresentano i nodi identità con l’attributo univoco id (esempio shop_id) mentre i nodi rossi rappresentano i nodi di stato con i vari attributi che lo caratterizzano.

Entrambe le relazioni di stato (STATE) e strutturali (SUPPLIED_BY e SELLS) hanno la proprietà from e to.

I nodi di stato e la relazione STATE rappresentano lo stato dell’identità in un preciso momento.

Cosa possiamo analizzare ora?

È facile notare come questa modellazione renda semplice ed intuitiva una query che interroghi lo stato “corrente” utilizzando la proprietà to oppure cerca relazioni il cui periodo è tra la proprietà from e to.

Convertendo il formato della data in maniera adeguata possiamo formulare query su tutti i campi temporali dello stato del grafo

Qual è lo svantaggio?

  • Non adatto a grafi in evoluzione rapida nel tempo

3. Snapshot System

L’ approccio consiste nel convertire il grafo time-dependent (grafo che cambia nel tempo) in una sequenza di grafi statici nel tempo ed ognuno di questi è chiamato “istantanea” (“snapshot”). L’approccio basato su snapshot deve avere la capacità di generare un gran numero di istantanee (fotografie) ogni volta che avviene una modifica nel grafo e archiviarle, anche se esiste un solo grafo time-dependent. In particolare, il metodo basato su snapshot nelle reti dinamiche è una sequenza di istantanee del grafo G[t1-tn]={G1,G2,G3, …, Gn}. Ogni istantanea Gi è un grafo statico che rappresenta uno stato della rete al tempo ti .

Ma quali sono gli svantaggi?

  • Elevato dispendio di memoria nel tempo dovuto alla replica di un intero grafo ogni volta che si verifica un aggiornamento o una modifica
  • Non adatto a grafi in evoluzione rapida nel tempo

E se dovessimo modellare grafi in evoluzione rapida nel tempo?

4. Space-Time Varying Graph

Per le reti in rapida evoluzione si presenta un framework basato sul grafo spazio-temporale (STVG) che utilizza l’approccio Whole-graph (grafo intero).

L’approccio Whole-graph modella una rete dinamica come un grande grafo indicizzato nel tempo, G[t1,tn]=(V[t1-tn],E[t1-tn]), dove V[t1-tn] ed E[t1-tn] sono un insieme di tutte le istanze nodi e archi rispettivamente nell’arco temporale t1-tn. Ogni nodo e arco ha un timestamp in modo da rappresentare il suo tempo di validità nel grafo. Il tempo è acquisito nel momento in cui sono inseriti o cancellati nel grafo nodi, archi e relativi attributi.

I tre componenti principali sono:

  1. Grafo intero G (Whole-Graph) rappresentato dallo spazio e dal tempo (S,T) dove S sono tutti i sottografi di G (S’1, S’2, …, S’n) mentre T è il Time Graph.
  2. Grafi proiettati fondamentali per il recupero di nodi e archi che definiscono lo stato del Whole-Graph a determinate risoluzioni temporali. I grafi proiettati presentano i grafi chiave su cui sono calcolate le metriche per l’analisi evolutiva dell’intero grafo G.

3. I sottografi (S’1, S’2, …, S’n) utilizzati per facilitare la modellazione concettuale della connettività tra entità in spazi distinti di una rete nel mondo reale. I sottografi richiedono una connessione costante. I nodi appartenenti a sottografi differenti, ad esempio S’i ⊂ S e S’j ⊂ S sono collegati da archi di connettività complementari. Solo un sottografo S’i è collegato al Time-graph T rappresentato in diversi livelli di risoluzione temporali. Inoltre, in qualsiasi momento un nodo sorgente v ∈ S’i ⊂ S sarà connesso in sequenza ad un nodo destinazione u ∈ S’i ⊂ S attraverso archi di adiacenza (“NEXT”).

Compresi tutti gli ingredienti necessari, analizziamo un caso di studio!

Prendiamo in esame una rete di transito degli autobus di Greater Moncton, New Brunswick, Canada modellata con il framework Space-Time Varying Graph.

Per generare il whole-graph si definiscono prima i sottografi Platial e Mobility.
Il sottografo Platial è formato da archi e nodi spaziali; una sequenza di luoghi geografici fisici che rappresentano un viaggio (“Trip”) del bus all’interno della rete di transito. Il viaggio consiste in un percorso della linea di autobus che ha inizio, ad esempio, in un “Bus Stop” (luogo di partenza), attraversa strade, fermate ed incroci fino ad arrivare a destinazione. Gli archi “Next” rappresentano le relazioni di adiacenza tra due luoghi geografici consecutivi.
Il sottografo Mobility è formato da nodi e archi spazio-temporali; rappresenta la sequenza di eventi di mobilità (spostamenti e fermate) di un bus in movimento nello spazio e nel tempo. In questo sottografo l’entità primaria è “Trip” che rappresenta la traiettoria di un bus in movimento.
Ogni nodo nel sottografo Mobility si verifica in un determinato momento; essi sono collegati ai nodi foglia del time-graph.
I sottografi sopra descritti risultano essere così connessi:

Analisi dei dati e risultati

Gli algoritmi delle metriche per analizzare l’evoluzione della rete di trasporto sono stati implementati ed eseguiti con query ad-hoc in Neo4j. Si riportano due dei più importanti risultati di tale analisi.

a. Grado di centralità: mostra quali sono le principali vie, fermate e linee di autobus nella città di Moncton. La classifica del grado di centralità per le linee di autobus, stilata sulla basedei loro spostamenti, è una visione utile che consentirebbe di prendere decisioni come, ad esempio, quali linee di autobus combinare o rimuovere, affinché siano ridotti i viaggi meno frequentati, oppure quali linee ottimizzare per migliorare la mobilità.

b. Connessione del grafo: si mostra il percorso dell’autobus 50–12, in transito dalle 8 del mattino per quattro giorni consecutivi, che genera un grafo di connessione con altre entità, dal suo nodo origine fino al nodo destinazione. Il grafo in figura rende semplice per i gestori del transito visualizzare le soste effettuate dagli autobus alle fermate previste o in generale gli episodi di arresto in diversi punti nel tempo. Pertanto, grazie alla connettività è possibile individuare i luoghi e i momenti in cui il viaggio ha subito alcune soste a causa della congestione del traffico.

Cosa sarebbe successo se avessimo analizzato il caso di studio attraverso il sistema snapshot?

Il caso di studio attraverso il modello STVG ha generato un grafo di circa 44GB. Gli autori riportano che, al contrario, se si fosse adottato un sistema basato su snapshot si sarebbero create 7280 istantanee ogni ora, 732 al giorno, 18 al mese e 2 annuali, tra le quali la più piccola avrebbe occupato 1,3 GB di spazio. Di conseguenza, lo spazio necessario per l’archiviazione di tutte le istantanee del grafo sarebbe stato di circa 24 TB, poiché lo spazio totale di archiviazione aumenta linearmente con il numero di istantanee.

In conclusione

Questo tipo di analisi adatto a qualsiasi rete di transito offre potenzialmente un modo efficiente per scoprire la dinamica della rete nello spazio e nel tempo.
La fase successiva di questo lavoro potrebbe essere un’analisi dettagliata di ciascuna delle metriche del grafo dei trasporti, per un periodo di tempo ed un feed di dati più lungo, che consentirebbe di effettuare ulteriori approfondimenti predittivi in base all’evoluzione. Un’analisi basata su un lasso di tempo più lungo permetterebbe, altresì, di valutare con maggior adeguatezza anche la struttura dello stesso database a grafo, al fine di valutare le prestazioni e la capacità di gestione dei dati di grandi dimensioni.

Laura Di Egidio, Data Scientist @LARUS

--

--

We are data engineers and data scientists team passionate about data and top quality data insight-driven software solutions. We share contents around NoSQL, Graph Technologies and stream processing platform

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store