Category: SPARQL – spatialguru.com

Neo4j Cypher Query for Graph Density Analysis

Graph analysis is all about finding relationships. In this post I show how to compute graph density (a ratio of how well connected relationships in a graph are) using a Cypher query with Neo4j. This is a follow up to the earlier post: SPARQL Query for Graph Density Analysis.

Installing Neo4j Graph Database

In this example we launch Neo4j and enter Cypher commands into the web console…

Neo4j is a java application and requires OracleJDK 7 or OpenJDK 7 to be on your system.
Download the Community Edition of Neo4j. In my case I grabbed the Unix .tar.gz file and unzipped the files. Install on Windows may vary.
From command line and within the newlycreatedneo4j-community folder, start the database:
1. ```
bin/neo4j start
```
Use web console at: http://localhost:7474 – the top line of the page is a window for entering Cypher commands.
Load sample CSV data using a Cypher command – I cover this in a separate post here. Be sure the path to the file is the same on your system, matching where you saved the CSV files to.

Quick Visualization

Using the built-in Neo4j graph browser, you can easily see all your relationships as nodes and edges. For a query, return results that include all the objects:

MATCH (p:Person)
RETURN p

Compute Graph Density

Graph Density requires total number of nodes and total number of relationships/edges. We do them both separately, then pull them together at the end.

Compute the number of unique nodes in the graph

MATCH (p:Person)
RETURN count(p)

count(p)
21
Returned 1 row in 49 ms

This tells us that there are 21 people as Subjects in the graph. (I’m not sure how this differed from the 20 I had in my other post – perhaps part of the header from the CSV came in?)

Therefore, a maximum number of edges between all people would be 21² (we’ll use only 21×20 as a person might not link to themselves in this example).

Compute the number of edges in the graph

Here we only select subjects that are “Person” and only where they have a relationship called “HAS_FRIEND”.

(The “p:”, “r:” and “f:” prefixes act like the “?…” variables references in SPARQL – you set them to whatever you want as a pointer to the data returned from the MATCH statement.)

MATCH (p:Person)-[r:HAS_FRIEND]-(f:Person)
RETURN count(DISTINCT r)

count(DISTINCT r)
57

When we defined the data from CSV, we set up a relationship that I thought would be just one-way. But you can see, if you don’t provide the DISTINCT keyword, that you’ll get double the record counts, so I’m assuming it’s treating the relationships as bi-directional.

Total edges is 57. Do the quick math and see that the ratio is then:

57 / (21 x 20)
= 57 / 420
= 0.136...

Rolling it all together

We can do all this in a single query and get some nice readable results, even though the query looks a bit long. Note that I snuck in an extra “-1” to account for that stray record I didn’t account for.

MATCH (p:Person)-[r:HAS_FRIEND]-(f:Person) 
RETURN count(DISTINCT p) as nrNodes, 
 count(DISTINCT r) as nrEdges,
 count(DISTINCT r)/((count(DISTINCT p)-1) * (count(DISTINCT p) - 1.0)) AS graphDensity

nrNodes nrEdges graphDensity
21      57      0.1425

Challenge: Why did I get different results than in the SPARQL query example?

In the earlier post I had only 20 nodes, but in this one got 21. Can you explain why?

Future Post

What’s your favourite graph analytic? Let me know and I’ll try it out in the future post.

One of things I have planned is to do some further comparisons between graph analytics in SPARQLverse and other product like Neo4j but with large amounts of data instead of these tiny examples. What different results would you expect?

Code snippet: SPARQL Query Graph Density

I’m testing out sharing SPARQL code snippets using Github Gist features. I’ll be adding more as I work through more graph-specific examples using SPARQLverse, but here is my first one:

 SELECT (?nrEdges/(?nrNodes *(?nrNodes - 1.0)) AS ?graphDensity)
 FROM <graphName>
 WHERE {
  { SELECT (COUNT (*) AS ?nrEdges) (COUNT (DISTINCT ?person) AS ?nrNodes)
    WHERE { ?person <knows> ?anotherPerson . }
   }
 }

Ideally we’d have a common landing place for building up a library of these kinds of examples.

Graph relations in Neo4j – simple load example

In preparation for a post about doing graph analytics in Neo4j (paralleling SPARQLverse from this earlier post), I had to learn to load text/CSV data into Neo. This post just shows the steps I took to load nodes and then establish edges/relationships in the database.

My head hurt trying to find a simple example of loading the data I had used in my earlier example but this was because I was new to the Cypher language. I was getting really hung up on previewing the data in the Neo4j visualiser and finding that all my nodes had only ID numbers was really confusing me. I had thought it wasn’t loading my name properties or something when it was really just a visualisation setting (more on that another time). Anyway, enough distractions…

Graph Data File – Simple Graph Relations Example

I took my earlier sample data and dumbed it down to fit the normal paradigm of Neo4j – separate nodes and edges load files. I appreciated working with triples before as I didn’t have to pre-load all the nodes first, but that’s also a story for another day.

First, the nodes file looked like the following. Note, I thought I had to add the ID though I didn’t end up using it after all:

id,name
1,Chong
2,Lashaun
3,Roberta
4,Elin
5,Tameka
6,Rosalie
7,Noella
8,Elim
9,Mae
10,Fernando
11,Alan
12,Katrina
13,Kaitlyn
14,Zackary
15,Nana
16,Lamonica
17,Meggan
18,Fermina
19,Genevieve
20,Manual
21,Jolie

The second file was simply a list of “source” and “target” names – the graph relations – where the first person had the second person for a friend. (We handle them as unidirectional in this example.)

source,target
Chong,Lashaun
Chong,Roberta
Chong,Elin
Chong,Tameka
Chong,Rosalie
Chong,Noella
Lashaun,Roberta
Lashaun,Elin
Lashaun,Tameka
Roberta,Elin
Roberta,Tameka
Roberta,Rosalie
Roberta,Noella
Elim,Tameka
Elim,Rosalie
Elim,Noella
Elim,Mae
Elim,Fernando
Elim,Alan
Tameka,Katrina
Tameka,Kaitlyn
Rosalie,Alan
Noella,Katrina
Mae,Kaitlyn
Mae,Zackary
Mae,Nana
Mae,Lamonica
Fernando,Meggan
Fernando,Fermina
Fernando,Genevieve
Fernando,Manual
Fernando,Jolie
Fernando,Chong
Alan,Lashaun
Alan,Roberta
Alan,Elin
Katrina,Tameka
Katrina,Rosalie
Kaitlyn,Noella
Zackary,Fernando
Zackary,Alan
Nana,Katrina
Nana,Kaitlyn
Nana,Zackary
Lamonica,Zackary
Lamonica,Fernando
Meggan,Zackary
Meggan,Fernando
Meggan,Jolie
Fermina,Fernando
Fermina,Jolie
Fermina,Chong
Genevieve,Lashaun
Genevieve,Roberta
Manual,Elin
Manual,Tameka
Jolie,Rosalie

Graph of first load test of Neo4j — Basic load example of a handful of relationships.

Loading CSV Relationships into Neo4j

To get the data into Neo4j I had to run two commands. But first I run a sort of “delete all” as I was doing lots of testing:

MATCH (n)
WITH n LIMIT 10000
OPTIONAL MATCH (n)-[r]->()
DELETE n,r;

Then load all the nodes, assigning each one to a Person entity and grabbing only the name property from the CSV:

LOAD CSV WITH HEADERS FROM "file:///Users/tyler/graph/friends_nodes.csv" AS nodes
CREATE (p:Person { name: nodes.name })

And finally, load the edges/relationships to map persons -> to persons via a has_friend relationship:

LOAD CSV WITH HEADERS FROM "file:///Users/tyler/graph/friends_edges.csv" AS edges
MATCH (a:Person { name: edges.source})
MATCH (b:Person { name: edges.target })
CREATE (a)-[:HAS_FRIEND]->(b);

The resulting load will say something like:

Created 57 relationships, returned 0 rows in 46 ms

More on exploring and analysing this in a future post. Tweet it or comment if you are interested in more along this line. Thanks for reading!

Graph analytics – the new super power

Graph analytics – is it just hype or is it technology that has come of age? Mike Hoskins, CTO of Actian sums it up well in this article from InfoWorld:

Mike Hoskins writes about graph analytics and how it is a game changer for finding unknown unknowns

“One area where graph analytics particularly earns its stripes is in data discovery. While most of the discussion around big data has centered on how to answer a particular question or achieve a specific outcome, graph analytics enables us, in many cases, to discover the “unknown unknowns” — to see patterns in the data when we don’t know the right question to ask in the first place.”

Read Mike’s full article at:

February 4, 2015
How graph analytics deliver deeper understanding

In the remainder of this post I outline a few more of my thoughts on this topic and give you pointers to some more resources to help you understand what to do next.

Finding the unknown unknowns?

You are already familiar with the idea of writing SQL queries to extract data from a database. Perhaps more recently you even remember having to wrap your head around how to consolidate data from a distributed data store?

But that will only answer your questions.

Say again? Of course you want answers to your questions, but what about discovering new insights via relationships you didn’t even known existed in your data? Hence, extracting data with a question you did not anticipate. For example, you may be looking for edge cases or anomalies that can only be seen when analysing multiple “hops” of a relationships in a network (e.g. friends of friends who like the same music).

Until you try some graph analytics or think through a related problem, you probably won’t really understand the power in these ideas. In many ways our SQL experience has taught us to not ask some of the harder questions because they weren’t possible to answer with SQL! I’m speaking from my own personal experience on this and how challenged I was to break out of my previous paradigm.

When SQL is a hammer…

…every data problem that can fit in a table looks like a nail. However, when a single table is full of a myriad of complex relationships, that’s when things start to get really tricky. If that data should end up on your Data Analyst’s desk, just wait for the fireworks. That is, unless the DA has graph-like querying tools available.

Let’s look at an example, the many-to-many relationships table. The table in SQL would just be two columns with names in them, representing a relationship between two people: i.e. Harry, Sally. Those from the graph world see them as two special subjects with a relationship, not two pieces of text in a table.

These two subjects may have a bidirectional relationship too. So when doing RDF querying or graph analytics, you will often be building queries to find both relationships: Harry->Knows->Sally and Sally->Knows->Harry.

You can emulate this in SQL with a self join or a second query but don’t bother unless your dataset is really simple and your questions are very superficial as you’ll only get one degree of relationships for each join – then you’ll be tempted to do 20 joins to emulate what can be much easier in a graph analysis engine.

You need graph analytics in the future

“You don’t know my business!” Yes, but we know what the common data handling needs are for most organisations. Without fail, companies, governments and non-profits alike all deal with relationship-laden data:

Customers “know” other customers – who are the key influencers in your buying community?
Donors support certain kinds of causes and share about them in social media – what other causes are gaining more traction than yours with similar types of donors?
Patients have various diagnosis that relate to other patients with similar issues – how can we predict better outcomes if certain factors of care are modified?

How are you planning to deal with such complexity in a proactive way? Your competitors (and all the Internet titans) are already using it in some way (likely to sell to you better), so it is not going away any time soon.

If you’re just getting started in understanding graph analytics, may I recommend my earlier blog post which is a mini HOWTO using the SPARQLverse analytic engine (from SPARQLcity). Install it in a couple minutes, push some simple data in and get your hands dirty with the ultra simple example there.

Also, if you don’t know some of the differences between RDF, graph data, SQL and SPARQL, it’s worth digging into. I’ll leave you with a great article by Robin Bloor on the subject. He clears the air very well in this article from Inside Analysis, here is a snippet but you should really read the whole thing as it’s very insightful:

“Where the RDF databases really score is when you want to do set processing (a la SQL) at the same time that you want to do graph processing. Consider a query such as “Who are the biggest influencers on Twitter over the past six months?”

Both the RDF and Graph database would handle such a query and return the same results quickly. But if you ask the very different question, “Which influencers have had the same pattern of influence on Twitter over the last six months?” you are asking both for graph processing and set processing at the same time to get to the answer, and the RDF databases do both well. Not only that, but this is an area of analytics, which was virtually untapped until recently, because there was no software that could easily do it.”

Follow me @1tylermitchell for further discussion or see my links in the sidebar.