Skip to content

The Underbelly of the Graph

Share on facebook
Facebook
Share on twitter
Twitter
Share on linkedin
LinkedIn

How does Facebook suggest new long lost friends? And, how does Google get your searches right so often. The answer is Graph Theory, an area of mathematics being investigated by Prof. Josef Lauri. Dr Claude Bajada finds out more.

A mathematician sits alone at his desk. Hunched over a stack of papers he plays with numbers as a child would work at a jigsaw puzzle. The scene dematerialises in front of your eyes. A new reality builds up. People are connected to one another by virtual links. They have access to every convenience at the click of a button. Computers know their likes and dislikes. Algorithms find cures for diseases. Security agencies know your every step. The world is safe. The world is good. There is nowhere to hide.

As I interview mathematician Prof. Josef Lauri (University of Malta), these thoughts race through my mind. Lauri works on Graph Theory, which involves solving complex puzzles. He starts the interview by drawing an odd shape on a blank piece of paper; dots with lines connecting them. While drawing and explaining a particularly difficult problem he is tackling, Lauri tells me that his fondness for Graph Theory is akin to his son’s passion for the football players Lionel Messi and Cristiano Ronaldo. ‘Neither of them have solved any medical problem, but they have made a lot of people happy.’ Abstract mathematical problems make pure mathematicians like Lauri happy. But the difference between a goal by Messi and a puzzle of the pure mathematician is that the joys of the mathematician can change the world.

Leonhard Euler established Graph Theory in 1737. Like Lauri, Euler set out to solve a puzzle. Königsberg (now Kaliningrad, part of Russia) was a city with two islands and seven bridges. Was it possible to walk through the city using each bridge only once? Euler created a mathematical description of the way objects (land) related to one another (bridges). We use the term ‘node’ to describe the land areas in Königsberg and the term ‘edge’ to describe the bridges. By abstracting the problem into a mathematical framework, Euler was able to prove that there was no way of taking the suggested path. More importantly, this solution allowed other problems to be solved.

Computers revolutionised Graph Theory. Until then, it was ‘a specialised subject with no applications. The applications of mathematics were oriented towards the physical sciences,’ says Lauri. But in 1996 a paradigm shift occurred. Larry Page and Sergey Brin used Graph Theory to organise the world wide web. They developed PageRank and Google was born. In the old days, search engines ranked pages by the amount of keywords present on that page. If someone looked up the phrase ‘Think magazine’ on the Internet, search engines would crawl the web looking for websites that contained those keyword. The search engine assumed that the page that used that phrase the most was the most important result. A problem with this method was that a site that contains a keyword many times was not necessarily the most important site. Spammers could pad their site with keywords of their choice and appear high on the ranking. Brin and Page’s new algorithm ranked websites (the nodes of their graph) according to the number of other sites that linked to them (the edges). Lauri tells me that to understand the way this is done one needs to learn about fancy things like eigenvectors, but PageRank, like much in Graph Theory, is simple to understand: a page is important if other important pages link to it.

Like Google, other Internet companies have seen value in using Graph Theory. Facebook and LinkedIn create social networks, in other words, social graphs. Each person is a node and a ‘friendship’ is an edge. Many people have experienced looking up an old school friend on Facebook. The site then starts recommending other people from your class. An algorithm tailors its suggestions to your specific situation by using your social graph. ‘It looks simplistic but it is amazing how well it works, you can see it yourself!’ exclaims Lauri. In this way advertising is becoming personalised. Digital assistants such as Siri, Cortana, and Google Now suggest new movies for you to watch using the same principles that underlie Lauri’s puzzles. Sociologists caught the bug before the modern day Internet giants. They have been analysing sociograms since the 1930s. They analyse social problems by looking for abnormal network structure. The reach of Graph Theory has been immense, scientists now use Graph Theory to analyse medical data and find new ways of curing diseases.

Governments have jumped on the bandwagon. They use Graph Theory for public security. In 2001, the National Security Agency (NSA) started collecting metadata from US telephone calls. This allowed them to build a communications network that is like a Facebook friendship network. Imagine having access to everyone’s Facebook network. NSA have access to this level of information. The NSA analyses this data using Graph Theory coupled with raw computing power. The agency can then root out suspected criminals and prevent terrorist activity. But, there is always collateral damage. Using the mathematics of Graph Theory, governments know a lot more about their citizens than ever before.

As the interview ends, the dystopic visions disassemble. Once again, I see the pure mathematician sitting in front of me. The interview has opened a door to perceive both the amazing and scary applications of Lauri’s work. When I leave the room I cannot help but think: all the giants of our modern world, Facebook, Google, and NSA, are standing high on the shoulders of the work of pure mathematicians.


What is Graph Theory?

Graph Theory is a branch of Mathematics that describes how networks work. Networks are basically the relationship of a group of separate objects to one another. For example, five objects labeled as 1, 2, 3, 4, 5 can interact as follows:

Graph1

Each of the objects are called vertices or nodes. The lines that connect them are called edges or links. This graph can then be used to describe many different types of networks. For example, the nodes could represent people and the edges may be friendships. Alternatively they could be websites and weblinks. The way the graph is drawn does not matter as long as the connections are the same.

Graph2

The graph can either be described as it is, or more often, it can be transformed into a matrix in order to do more complicated mathematics on it. This can identify which node is more important (a hub) or which group of nodes belong to the same group (or cluster). For example, in Think magazine’s facebook network. The University of Malta page is a hub in the same cluster as Think’s page.


Further reading
  • Barabasi, A. (2015). Network Science. [online] Barabasi.com. Available here.
  • Brin, S. and Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1-7), pp.107-117.
  • Seven Bridges of Königsberg – Woodside High School. (2013). Video available here

More to Explore

Adrift at Sea: Laws, Morals, and Policies in Malta’s Search and Rescue Region

Since 2016, EU member states have scaled down search and rescue operations that save lives at sea and replaced them with policies intended to reduce the number of migrant arrivals to Europe. These policies of non-assistance and forced returns to Libya render the central Mediterranean one of the world’s deadliest border spaces and force asylum seekers back to a war zone where inhuman and degrading treatment is well-documented. A growing network of civil society organisations continues to challenge these policies in the courts, on the streets, and at sea. This article, the second in a two-part series on migration, is based in part on interviews conducted with Dr Omar Grech, Senior Lecturer in International Law at the University of Malta (UM), Dr Derek Lutterbeck, Deputy Director at the Mediterranean Academy of Diplomatic Studies at UM, and Dr Felicity Attard, expert in International and Maritime Security Law at the Faculty of Laws at UM.

Concentration Camps in Libya

Following the NATO-backed overthrow of Muammar Gaddafi in 2011, Libya descended into a decade of disunity and violence resulting in incalculable suffering and loss of life. Today, much of the country remains a war zone, and migrants in EU-sponsored Libyan detention facilities continue to suffer well-documented, gross human rights violations. This article, the first in a two-part series on migration, is based in part on interviews conducted with Dr Omar Grech, Senior Lecturer in International Law at the University of Malta (UM); Dr Derek Lutterbeck, Deputy Director at the Mediterranean Academy of Diplomatic Studies at UM; and Dr Felicity Attard, expert in International and Maritime Security Law at the Faculty of Laws at UM. 

No comment yet, add your voice below!


Add a Comment