GraphGist: Time Scale Event Meta Model

by Kenny Bastani

[Warning]Warning

This GraphGist has not yet been submitted and approved for publication. If you're the developer, please submit for publication using the GraphGist Portal.

Recently at the GraphConnect 2013 conference in San Francisco, many questions were asked about how to handle temporal or time-based traversals in a Neo4j graph database.

The goal of this GraphGist is to provide you with a lens to help you see information as simple temporal facts that are captured across space and time.

"Time is a dimension in which events can be ordered from the past through the present into the future." - via Wikipedia - Time

Graph databases like Neo4j are not just a traditional data store. Rather, graph databases are an entirely new paradigm that aids a person in capturing meaning from the world as relativistic information described by connected data.

What is relativistic information?

Relatvistic information is actually meaning. Unconnected data has no meaning. Only when you connect data can you better describe what it actually means.

Observations are made, captured, from a perspective of a position in time and space. A graph is a model of that space.

A graph database provides you a means to model space and see information from the perspective of a point relative to other points. Those points can represent a condition or state of the world.

Consider the example below.

  • Pam met Sally.

  • John met Sally.

  • Sally met Anne.

  • Anne met Pam.

Each point on the graph is from the perspective of a person relative to meeting other people.

The need to understand these nodes temporally, ordered linearly as time-based events, starts with modeling time as a graph.

What is a time graph?

Time is a hierarchical model of categorization that enables the back-referencing or prediction of events on a timeline that moves forward in a single direction.

In the time scale graph that is modeled above, a shortest path traversal from a blue colored node to the transparent colored node constitutes a unique time identity in bits.

The identity traced by the red path is 0→1→0→1→0→0. The reverse path is 0→0→1→0→1→0 or simply 001010, a unique identity in bits.

CREATE (a:a { key:'a0', tempo:'0' })
CREATE (a)<-[:child_of]-(b0:b { key:'b0', tempo:'0' })
CREATE (a)<-[:child_of]-(b1:b { key:'b1', tempo:'1' })
CREATE b0<-[:child_of]-(c0:c { key:'c0', tempo:'0' })
CREATE b0<-[:child_of]-(c1:c { key:'c1', tempo:'1' })
CREATE b1<-[:child_of]-(c2:c { key:'c2', tempo:'0' })
CREATE b1<-[:child_of]-(c3:c { key:'c3', tempo:'1' })
CREATE (d0:d { key:'d0', tempo:'0', interval:'50' }),(d1:d { key:'d1', tempo:'1', interval:'50' })
CREATE (d2:d { key:'d2', tempo:'0', interval:'50' }),(d3:d { key:'d3', tempo:'1', interval:'50' })
CREATE (d4:d { key:'d4', tempo:'0', interval:'50' }),(d5:d { key:'d5', tempo:'1', interval:'50' })
CREATE (d6:d { key:'d6', tempo:'0', interval:'50' }),(d7:d { key:'d7', tempo:'1', interval:'50' })
CREATE c0<-[:child_of]-d0, c0<-[:child_of]-d1
CREATE c1<-[:child_of]-d2, c1<-[:child_of]-d3
CREATE c2<-[:child_of]-d4, c2<-[:child_of]-d5
CREATE c3<-[:child_of]-d6, c3<-[:child_of]-d7
CREATE d0-[:NEXT]->d1-[:NEXT]->d2-[:NEXT]->d3-[:NEXT]->d4-[:NEXT]->d5-[:NEXT]->d6-[:NEXT]->d7
CREATE (a1:a { key:'a1', tempo:'1' })
CREATE (a1)<-[:child_of]-(b2:b { key:'b2', tempo:'0' })
CREATE (a1)<-[:child_of]-(b3:b { key:'b3', tempo:'1' })
CREATE (z0:z { key: 'z0' , tempo:'0' })<-[:child_of]-(a1)
CREATE (y0:y { key: 'y0' , tempo:'0' })<-[:child_of]-(z0)
CREATE (z0)<-[:child_of]-(a)
CREATE b2<-[:child_of]-(c4:c { key:'c4', tempo:'0' })
CREATE b2<-[:child_of]-(c5:c { key:'c5', tempo:'1' })
CREATE b3<-[:child_of]-(c6:c { key:'c6', tempo:'0' })
CREATE b3<-[:child_of]-(c7:c { key:'c7', tempo:'1' })
CREATE (d8:d { key:'d8', tempo:'0', interval:'50' }),(d9:d { key:'d9', tempo:'1', interval:'50' })
CREATE (d10:d { key:'d10', tempo:'0', interval:'50' }),(d11:d { key:'d11', tempo:'1', interval:'50' })
CREATE (d12:d { key:'d12', tempo:'0', interval:'50' }),(d13:d { key:'d13', tempo:'1', interval:'50' })
CREATE (d14:d { key:'d14', tempo:'0', interval:'50' }),(d15:d { key:'d15', tempo:'1', interval:'50' })
CREATE c4<-[:child_of]-d8, c4<-[:child_of]-d9
CREATE c5<-[:child_of]-d10, c5<-[:child_of]-d11
CREATE c6<-[:child_of]-d12, c6<-[:child_of]-d13
CREATE c7<-[:child_of]-d14, c7<-[:child_of]-d15
CREATE d7-[:NEXT]->d8-[:NEXT]->d9-[:NEXT]->d10-[:NEXT]->d11-[:NEXT]->d12-[:NEXT]->d13-[:NEXT]->d14-[:NEXT]->d15
CREATE (a2:a { key:'a2', tempo:'0' })
CREATE (a2)<-[:child_of]-(b4:b { key:'b4', tempo:'0' })
CREATE (a2)<-[:child_of]-(b5:b { key:'b5', tempo:'1' })
CREATE (z1:z { key: 'z1' , tempo:'1' })<-[:child_of]-(a2)
CREATE y0<-[:child_of]-z1
CREATE b4<-[:child_of]-(c8:c { key:'c8', tempo:'0' })
CREATE b4<-[:child_of]-(c9:c { key:'c9', tempo:'1' })
CREATE b5<-[:child_of]-(c10:c { key:'c10', tempo:'0' })
CREATE b5<-[:child_of]-(c11:c { key:'c11', tempo:'1' })
CREATE (d16:d { key:'d16', tempo:'0', interval:'50' }),(d17:d { key:'d17', tempo:'1', interval:'50' })
CREATE (d18:d { key:'d18', tempo:'0', interval:'50' }),(d19:d { key:'d19', tempo:'1', interval:'50' })
CREATE (d20:d { key:'d20', tempo:'0', interval:'50' }),(d21:d { key:'d21', tempo:'1', interval:'50' })
CREATE (d22:d { key:'d22', tempo:'0', interval:'50' }),(d23:d { key:'d23', tempo:'1', interval:'50' })
CREATE c8<-[:child_of]-d16, c8<-[:child_of]-d17
CREATE c9<-[:child_of]-d18, c9<-[:child_of]-d19
CREATE c10<-[:child_of]-d20, c10<-[:child_of]-d21
CREATE c11<-[:child_of]-d22, c11<-[:child_of]-d23
CREATE d15-[:NEXT]->d16-[:NEXT]->d17-[:NEXT]->d18-[:NEXT]->d19-[:NEXT]->d20-[:NEXT]->d21-[:NEXT]->d22-[:NEXT]->d23
CREATE (a3:a { key:'a3', tempo:'1' })
CREATE (a3)<-[:child_of]-(b6:b { key:'b6', tempo:'0' })
CREATE (a3)<-[:child_of]-(b7:b { key:'b7', tempo:'1' })
CREATE (z1)<-[:child_of]-(a3)
CREATE b6<-[:child_of]-(c12:c { key:'c12', tempo:'0' })
CREATE b6<-[:child_of]-(c13:c { key:'c13', tempo:'1' })
CREATE b7<-[:child_of]-(c14:c { key:'c14', tempo:'0' })
CREATE b7<-[:child_of]-(c15:c { key:'c15', tempo:'1' })
CREATE (d24:d { key:'d24', tempo:'0', interval:'50' }),(d25:d { key:'d25', tempo:'1', interval:'50' })
CREATE (d26:d { key:'d26', tempo:'0', interval:'50' }),(d27:d { key:'d27', tempo:'1', interval:'50' })
CREATE (d28:d { key:'d28', tempo:'0', interval:'50' }),(d29:d { key:'d29', tempo:'1', interval:'50' })
CREATE (d30:d { key:'d30', tempo:'0', interval:'50' }),(d31:d { key:'d31', tempo:'1', interval:'50' })
CREATE c12<-[:child_of]-d24, c12<-[:child_of]-d25
CREATE c13<-[:child_of]-d26, c13<-[:child_of]-d27
CREATE c14<-[:child_of]-d28, c14<-[:child_of]-d29
CREATE c15<-[:child_of]-d30, c15<-[:child_of]-d31
CREATE d23-[:NEXT]->d24-[:NEXT]->d25-[:NEXT]->d26-[:NEXT]->d27-[:NEXT]->d28-[:NEXT]->d29-[:NEXT]->d30-[:NEXT]->d31
CREATE (met0:event:met { key:'met0', verb:'meet', past:'has met', present:'meets', future:'will meet' })-[:event]->d0
CREATE (met1:event:met { key:'met1', verb:'meet', past:'has met', present:'meets', future:'will meet' })-[:event]->d5
CREATE (met2:event:met { key:'met2', verb:'meet', past:'has met', present:'meets', future:'will meet' })-[:event]->d9
CREATE (met3:event:met { key:'met3', verb:'meet', past:'has met', present:'meets', future:'will meet' })-[:event]->d14
CREATE (person:class { key:'person', plural:'People', singular:'Person' })
CREATE (sally:person { key:'person0', name:'Sally' })-[:class_of]->person
CREATE (anne:person { key:'person1', name:'Anne' })-[:class_of]->person
CREATE (john:person { key:'person2', name:'John' })-[:class_of]->person
CREATE (pam:person { key: 'person3' , name:'Pam' })-[:class_of]->person
CREATE (product:class { key:'product', plural:'Products', singular:'Product' })
CREATE (shoe:product:shoes { key:'product0', name:'pair of red heels' })-[:class_of]->product
CREATE (hat:product:hats { key:'product1', name:'sombrero' })-[:class_of]->product
CREATE (headphone:product:headphones { key:'product1', name:'noise cancelling headphones' })-[:class_of]->product
CREATE (coffeemug:product:coffeemugs { key:'product1', name:'i heart neo4j coffee mug' })-[:class_of]->product
CREATE (view0:event:view { key:'view0', verb:'view', past:'has viewed', present:'is viewing', future:'will view' })-[:event]->d16
CREATE (view1:event:view { key:'view1', verb:'view', past:'has viewed', present:'is viewing', future:'will view' })-[:event]->d17
CREATE (view2:event:view { key:'view2', verb:'view', past:'has viewed', present:'is viewing', future:'will view' })-[:event]->d18
CREATE (view3:event:view { key:'view3', verb:'view', past:'has viewed', present:'is viewing', future:'will view' })-[:event]->d21
CREATE (view4:event:view { key:'view4', verb:'view', past:'has viewed', present:'is viewing', future:'will view' })-[:event]->d22
CREATE (view5:event:view { key:'view5', verb:'view', past:'has viewed', present:'is viewing', future:'will view' })-[:event]->d23
CREATE (buy0:event:buy { key:'buy0', verb:'buy', past:'bought', present:'is buying', future:'will buy' })-[:event]->d19
CREATE (buy1:event:buy { key:'buy1', verb:'buy', past:'bought', present:'is buying', future:'will buy' })-[:event]->d24
CREATE anne-[:event]->met0-[:event]->pam
CREATE pam-[:event]->met1-[:event]->sally
CREATE sally-[:event]->met2-[:event]->anne
CREATE john-[:event]->met3-[:event]->sally
CREATE pam-[:event]->view0-[:event]->shoe
CREATE pam-[:event]->view3-[:event]->headphone
CREATE pam-[:event]->view4-[:event]->coffeemug
CREATE pam-[:event]->buy0-[:event]->shoe
CREATE sally-[:event]->view1-[:event]->shoe
CREATE sally-[:event]->view2-[:event]->hat
CREATE sally-[:event]->buy1-[:event]->hat
CREATE sally-[:event]->view5-[:event]->coffeemug
RETURN *

Get time identity as shortest path

MATCH p=shortestPath((n1:d)-[:child_of*]->(n2:y))
WHERE n1.key = 'd10'
RETURN extract(n IN nodes(p) | n.key) as Path
Loading graph...
Loading table...

Get time identity as bit string

MATCH p=shortestPath((n1:d)-[:child_of*]->(n2:y))
WHERE n1.key = 'd10'
RETURN DISTINCT reduce(s = '' , n IN nodes(p)| n.tempo + s) AS TimeIdentity
ORDER BY TimeIdentity
Loading table...

Get all time identities as bit strings

MATCH p=shortestPath((n1:d)-[:child_of*]->(n2:y))
RETURN DISTINCT reduce(s = '' , n IN nodes(p)| n.tempo + s) AS TimeIdentity
ORDER BY TimeIdentity
Loading table...

One of the most powerful use cases for traversals in a graph database is the need to model the recurrence relations of past events as they relate to future events.

What is an event graph?

An event is any feature or characteristic that describes the state of the world in the past, present, or future.

Furthermore, an event is described by an arbitrary set of features that generalize on the properties contained across all possible events.

This means that an event is only meaningful by connecting it to data that describes it. By attaching a set of features, represented by nodes in the graph, it is possible to attribute meaning to a set of temporal events.

A feature is further described by an arbitrary set of classes that generalize on its combinatorial or shared characteristics. In other words, two or more features can be grouped into a class that generalizes its characteristics at a group level.

The image below represents a time scale connected to a series of events (met). Events, represented as triangular nodes in the image, are also connected to a hierarchy of features (John, Sally, Pam, Anne) which are then further generalized into classes (Person).

Get time ordered events where people met other people

MATCH p=(p0:person)-[:event]->(ev)-[:event]->(p1:person)
WITH p, ev
MATCH time_identity = (d0:d)<-[:event]-(ev)
WITH d0, p
MATCH p1=(d0)-[:child_of*]->(y0:y)
RETURN extract(x IN nodes(p)| coalesce(x.name, x.future)) AS Interaction, reduce(s = '' , n IN nodes(p1)| n.tempo + s) AS TimeIdentity
ORDER BY TimeIdentity
Loading table...

Get time ordered events where people interacted with a product

MATCH p=(p0:person)-[:event]->(ev)-[:event]->(p1:product)
WITH p, ev
MATCH time_identity = (d0:d)<-[:event]-(ev)
WITH d0, p
MATCH p1=(d0)-[:child_of*]->(y0:y)
RETURN extract(x IN nodes(p)| coalesce(x.name, x.future)) AS Interaction, reduce(s = '' , n IN nodes(p1)| n.tempo + s) AS TimeIdentity
ORDER BY TimeIdentity
Loading table...

Using this model we can determine how to recommend products or services to a user based on similar patterns of behavior happening over time.

How do I do recommendations?

Graphs allow us to connect the dots in order to find recommendations.

People who viewed a product

MATCH p=(p0:person)-[:event]->(ev:view)-[:event]->(p1:product)
WITH p, ev
MATCH time_identity = (d0:d)<-[:event]-(ev)
WITH d0, p
MATCH p1=(d0)-[:child_of*]->(y0:y)
RETURN extract(x IN nodes(p)| coalesce(x.name, x.past)) AS Interaction, reduce(s = '' , n IN nodes(p1)| n.tempo + s) AS TimeIdentity
ORDER BY TimeIdentity
Loading table...

People who viewed X also viewed Y

Let’s find products that other people viewed who also viewed the product named 'pair of red heels'.

MATCH p=(p0:person)-[:event]->(ev:view)-[:event]->(p1:product)
WITH p0, p1
WHERE p1.name = 'pair of red heels'
WITH p0
MATCH p0-[:event]->(ev:view)-[:event]->(p2:product)
WHERE p2.name <> 'pair of red heels'
RETURN p2.name as Product, count(p0) as Views
Loading table...

Recommendation GraphGists

It’s your turn! Fork this GraphGist on GitHub and modify the code to create your own recommendation GraphGists.

Also, follow me on Twitter for more Neo4j GraphGists → @kennybastani

Run
Table
Graph
Table!
Graph!
Error!
Loading