Introducing Capgemini’s UK Graph Guild

Publish date:

“The origins of graph theory are humble, even frivolous.” Norman L Biggs

I am pleased to announce the launch of Capgemini’s “Graph Guild” in the UK, which is a new initiative dedicated to helping clients understand and apply graph databases, graph algorithms and graph visualisations to solve real world problems.

Figure 1 : A graph of a mathematical function
Image reference: Shutterstock

So what are “graphs” and why are they important?  If I were to ask “what is a graph”, I suspect most people would imagine something like a chart in Excel, with perhaps a handful of people thinking of a real analytical mathematical function.

Whilst such answers are to be expected, in mathematics there is another kind of graph which at first sight may seem rather abstract, but as I hope to show is really very natural and which we all unknowingly use every day.  For our purposes, a “graph” is a structure comprising of:

Figure 2: An example of a graph, called the “Petersen graph”.
Image reference:Shutterstock

 

  • A set of nodes; and
  • A set of edges, where an edge connects one node to another. An edge between two nodes only exists if there is a relationship (of some sort) between them.

 

 

Examples and applications of graphs

Figure 3: A mind-map is a graph
Image reference:Shutterstock

Whilst the above definition is perhaps new or rather abstract, nevertheless we all subconsciously think in a “graphy” manner every day of our lives.  Our ruminations are best illustrated using “mind-maps”, a picture used to describe our thought processes about, well, anything really; from how to tackle a task, to studying for an exam, or brainstorming ideas.

 

 

 

Figure 4: Asking for directions is “graph speak”
Image reference: Shutterstock

If we subconsciously think in a “graphy” manner, then it should be no surprise that without realising it we also talk and behave in a “graphy” manner.  For example, every time we use any travel network, whether it is the railway or the roads, we actively traverse a graph, and whenever we ask for directions we are asking a graph based question.

 

 

 

The use of graphs is not restricted to mind-maps and travel networks, but it has diverse and almost endless applications, including:

  • Understanding the structure of molecules and chemical compounds
  • Modelling connections, communities and influencers in social media networks
  • In biology and conservation, to track where certain species live and migration paths
  • In operational research, finding the shortest route from one point to another
  • In finance, detecting credit card and other financial fraud, such as suspicious activity with cryptocurrencies

A rather different but very practical application of graphs is in the security of buildings.  For example, suppose there is a very weirdly shaped art gallery housing some of the world’s finest art work.  As security and costs are key concerns, high-tech security cameras (equipped with 360 degree fields of view) are to be installed to monitor every part of the gallery but in such a way that costs are minimised.  The question becomes: if all the walls of the art gallery are straight (so no curves) what is the least number of such security cameras needed so that the entire gallery can be monitored?

Figure 5: An oddly shaped art gallery
Figure 5: An oddly shaped art gallery

This problem was solved by Václav Chvátal who proved that at most ⌊n⁄3⌋ cameras are needed to monitor any simple n-sided polygon.  So, if the art gallery were shaped as in  Figure 5, then no more than 5 cameras are needed – which is somewhat surprising given there are 15 walls and the irregular shape of the gallery.  Rather than being an abstract idea, real-life examples of this can be seen in the floor plans of the art galleries designed by Frank Gehry.  In addition, related applications include the design of algorithms to search terrains and robot-motion planning such as automatic vacuum cleaners.

Graph database or Relational database?

As is hopefully now evident, there are many situations in which the questions that we are interested in answering are best served by graphs.  It is the power of graphs that has given rise over the last 20 or so years to a diverse ecosystem of graph databases, graph query languages and graph visualisation tools.

As graph databases are relatively new, a common misconception is that graph databases are much harder to use than traditional relational databases.  In fact, often the opposite is true, for whilst traditional relational databases can be used to store exactly the same data, and in theory (at least) answer the same types of problems mentioned above, in practice using a relational database is often very difficult and inefficient.

In fact, to answer almost any question of real interest using a relational database, it involves brute forcing a primitive graph structure between the tables – this is exactly what happens when a “join” is created between tables via foreign keys as it creates a relationship between them.  Further, despite the advances in computer memory and faster processors, the performance of relational databases when executing complex queries involving multiple joins is very poor.  In contrast, graph databases store not only the data but they also store the relationships, providing far superior query performance.

Figure 6:  Wrong tool for the job
Image reference: Shutterstock

Whilst relational databases can be used to answer graph type questions, it is rather perverse that we force them to behave like graph databases yet without the performance and other benefits graph databases provide.  It’s akin to using a tiny axe to fell a redwood – it’s possible but exceptionally difficult and rather impractical.

Although there are numerous use cases and other benefits to graph databases, I do not believe that graph databases are a replacement to relational databases.  Instead, graph databases should be viewed as a necessary addition and complement to them.  Indeed, there are still specific use cases where relational databases do currently outperform graph databases, such as certain types of aggregation.

How we can help

If you would like to know more about graph databases, graph algorithms and visualisations, and discover how they can be used, then Capgemini’s UK Graph Guild is well placed to help and advise you.  Please do email me  at calum.chalmers@capgemini.com  if you want to find out more, or if you have a graph or other data science question.

 

Author


Calum Chalmers

Calum Chalmers is a senior data scientist in the Insights & Data practice, with over 20 years’ analytical and machine learning experience.  He first fell in love with graph theory when studying mathematics at Glasgow University and at the University of Warwick.

Related Posts

Insights and Data

Flexible working in challenging times

Date icon June 25, 2020

Chris Withington, Senior Solution Architect in SAP BI & Analytics discusses why Capgemini...