The Graph theory is the main component in discrete mathematics and computer science. Understanding and decoding it is crucial for any network, a network as big as the World wide Web also called the ‘global brain’ or any multi-pronged social network for collaboration and innovation.
In any network, there are units that are linked or connected to each other. These links usually connect people, organization or social communities. In general, these links usually relate to some kind of information flow or economic transaction that happens between the connections. Cheerful to say even love flows through these connections in love relationships.
Now, if the units in that network are connected through pieces of information, then it becomes an information network. We are talking about one such network, a vast ever expanding ocean, the World Wide Web (WWW).
The fundamentals that operate in any network including the social network, operate here as well. In many ways, we can say that the way we live socially and our social network has influenced the World Wide Web. Nevertheless, the World Wide Web is a classic example of a global information network and we can also call it the ‘global brain’.
Technically, if you look at it, there is crucial underlying structure called the graph theory on which it (WWW) operates. The web as an application which connects the numerous computers (Also called, The Internet) was first created by Tim Berners-Lee during the period 1989-1991. Although, the web at that time was in its simplest of its forms, connecting merely web documents.
Experiencing the web in its present structure is mind boggling, the connected links represent some kind of a directed graph. Let’s understand what ‘Graph theory’ is all about.
Let’s understand what ‘Graph theory’ is all about.
Watch Tim Berners – lee’s talk on Ted Talks on the 25th Anniversary of the World Wide Web.
Understanding Graph theory in its very basic and simple form
Graph theory is the study of graphs within the field of discrete mathematics. Big multi-billion search engine companies like Google have built their businesses on Graph theory.
From a lame man perspective, people often get confused with the “chart” – which is a graphical representation of information (Numerical or qualitative data) over the two axis.
Here in this context, graph theory means a set of points or vertices which are connected to each other through lines or edges or arcs.
The graphs broadly are divided into two types. They are directed, where the lines point to the vertices or un-directed.
It is easy to look at it in the form of a diagram. The diagram below shows a simple graph.
A diagram of a graph
Graphs can be used to model all kinds of relationships in the real world. They are used in the physical and chemical processes as well as information systems. Most notably, graphs are used to represent a network like for example, the internet.
Graph theory is used to solve problems in social media and used in the analysis of social networks. There are “influence graphs” and “friendship graphs” within groups. Graph theory is also used to monitor and analyze rumor spreading as well celebrity popularity among others.
Graph theory can also be used to determine how people collaborate with each other. This is also called the collaboration graph. The same even applies for an innovation spark graph in a collaborative network.
A simple example
Let’s look at a simple example of how the graph theory can be applied.
As mentioned earlier, according to the “Worldwide web size” The estimated number of webpages as of August, 26th, 2016 is around 4.76 billion pages. A famous question that was asked at that time was ‘What is the diameter of the world wide web’. The answer is not thousands and thousands of miles even though it spreads across the world. It is just about 19 according to Albert-Laszlo Barabasi, Reka Albert and Hawoong Jeong of the University of Notre dame. The diameter of the web is 19.
The number 19 does not represent any astronomical distance. It is the number of “clicks”. This is a super example of the application of the graph theory of a very large graph such as the “WWW”. The web is connected through webpages. There are hypertext links which connects one page to another page. It becomes a huge enormous graph.
Identifying the shortest path
So if we take any two random pages. The question is what is the distance between them? Or in other words what is the shortest path between these two pages. How can graph theory calculation help us?
The shortest path algorithms are what giant search companies like Google use to display the search results (millions of pages) which are all relevant, in less than a second.
Barabasi’s conclusion is that you don’t have to wander around all the webpages on the earth. You just have to know the right path. The right path takes about 19 clicks and that’s all.
The way they went through is by looking at some corner portion of the web (About 0.3 percent, which is the nd.edu of Netherlands) and extrapolating it to the rest of the web. They used a robot software to do the job. The key data in the analysis is the number of inward and outward links of a webpage. A power law formulated states that there will be numerous web pages with small number of links which connect to power nodes or webpages which have thousands of inward and outward links.
Such power nodes are the key for the robot to find out the shortest path or the right path which leads to the webpage which was searched.
All in all, the shortest web path is about 19 clicks.
Such power nodes or high degree nodes were rare at that point in time, in the year 2000. Now there are thousands of such nodes. The search for the shortest right path becomes much easier and much faster.
The clever project
The clever project used the “Hubs’ and Authority” webpages concept to decode the shortest path that leads to the right webpage.
The Hubs are the giant portals with many thousands of links projecting outward from them. The authority pages are the ones with many inward links pointing to them (Because of their subject expertise or knowledge authority).
The clever project robot identified the shortest path by identifying the hubs and authorities on the ‘WWW’ and made use of them to quickly reach the right path.
Google, developed by two Stanford University graduate PhD students (The Google search engine development, was initially funded by the University) now a multi-billion dollar giant, has become so ubiquitous that people in some parts cannot live without, is pretty much developed based on the above principles.
It still serves pages to public based on weight ages given to the links of a webpage. Though it does have a text based search on the page to index it, but the recommendation to serve and rank it comes from the above principles of graph theory and the links of a webpage.
What we have seen so far is the basics of graph theory in its simplest form sans the ‘maths’. The primary component is to understand the spread of the vertices or the nodes in the graph structure. The second one is to develop an algorithm which promote its spread.
This is all for now. I would come back to visit more on this topic for later.
For further reading on this topic, please find below the resources
- A good reading in graph theory – website
- This stackoverflow.com page has got good resource links on graph theory, worth the try.
- Graph theory on Wiki
If you find this article interesting, please do share us.