PEGASUS - Large Scale and Big Data: Processing and Management - page 256

diameter and radii of a graph. Finally, in Section 8.2.4, we present briefly, work related
to space efficient algorithms for finding the number of distinct elements in a multiset.
Throughout the chapter, we use n, m for the number of vertices and edges of the graph G .

8.2.1 s truCture oF r eal -w orlD n etworks
8.2.1.1 Bow-Tie Structure of the Web Graph
In 1999, Andrei Broder et al. [16], performed an influential study of the web graph
using strongly connected components (SCCs) as their building blocks. Specifically,
they proposed the bow-tie model for the structure of the web graph based on their
findings on the index of pages and links of the AltaVista search engine. According
to the bow-tie structure of the web, there exists a single giant SCC. Broder et al. [16]
positioned the remaining SCCs with respect to the giant SCC as follows:

• IN: vertices that can reach the giant SCC but cannot be reached from it.

• OUT: vertices that can be reached from the giant SCC but cannot be reached

from it.

• Tendrils: These are vertices that either are reachable from IN but can-

not reach the giant SCC or the vertices that can reach OUT but cannot be
reached from the giant SCC.

• Disconnected: vertices that belong to none of the above categories. These

are the vertices that even if we ignore the direction of the edges have no
path connecting them to the giant SCC.

A schematic picture of the bow-tie structure of the web is shown in Figure 8.1.
This structure has been verified in other studies as well [12,20].

Tendrils
44 million
nodes

IN SCC OUT

56 million nodes

44 million
nodes

44 million
nodes

Tubes

Disconnected
components

FIGURE 8.1 Bow-tie structure of the web graph. (Image from A. Broder et al., Comput.
Networks , 33(1), 309-320, 2000.)