Database Reference
In-Depth Information
around 19 for a 1.4 billion-vertex web graph as shown in the upper line of Figure 8.17.
Broder et al. [16] used their sampling approach from approximately 200 million ver-
tices and reported 16.15 and 6.83 as the diameter for the directed and the undirected
cases, respectively. What should the effective diameter be, for a signiicantly larger
crawl of the web, with billions of vertices? Figure 8.16 gives the surprising answer:
Observation 1 (Small Web)
The effective diameter of the
YahooWeb
graph
(year: 2002) is surprisingly small, between 7 and 8.
The previous results from Albert et al. [5] and Broder et al. [16] also consider
the undirected version of the web graph. We compute the average diameter and
show the comparison of diameters of different graphs in Figure 8.17. We irst
observe that the average diameters of all graphs are relatively small (<20) for both
the directed and the undirected cases. We also observe that the Albert et al.'s con-
jecture for the diameter of the directed graph is overpessimistic: both the sampling
approach and Hadi output smaller values for the diameter of the directed graph.
(a)
10
9
10
8
10
7
10
6
10
5
10
4
10
3
10
2
10
1
10
0
YahooWeb
S
Multi-modal
Effective
diameter = 7.62
0
5
10
15
20
25
30
Radius
(b)
10
9
10
8
10
7
10
6
10
5
10
4
10
3
10
2
10
1
10
0
GCC
google.com
C
0
5
10
15 20
Radius
25
30
FIGURE 8.16
(a) Radius plot (count vs. radius) of the YahooWeb graph. Notice the effec-
tive diameter is surprisingly small. Also notice the peak (marked “S”) at radius 2, due to star-
structured disconnected components. (b) Radius plot of GCC (giant connected component) of
YahooWeb graph. The
only
vertex with radius 5 (marked “C”) is google.com.
Search WWH ::
Custom Search