Graph theory and connectivity of the web
It is useful to visually map the web to better understand the structure. There are many different ways to imagine what the web might look like (including this rather funny map) but there is some academic agreement about:
- bowtie structure
- strongly connected core (SCC)
- diameter
Bowtie structure[edit]
It has been suggested we can imagine the web as a bowtie structure (image below).
The Bow Tie model comprises four main groups of web pages. There is a strongly connected core. There are then two other large groups, roughly of equal size. One consists of all pages that link to the strongly connected core, but which have no links from the core back out to them. This is the "Origination" or "In" group, as it contains links that lead into the core when originating from it. The counterpart to this is the group of all pages that the strongly connected core links to, but which have no links back into the core. This is the "Termination" or "Out" group, as it contains links that lead out of the core and terminate from it. The fourth and final group is all other disconnected pages, which neither link to the core nor are linked from it.
A more comprehensive representation of the Bow Tie model has been presented with additional, smaller groups of web pages. In this version, both the "In" and "Out" groups have smaller "tendrils" leading to and from them. These consist of pages that link to and from the "In" and "Out" group but are not part of either to begin with, in essence the "Origination" and "Termination" groups of the larger "In" and "Out". This can be carried on ad nauseam, adding tendrils to the tendrils, and so on. Additionally, this more detailed version contains another important group known as the "Tubes". This group consists of pages accessible from "In" and which link to "Out", but which are not part of the large core. Visually, they form alternative routes from "In" to "Out", like tubes bending around the central strongly connected component.[2]
Do you understand this?[edit]
Standards[edit]
These standards are used from the IB Computer Science Subject Guide[3]
- Describe the main features of the web graph such as bowtie structure, strongly connected core (SCC), diameter.
- Explain the role of graph theory in determining the connectivity of the web.
References[edit]
- ↑ http://www.flaticon.com/
- ↑ https://en.wikipedia.org/wiki/Internet_topology#Bow_Tie_Model
- ↑ IB Diploma Programme Computer science guide (first examinations 2014). Cardiff, Wales, United Kingdom: International Baccalaureate Organization. January 2012.