Can you find a path that crosses every bridge once and only once? Image: Bogdan Giuşcă.
One of our favourite maths problems is called the bridges of Königsberg. It involves finding a path on an 18th century map of the city of Königsberg that crosses each of its seven bridges once and only once — or proving that there isn't one. We love the problem because its solution, provided by Leonhard Euler in 1736, is elegant and simple, just what a good solution should be (see here). But that's not all there is to it. Euler's solution also laid the foundation for an area of maths that couldn't be more relevant to modern life: network theory. Here's why.
A network (also known as a graph) is a collection of nodes connected up by links (in the bridges problem the nodes would represent the bits of land and the links between them the connecting bridges). Networks are absolutely everywhere. We live in social networks, travel along road and rail networks, and rely on telephone networks and utility networks that deliver power or water. Our computers and phones are hooked up to that vast network called the internet; rivalled in complexity only by the network of neurons in our brains, which enables us to produce all these complex structures in the first place.
Those networks are large and complex, but mathematical study has revealed interesting features that can help us understand, protect, or even break them. One such feature has become famous as the "six degrees of Kevin Bacon". The idea is that if you link two actors that have appeared in the same movie, then every actor, no matter how obscure and unimportant, is only six links away from the Hollywood star Kevin Bacon.
Partial map of the internet based on 2005 data. Image courtesy the Opte project.
Behind this strange "fact" is the concept of small world networks. A small world network is one in which the average distance between any two nodes (where distance is counted in the number of links that connect two nodes) is small and in which there also is a lot of local clustering: if two nodes are connected, then so are their other immediate neighbours.
Many real life networks, including social networks, the internet, and networks in our brain, have been found to be small world networks. You can see how this feature might evolve. For example, if two people know each other (so they are represented by two nodes with a link between them) then their friends also tend to know each other, so the network representing acquaintances between people has a high degree of local clustering. But through work, hobbies, or random chance, people also make connections to people in other local clusters. These long-range connection mean that any two people in the network, even if they move in very different circles, are separated by surprisingly few links. For networks that perform a useful function, like utility networks or the neural networks in our brain, the small world feature is very useful. It means that tasks can be performed efficiently both at a local level and distributed between clusters.
Another feature often found in networks is that they contain a few extremely well-connected hubs: these are nodes that have many more links than the majority of others. You can also see how they might evolve. If a new person joins a social network they tend to do so via someone who is already popular. Similarly it makes sense to link a railway station in a small town to the nearest railway hub. This means that nodes with many connections tend to accumulate more, so hubs develop naturally.
A large class of networks, which are called scale-free networks, contain such hubs. The difference between these and those with evenly distributed links is that they behave very differently when they are under stress which causes individual nodes to drop out or fail. This could happen by police arresting terrorists in a terrorist network, doctors immunising people against a disease in a "disease network", or by internal congestion for example in a traffic or computer network. If you eliminate nodes of a scale free network at random, then the network will remain pretty much unharmed for a long time, because the chance that you happen to take out one of the highly connected hubs is low. By contrast, a network with evenly distributed degrees will fall apart quite quickly.
If, however, you know what you are doing, you can completely paralyse a scale free network by simply taking out a very small number of highly connected nodes. By analysing the structure of a network mathematically, you can figure out how to disrupt a network you don't want, to stop terrorists or the spread of a disease, or how to protect those you do want to perform well, such as the internet or a neural network in a person's brain.
The London Underground map.
One hugely important insight from the mathematics of networks, which also helped Leonhard Euler solve the bridges problem, is that it often helps to forget how a network is arranged in space and concentrate on the links between nodes. A great example of this is the London tube map. Geographically it is woefully incorrect as it distorts distances between stations and pretends that lines run along neat straight lines, which they don't. But this distorted lay-out is exactly what makes the map so easy to read: were it correct you would see all the central London stations cramped together in the middle, so that the far-away ones still fit in, and they’d all be connected by a tangled mess of lines. The London tube map is a topological map, after an area of maths called topology which concentrates on the connectivity of a shape rather than its precise geometry. Euler did just that when he solved the bridges problem, so he can also be credited with laying the foundations for topology.
Whether you are trying to make friends, fight terrorists, improve internet connections or travel around London, look to mathematics to help you along!
You can read more about graphs and networks on Plus.