Graph theory and connectivity of the web

From Computer Science Wiki
Jump to: navigation, search
Web Science[1]

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

It has been suggested we can imagine the web as a bowtie structure (image below). The image below references older numberA unit of abstract mathematical system subject to the laws of arithmetic. of vertices (nodes) There are many more.
Bowtie.png
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)

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 contextThe circumstances that form the setting for an event, statement, or idea, and in terms of which it can be fully understood and assessed. of web science, we use SCC to describeGive a detailed account or picture of a situation, event, pattern or process. a large cluster of websites that are connected to each other. Imagine the numberA unit of abstract mathematical system subject to the laws of arithmetic. 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

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 numberA unit of abstract mathematical system subject to the laws of arithmetic. 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

We graph the web to model connectivity. We would want to be aware of the numberA unit of abstract mathematical system subject to the laws of arithmetic. 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?

Standards

These standards are used from the IB Computer Science Subject Guide[6]

  • DescribeGive a detailed account or picture of a situation, event, pattern or process. the main features of the web graph such as bowtie structure, strongly connected core (SCC), diameter.
  • ExplainGive a detailed account including reasons or causes. the role of graph theory in determining the connectivity of the web.

References

  1. http://www.flaticon.com/
  2. https://en.wikipedia.org/wiki/Internet_topology#Bow_Tie_Model
  3. https://en.wikipedia.org/wiki/Strongly_connected_component
  4. Weisstein, Eric W. "Graph Diameter." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GraphDiameter.html
  5. https://stackoverflow.com/questions/3174569/what-is-meant-by-diameter-of-a-network
  6. IB Diploma Programme Computer science guide (first examinations 2014). Cardiff, Wales, United Kingdom: International Baccalaureate Organization. January 2012.