Types of Graphs That Google Uses to Rank Webpages

Link Graph – The link graph model consists of nodes and edges. Suppose, if page 1 links out to 3 pages namely page 2, page 3 and page 4 respectively, then we call it as 1 node with 3 outgoing edges. Now, think of a bigger model where each page links to each other in a manner as shown in the picture below:

As per the above figure, the following structure of the graph is obtained. This is known as the link graph or the Page Rank factor which Google widely uses in its ranking algorithm. Here, node 1 has 3 links so it has 3 outgoing edges namely 2,3,4, node 2 has 2 links so it has 2 edges namely 3 and 4, node 3 has 1 link so it has 1 edge, namely 1 and similarly, node 4 has 2 links so it has 2 edges namely 3 and 1.

Now, based on the number of edges every node has, the importance of the node will get passed onto the other nodes. If a node has k edges, then the node value gets divided by 1/k of its importance to each of the node. This is shown by the graph below:

In simpler terms, this is what is known as the link graph and Google uses this graph in order to pass on the related value between the connected nodes and this value is known by the name of Page Rank.

(Note: There are certain other types of link graphs as well but the simplest of them is explained here in order to simplify the main concept. )

Co-Citation Graph – The Co-Citation graph is a measure of the relative importance of documents cited together. Suppose a document A cites 2 other documents B and C then the documents B and C are said to have a co-citation score of 1 (as they were referenced together by 1 document). Similarly if B and C are cited by 3 more documents then their co-citation score increases upto 4. The higher the co-citation value, the higher is the semantic relevancy between those documents.

In addition of co-citation score there is also a co-citation proximity Index value. This suggests that resources cited at closer proximity have a higher CPI value as compared to the resources which have a far proximity levels.

The study of citation is known as citation analysis and Google makes use of both co-citation value and CPI value in order to determine the semantic relevancy of documents. Remember that citation analysis can be done for almost anything like instead of judging semantic relevancy of documents, it can be done to judge the semantic relevancy of authors also. Learn more about Hummingbird update and semantic search relevancy.

Social Graph – Facebook has been the top researcher of the social graph concept and has been implementing it on its Graph Search Algorithm. But, Google is not lagging behind, it has also started using social graph based information in order to determine relevancy of the search queries based on the social relationships of the people.

You can think of social graph as a interconnection of social connection than an individual has. Moreover, different social connections can also be interconnected in order to deeper the cluster of this web based relationship model.

As an example, let us suppose Joydeep has 2 friends, Jack and Jill. So all 3 of them are connected with each other. Now, if Jack shares any information and if Joydeep is specifically looking for that information then Google can find and display that information in the search results. This is what happens when Google Plus results are displayed in the search results when you are logged in. This is the power of social web. Connections on the social graph might include user mail or chat contact, direct contacts on social sites like friends of friends, connections of users that have a direct connection to the user. It can also include content generated by individuals (e.g., blog posts, reviews), public relationships can be established through public profiles and/or public social networking services.

An individual who is a user in the social space has a custom graph. This social graph can include people and particular content at different degrees of separation. It might include friends, friends of friends (e.g., as defined by a user, social graphing site, or other metric), the user’s social circle, people followed by the user (e.g., subscribed blogs, feeds, or web sites), co-workers, and other specifically identified content of interest to the user (e.g., particular web sites).

Knowledge Graph – Google has got brains simply because of knowledge graph. You can think of knowledge graph as a large database of semantically related objects. For any query that includes objects, Google makes use of this graph. Suppose if I enter the query “What is the capital of Australia?”, here Australia is an object and Google has an associated knowledge graph of Australia. With the help of that graph, Google is able to determine that Australia is a country and the capital of Australia is Canberra, so amazingly Google returns the result as Canberra, without the need to visit any other resource in order to get the results. This was the major accomplishment which Google obtained with the help of knowledge graph.

Similarly for another query like “land of the rising sun”, Google returns the answer as Japan. How did Google knew that, the answer is because of the Knowledge graph. In the graph of Japan, there is reference that this country is also known as “land of the rising sun” so Google knows what to return as an answer. Intelligent huh!

It is important to note that knowledge graph is powered by Wikipedia and other similar databases of trustworthy resources. It is because of these resources especially Wikipedia that Google is able to return instant answers.

References: 


Cornell University, Page Rank Algorithm , The Mathematics of Google Search – : http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/Lecture3/lecture3.html
Filtering Social Search Results – http://www.google.com/patents/WO2013022674A1?cl=en

Also See:

How Does Google Applies Semantic Search?
Latent Semantic Indexing
Google Hummingbird Algorithm
Facebook Graph Search Optimization
Google Indepth Articles