An introduction to graph theory

By Gordon Rugg

Graph theory is an extremely powerful approach that is based on a handful of elegantly simple concepts. It was invented by Euler in the 1740s, and is a central part of modern mathematics and technology. Among other things, it plays a key role in handling traffic on the Internet.

It’s invaluable for representing knowledge, because it combines flexibility with formalism. In particular, it’s useful for representing different facets and viewpoints; for representing hierarchies of goals and values; for representing successive layers of explanations; and for formal taxonomies.

The core concepts are arcs and nodes (also sometimes known as edges and vertices respectively). Nodes are points that are connected by arcs. Here’s a simple example.

Even this simple example shows how the representation captures key features of the relationships between the nodes. Node A is directly connected both to node B and to node C; node B and node C are not directly connected to each other, and are connected only indirectly, via node A.

This approach is widely used for the study of social networks. A common finding is that some members of a social network have a disproportionately large number of connections, and play a correspondingly important role as gatekeepers and as go-betweens. The illustration below shows what this looks like; the person represented by node C has a much larger number of contacts than any of the others in this network.

An obvious problem when representing social networks is that some of the connections will be stronger than others, in terms of how frequently two individuals interact, or how strong the type of interaction is, etc. This can be handled within graph theory by graph colouring, where the arcs and/or nodes are annotated in some way to show the strength of a connection. The annotation may take the form of colour, or of line thickness, or a numeric label, or of other representations.

The illustration below shows this principle applied to the same hypothetical social network as in the previous diagram, with the strength of each connection represented by the thickness of the corresponding arc. Person C has some very strong connections, and also one very weak connection, to person E, who doesn’t have any other connections.

The examples so far involve graphs where paths diverge and re-converge. In graph theory terminology, these are known as nets. In another form of graph, once paths diverge, they never re-converge. These are known as trees.

Trees are the basis of hierarchical diagrams, and of most taxonomic systems of classification.

In some of our work, we’ve looked at what happens when you unpack explanations using graph theory, systematically unpacking the explanations of the explanations. It turns out that usually you get a tree rather than a net; the explanations end up bottoming out in a few types of explanation such as named shapes, or colours, or numbers, where the person can show you precisely what they mean. This is invaluable for unpacking what someone means by subjective terms or technical terms. The illustration below shows schematically the bottoming out level for a set of explanations, with the bottoming-out nodes in black.

Graph theory is also useful as a way of representing facet theory, where you use two or more different ways of categorising the same area from different perspectives. We’ve published a separate blog article on this concept. It’s an invaluable way of structuring classifications of a topic neatly and systematically.

The illustration below shows the basic principle, with classifications of cars using two different facets, of cost and place of manufacture. The facet of cost groups the green car with the yellow car, and the red car with the purple car; the facet of place of manufacture groups the same cars in a completely different way. Both classifications are sensible and internally consistent, but this would be lost if you incautiously analysed the same data with a statistical approach that tried to crunch the similarities down into a single measure of statistical distance between each pair of cars.

Cost                                 Place of manufacture

When knowledge is represented using graph theory, you can use a wide range of qualitative and quantitative forms of analysis. For instance, you can count the shortest route between two nodes (which is a central concept of Internet traffic management, but can also be applied to e.g. measures of social distance). You can count the number of arcs and the number of nodes; you can count the average number of arcs per node, as a measure of the connectedness of a graph. If you’re assessing expertise, then you can represent the person’s categorisations and their explanations using graphs, and see where the resulting graphs are richly structured compared to where the graphs are sparsely structured, potentially indicating knowledge gaps.

The graph below shows evenly structured knowledge, which is a typical pattern for well-developed expertise.

The graph below shows unevenly structured knowledge, more typical of a novice or of a hobbyist with narrow interests. (Both this and the previous graph are simplified for clarity; real examples typically contain some more information in novice graphs and much more information in the expert graphs.)

A closing thought for mathematical readers: Graph theory generally assumes crisp divisions between entities. We’ve been looking into graphical ways of combining graphs with fuzzy logic. This is showing potential for helping public understanding of science, in particular with regard to speciation in zoology, where the speciation process is often fuzzy rather than crisp. We’ll write more about this in later articles.

So, in conclusion, graph theory is a powerful, elegant and simple approach. We use it a lot in our work, particularly in conjunction with laddering, which is a systematic way of eliciting knowledge that’s structured into trees. We’ll be blogging about laddering in a later article.

Notes:

If you’re keen on history and/or mathematics, there’s an archive of Euler’s work on the Dartmouth University  website. His original graph theory paper is here: http://www.math.dartmouth.edu/~euler/pages/E053.html

For a facsimile of his original article, in Latin, you need to follow this link on that page: Original publication: E053 (in the Commentarii), Volume 8.

The Dartmouth site also contains links to translations of his original article.

There are a lot of online tutorials about graph theory, but some of them jump very rapidly from the very basic concepts into advanced heavy-duty maths.

One of the best books on the subject is by Ore, entitled Theory of Graphs. It’s on Google books. Although it’s sixty years old, it’s still good, and still regularly recommended as an introductory text.

Advertisement