# Topology of the web graph

## Learning goals

1. Understand the notion of a path in a (directed) graph
2. Know that shortest paths between nodes need not be unique
3. Understand the notion of a strongly connected component
4. Know about the diameter of a graph
5. Be aware of the bow tie structure of the Web

## Script

The slides can be found at File:Topology of the web graph.pdf

## Quiz

1

What is true about the largest strongly connected component of the World Wide Web

 It consists only of the Web pages of the Wide Web Consortium and CERN. the diameter will be surprisingly small (presumably less than 100) there is at least one path of links from one url to any other url in the strongly connected component every node inside the strongly connected component has at least 3 incoming edges every node inside the strongly connected component has at least 3 common nodes with any other node

2

Which of the following statements about the bow tie structure of the web are true?

 the incomponent of the bow tie model can easily be crawled. the out component cannot be crawled since search engines cannot find it. two random nodes from the in component can have a path between them two random nodes of the out component can have a path between them if a new link from a node of the out component is created to a node of the in component both nodes will then be part of the strongly connected component the strongly connected component is the intersection of the in component with the out component the strongly connected component is the union of the in component with the out component