Graph theory

Graph theory is based on two key concepts, namely arcs and nodes (also known as edges and vertices respectively). An arc is a line connecting two nodes, as in the example below.

A hierarchical graph where the branches never re-join, as in the example below on the left, is known as a tree. A graph where branches re-join, as in the example on the right, is known as a net.

The arcs in a graph can be weighted, for example to show likelihood of a connection, as on the left below. They can also be either undirected (as on the left below) or directed, as on the right, where the arrowheads on the arcs show the direction of a connection.

Nets

Graph theory 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 or 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.

Graph theory makes it possible to model complex relationships, and to quantify the complexity by e.g. counting the number of arcs within a graph.

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.

Trees

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

You can use graph theory to systematically unpack explanations, and then unpack the explanations of the explanations. 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, colours, or numbers, where a participant can show you precisely what they mean. This is invaluable for unpacking what someone means when they use subjective 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. It’s invaluable for structuring classifications of a topic neatly and systematically.

Facets

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 insight could be lost with a statistical approach that crunched different similarities down into a single measure of statistical distance between each pair of cars.

Analysis

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.