Graph theory in Search engines and web connectivity.pptx

Search Engine Algorithms (PageRank algorithm)
Search engines such as Google let us navigate through the World Wide Web without a problem. Once a query is made to search a specific set of words, the engine looks for websites that match the query. After finding millions of matches, how does the engine rank them to show the most popular ones first?

The search engine solves this through graph theory by first creating a web graph, a graph where the vertices are the websites, and the directed edges follow hyperlinks within those websites. The result is a directed graph that shows all relations between websites. Additionally, one can add weights to the vertices to give priority to more important or influential websites.

To classify the most popular websites, different algorithms can be used. One of the first ones used by Google is called PageRank. Here, the engine assigns probabilities to click a hyperlink and iteratively adds them up to form a probability distribution. This distribution represents the likelihood of a person randomly arriving at a particular website. Then, the engine orders the list of websites according to this distribution and shows the highest ones.

This algorithm had many faults. One can exploit it by having for example blog websites with many links to a particular website to increase the click probability, or by buying hyperlinks in websites with higher weights. Nowadays, there are more complicated algorithms that also consider sponsored advertisement, but the main core is still graph theory and the relations between websites.

1. Graph theory in Search engines Preethi Satsangi 2102818 BSc.CS

2. Understanding the web begins with visualising it as a directed graph, a concept where pages are nodes connected by links that have direction. Vertices and Edges Vertices (Nodes):  Each webpage is a vertex in the graph. The size of the vertex set can be used to gauge the scale of a web graph. Edges (Links):  Hyperlinks that direct from one page to another form the edges. The direction of an edge indicates the flow of navigation from one page to the next. Directed Graphs Unidirectional Flow:  Unlike undirected graphs, where edges have no orientation, the web graph's edges are directed, reflecting the one-way nature of hyperlinks. Cycles:  Cycles occur when a path of directed edges forms a loop, which is significant in understanding web navigation patterns.

3. Web Crawling This is the process by which search engines visit and index webpages, interpreting the web graph to build a database of information. Crawlers (Spiders):  These bots systematically visit webpages, tracing the graph's edges to discover new vertices. Indexing Strategies:  Different strategies determine the order in which pages are visited and indexed, impacting the freshness and comprehensiveness of the search results.

4. PageRank Algorithm PageRank is foundational to Google's search technology, applying graph theory to rank web pages. Here is an overview of how the PageRank algorithm works: Link Analysis:  The algorithm treats links as votes, with the idea that pages linked by important pages are themselves likely to be important. Iterative Calculation:  PageRank iteratively calculates the importance of each page based on the importance of the pages that link to it. Damping Factor:  Typically set around 0.85, this factor accounts for the probability that a user may stop following links and start a new search.

5. Conclusion In sum, graph theory is integral to understanding and navigating the web. By applying graph theory to the web,we gain valuable insights into the structure and dynamics of online information. It is a powerful tool that continues to shape the way we access and analyse data on the internet, making it an indispensable subject for those looking to delve deeper into the field of computer science.  

6. THANK YOU