Web Science/Part2: Emerging Web Properties/Modeling the Web as a graph/Topology of the web graph

From Wikiversity
Jump to: navigation, search

Topology of the web graph

Wikiversity-Mooc-Icon-Edit.svg
Wikiversity-Mooc-Icon-Ask.svg
Wikiversity-Mooc-Icon-Learning-goals.svg

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
Wikiversity-Mooc-Icon-Edit.svg
Wikiversity-Mooc-Icon-Ask.svg
Wikiversity-Mooc-Icon-Video.svg

Video

Wikiversity-Mooc-Icon-Edit.svg
Wikiversity-Mooc-Icon-Ask.svg
Wikiversity-Mooc-Icon-Script.svg

Script

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

Wikiversity-Mooc-Icon-Edit.svg
Wikiversity-Mooc-Icon-Ask.svg
Wikiversity-Mooc-Icon-Quiz.svg

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


Wikiversity-Mooc-Icon-Edit.svg
Wikiversity-Mooc-Icon-Ask.svg
Wikiversity-Mooc-Icon-Further-readings.svg

Further reading

  1. tba
Wikiversity-Mooc-Icon-Discussion.svg

Discussion