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 image below references older number of vertices (nodes) There are many more.
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]
Strongly Connected Core (SCC)[edit]
In the mathematical theory of directed graphs, a graph is said to be strongly connected if every vertex is reachable from every other vertex.[3]. In the context of web science, we use SCC to describe a large cluster of websites that are connected to each other. Imagine the number of shared connections between facebook, google, and reddit. We could imagine this as a center of gravity for the web, and refer to this as a strongly connected core (SCC).
Diameter[edit]
The length of the "longest shortest path" between any two graph vertices of a graph. In other words, a graph's diameter is the largest number of vertices which must be traversed in order to travel from one vertex to another when paths which backtrack, detour, or loop are excluded from consideration. [4]
Diameter: The diameter of a graph is the length of the longest chain you are forced to use to get from one vertex to another in that graph. You can find the diameter of a graph by finding the distance between every pair of vertices and taking the maximum of those distances.[5]
Graphs and determining the connectivity of the web[edit]
We graph the web to model connectivity. We would want to be aware of the number of links to any one cluster of sites, and any nodes which were unlinked. Understanding the nature of relationships between nodes gives us better information to build a more open, democratic web.
Do you understand this?[edit]
Standards[edit]
These standards are used from the IB Computer Science Subject Guide[6]
- 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
- ↑ https://en.wikipedia.org/wiki/Strongly_connected_component
- ↑ Weisstein, Eric W. "Graph Diameter." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GraphDiameter.html
- ↑ https://stackoverflow.com/questions/3174569/what-is-meant-by-diameter-of-a-network
- ↑ IB Diploma Programme Computer science guide (first examinations 2014). Cardiff, Wales, United Kingdom: International Baccalaureate Organization. January 2012.