English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGraphs and NetworksGraphs in Everyday Life
We have seen many different applications of graph theory in the previous chapters, although some of them were a bit contrived. However, it turns out that graphs are at the very foundation of many objects, concepts and processes in everyday life.
The Internet, for example, is a vast, virtual graph. Every vertex is an individual webpage, and every edge means that there is a hyperlink between two pages. Note that links only go one way, so this graph is
Some websites, like Wikipedia or Facebook, have lots of incoming links, while many smaller websites may have very few incoming links. This is the underlying concept which Google uses to sort search results.
Websites with more incoming links tend to be of higher quality and should be shown at the top of the search results. For example, when searching for “London”, official tourist information sites are shown before small shops in London, or blogs of people who live in London. This simple idea from graph theory, the Page Rank Algorithm, made Google much better than other early search engines.
The Internet is the largest network ever created by mankind. This image shows a very small proportion of all the servers connected to the Internet:
While websites and hyperlinks form a virtual graph, there is also the physical network of computers, servers, routers, phone lines and cables.
Every time you make a phone call or load a website, network operators have to find a way to connect sender and receiver, without exceeding the capacity of any individual cable or connection. Graph theory and probability make it possible to guarantee a reliable service, for example by finding diversions when a particular connection is busy.
Graphs also play an important role in transportation and navigation. All flight, train and subway networks form graphs, which can be used when creating efficient schedules. One of the most recognisable graphs is the London Underground map:
All roads and motorways also form a large network, which is used by navigation services like Google Maps when working out the shortest route between two given points.
In the future, Intelligent Transportation Systems will reduce congestion and accidents by routing cars more efficiently, using location data collected from smartphones and self-driving cars. This could save millions of hours lost on the road every year, significantly reduce pollution, and allow emergency services to travel faster.
This image shows the network of commercial airline flights across northern Europe.
There are countless other graphs in science, engineering or everyday life:
The links between atoms in molecules and crystal grids form a graph.
The spread of diseases and epidemics can be modelled using a network.
In Biology, the evolutionary trees that show the ancestry of species form a graph.
The different components of electric circuits and computer chips form a network.
The grammatical structure of languages can be modelled using graphs, for example to create translation algorithms.
Graphs also have many applications in probability, game theory and financial mathematics.
Social Networks
Finally, let us think about one particularly good example of graphs which exist in everyday life: social media. Here, vertices represent
When we draw social media graphs, we might see certain clusters of mutual friends, who may have gone to the same school or live in the same city. We can also determine people’s centrality, which depends on how well-connected a vertex is, and which may be a measure of a person’s popularity on social media.
In 2014, Facebook had 1.4 billion active users and a total of more than 200 billion friendships. Half of all Facebook users have more than 200 friends, and since most of our friends have a similar number of friends, we could easily have tens of thousands of friends of friends.
An exciting question would now be: if you pick any two random Facebook users, how many “friendship edges” would you need to follow to get from one to the other? For example, the distance between friends is
In 2016, Facebook conducted a study to determine how its users are connected to each other. They found that, on average, you are connected to anyone else on Facebook through at most 3.57 other people. And this includes celebrities, politicians or even royalty!
In other words, if you pick any one of the billions of Facebook users all around the world, they will probably have a friend of a friend who knows a friend of one of your friends. We say there are 3.57 degrees of separation.
Geographic visualisation of all Facebook friendships in 2010.
In 1929, when the Hungarian author
In 1967,
Today, every one of us is part of countless invisible graphs, which underlie our social interactions, travel, Internet and technology, science, and so much more.