What is a graph?

Mathematics relies on abstractions. Abstractions allow us to simplify complex real-world data into an object that is equipped with a series of rules and properties. A graph is one such example of an abstraction that allows us to represent pairwise relational data in a simple, yet powerful, abstraction.

Before unpacking that last statement, let’s cast this abstraction into a real-world problem so that we have some context. A social network is made up of individuals who connect with their friends and colleagues by following or befriending one another. This data is therefore relational.

Social network graph

In the graph above we can see the interaction structure of six people. We might infer that two groups are present: {Marta, Liam, Adam, Lara} and {Eva, Beth, Liam}. Further, Liam is present in both groups, so Liam could be seen as an important person in this graph as he connects two groups of individuals.

Technically speaking, graphs are defined by a set of vertices (sometimes called nodes) and edges. A vertex represents an individual element of the graph e.g., Liam, whilst an edge encodes a relationship between any pair of vertices e.g., the edge connecting Liam and Lara.

Earlier we mentioned that graphs describe pairwise relationships. To see this, consider the sub-graph of Liam-Eva-Beth. We can see that Liam and Eva are connected, as are Eva and Beth, and Beth and Liam. These are pairs of relationships. However, we have no idea if Liam, Eva, and Beth are all friends as a group though as this would be a third-order interaction. To model these types of relationships, one would need to use a hypergraph

Graphs are incredibly powerful objects. The number of ways in which a graph can be used to draw insights is endless, but more on that in the next atomic essay.