Skip to main content

Google Page ranking : One application of Markov chain Model



The biggest and widely used search engine on the web today is Google. Every second it meets queries by millions of internet users and provides answers.  There are millions of pages available in the web server and among these all pages the search engine needs to return the page based on the user’s need. This is properly done by using Google page Ranking. PageRank was developed by  Larry Page and Sergey Brin  in 1996 as a part of a research project about a new kind of search engine at Stanford University . This technique is used by Google to rank web pages according to their importance, link popularity: a page is ranked higher if there are more links to it. While a query for a particular web page is made by one internet user, Google search algorithm compiles the PageRank scores using PageRank algorithm and returns the web pages depending on the score of each page. In the PageRank algorithms the webs are considered as a directed graph in which nodes represent the pages and edges represent the hyperlinks in the page.
Apart from the basic PageRank method, Google also uses other techniques like Markov chain model to compute the score of each web page and based on the score it determines the order of the pages in which it should be listed in search results.


The concept of Markov dependence was first introduced by the Russian mathematician Andrei Andreivich  Markov (1856-1922) , to predict the behaviour of a system that makes a transition from one state to another. Markov chain is a random process where all information about the future is contained in the present state and not on the past to determine the future. Markov model has wide application in various fields such as genetics, economics, marketing, finance and in many more. One of the most recent internet applications of Markov model is PageRank of a webpage, used by Google. A random surfer while surfing the web may be selecting one page and going to other pages randomly by choosing a hyperlink (outgoing link) from that page. Or it may be the case that the surfer may be going to a page from where there are no outgoing links.  So the surfer chooses a random page from the web. This kind of random walk is known as Markov chain or Markov process. This limiting probability that a random surfer visits any particular page is its page Rank.


[Ref: http://blog.kleinproject.org/?p=280]
A simple web with five pages named ,  ,  ,  , and  . The directed lines are the hyperlinks.  For example if we are on page  , then there is only one link to page  , while, if we are on page  , we find three links, and we can choose to move to either page  , or  , or  .
                           
Dr. Jhumpa Bhadra
Assistant Professor
Department of Mathematics
Heritage Institute of Technology


References :
1. Pagerank Beyond The Web David F. Gleich [ arXiv:1407.5107v1]
2. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine. Comput. Netw. ISDN Syst., 30 (1-7), pp. 107–117, 1998.

Comments

Post a Comment

Popular posts from this blog

The God Particle

                      'The God particle' also known as Higgs boson particle was discovered in 2013, with the help of the Hadron collider. It was said to be “the missing cornerstone of particle physics” by the CERN director.         Many disputes have been over why this is named so. Basically this particle gives an explanation of the origin of the universe.  It is a physical proof of an invisible, universe wide field which gave mass to all particles after the Big Bang.         This field better known as the “Higg's field” is different from all other fields as it is present everywhere even in vacuum. Now after providing mass it forced all particles to merge and form the stars, planets and led to the formation of the whole Milky Way galaxy.          So it was a very essential particle leading to the origin of the universe and gradua...
10 comments
Read more

HYPERLOOP

FIFTH MODE OF TRANSPORTATION-“HYPERLOOP” The concept of Hyperloop was first conceived in 2012 by renowned entrepreneur and founder of SpaceX and TESLA, Elon Musk . He was in search of a new, the fifth mode of transportation which can redefine the future of travelling by drastically reducing the travel time on land. It is termed hyperloop as it would go in a loop. Hyperloop is the greatest leap in mode of transportation infrastructure for generations. With passengers sitting in a pod and travelling through evacuated sealed metal tubes at a speed greater than that of an airline, the concept seems to be fictitious but it is on the verge of becoming reality. The speed of conventional mode of transportation i.e. buses, cars or trains is limited by air resistance and friction.   Hyperloop drastically reduces friction and air resistance by means of magnetic levitation, electric Propulsion and partially vacuum steel tubes. The concept is open-sourced by Elon Musk, the result of...
12 comments
Read more

NEUROIMAGING IN IDENTIFYING DISORDERS

NEUROIMAGING IN IDENTIFYING DISORDERS Neuroimaging deals with the in vivo applications of various techniques to illustrate and study the structural & functional characteristics of the nervous system. Neuroimaging can be classified into two categories: • Structural neuroimaging, which involves the imaging of the structure of the nervous system and the diagnosis of intracranial injuries and tumours. • Functional imaging, which involves the study and diagnosis of metabolic diseases and cognitive research. The most widely used techniques involved in the process of neuroimaging are: 1. Computed Tomography (CT) or Computed Axial Tomography (CAT), in which X-ray images of the brain from various directions are taken and presented as cross-sections of the brain. 2. Magnetic Resonance Imaging (MRI), which uses magnetic fields and radio waves to obtain high-resolution 2D or 3D images of the brain. 3. Positron Emission Tomography (PET), which measures emissions from radioac...
3 comments
Read more