# From disease to data, it’s a small, networked world

## That’s Maths: Graph theory interprets the world as a series of nodes and their links, which aids greater understanding of networks

Networks are everywhere. They may be physical constructs, like the transport system or power grid, or more abstract entities, such as family trees or the worldwide web. A network is a collection of nodes linked together, like cities connected by roads or people genetically related to each other. Such a system of nodes and links is what mathematicians call a graph.

Graph theory underlies the analysis of networks. A graph can be depicted by drawing dots for the nodes and lines for links between nodes. The map of the London Underground is a good example of a graph. Mathematically, a graph can be represented by a large array of numbers called an adjacency matrix, with ones for links between nodes and zeros elsewhere. In a computer, the graph is stored as a list or a matrix. A list is smaller, saving memory, but a matrix allows faster access.

Many physical systems can be modelled by graphs. For example, the internet is a graph whose nodes are computers and whose links are communication channels between them. Graph theory has widespread applications in chemistry, electronics, computer science, economics, biology and sociology and many other disciplines in addition to mathematics itself. It is valuable in understanding the behaviour of complex systems and can be used to predict the effects of changes in their structure.

#### Cluster coefficients

We can define the distance between nodes as the smallest number of links needed to connect them. The maximum distance is called the diameter of the graph. The graph density is the ratio of the number of links to the maximum possible number. If it is low, the graph is called sparse, and efficient algorithms are available for its analysis. Sub-graphs can be identified using measures called cluster coefficients. In a social network, people with common interests may form a cluster or clique.