What are Graphs? A Modern Perspective
Graphs and network science have held sway over me for the last 7 years because they are the best avenues for understanding and modeling our complex world.
I’m often asked, “what’s a graph?” After years of launching into tediously interesting detail, I realize most people are searching to understand the modern implications. In honor of the founder of graph theory, Leonhard Euler, who was born on April 15, 1707 (just a wee bit of tedium!), the below is an attempt to answer that question from a contemporary perspective.
This is an excerpt from work that Mark Needham and I created a few years ago in the book “Graph Algorithms,” published by O’Reilly Media, Inc. copyright 2019.
________________________________________________________________
What Are Graphs?
Graphs have a history dating back to 1736, when Leonhard Euler solved the “Seven Bridges of Königsberg” problem. The problem asked whether it was possible to visit all four areas of a city connected by seven bridges, while only crossing each bridge once. It wasn’t.
With the insight that only the connections themselves were relevant, Euler set the groundwork for graph theory and its mathematics. Figure 1–1 depicts Euler’s progression with one of his original sketches, from the paper “Solutio problematis ad geome‐ triam situs pertinentis”.
While graphs originated in mathematics, they are also a pragmatic and high fidelity way of modeling and analyzing data. The objects that make up a graph are called nodes or vertices and the links between them are known as relationships, links, or edges. We use the terms nodes and relationships in this book: you can think of nodes as the nouns in sentences, and relationships as verbs giving context to the nodes. To avoid any confusion, the graphs we talk about in this book have nothing to do with graphing equations or charts as in Figure 1–2.
Looking at the person graph in Figure 1–2, we can easily construct several sentences which describe it. For example, person A lives with person B who owns a car, and person A drives a car that person B owns. This modeling approach is compelling because it maps easily to the real world and is very “whiteboard friendly.” This helps align data modeling and analysis.
But modeling graphs is only half the story. We might also want to process them to reveal insight that isn’t immediately obvious. This is the domain of graph algorithms.
What Are Graph Analytics and Algorithms?
Graph algorithms are a subset of tools for graph analytics. Graph analytics is something we do — it’s the use of any graph-based approach to analyze connected data. There are various methods we could use: we might query the graph data, use basic statistics, visually explore the graphs, or incorporate graphs into our machine learn‐ ing tasks. Graph pattern–based querying is often used for local data analysis, whereas graph computational algorithms usually refer to more global and iterative analysis. Although there is overlap in how these types of analysis can be employed, we use the term graph algorithms to refer to the latter, more computational analytics and data science uses.
Graph algorithms provide one of the most potent approaches to analyzing connected data because their mathematical calculations are specifically built to operate on relationships. They describe steps to be taken to process a graph to discover its general qualities or specific quantities. Based on the mathematics of graph theory, graph algorithms use the relationships between nodes to infer the organization and dynamics of complex systems. Network scientists use these algorithms to uncover hidden information, test hypotheses, and make predictions about behavior.
Graph algorithms have widespread potential, from preventing fraud and optimizing call routing to predicting the spread of the flu. For instance, we might want to score particular nodes that could correspond to overload conditions in a power system. Or we might like to discover groupings in the graph which correspond to congestion in a transport system.
In fact, in 2010 US air travel systems experienced two serious events involving multiple congested airports that were later studied using graph analytics. Network scientists P. Fleurquin, J. J. Ramasco, and V. M. Eguíluz used graph algorithms to confirm the events as part of systematic cascading delays and use this information for corrective advice, as described in their paper, “Systemic Delay Propagation in the US Airport Network”.
To visualize the network underpinning air transportation Figure 1–3 was created by Martin Grandjean for his article, “Connected World: Untangling the Air Traffic Network”. This illustration clearly shows the highly connected structure of air transportation clusters. Many transportation systems exhibit a concentrated distribution of links with clear hub-and-spoke patterns that influence delays.
Graphs also help uncover how very small interactions and dynamics lead to global mutations. They tie together the micro and macro scales by representing exactly which things are interacting within global structures. These associations are used to forecast behavior and determine missing links. Figure 1–4 is a foodweb of grassland species interactions that used graph analysis to evaluate the hierarchical organization and species interactions and then predict missing relationships, as detailed in the paper by A. Clauset, C. Moore, and M. E. J. Newman, “Hierarchical Structure and the Prediction of Missing Links in Network”.
________________________________________________________________
I hope that provides a little background to graphs and why so many of us are obsessed with them. Happy birthday Euler and long live graphs!
