Database Reference
In-Depth Information
Degree of
the original
minimum node
10
6
Wikipedia
10
5
10
4
10
3
10
2
10
1
10
0
Degree of
the new
minimum node
10
0
10
1
10
2
10
3
Degree (k)
10
4
10
5
10
6
FIGURE 8.9
Degree distribution of Wikipedia. Notice that the original minimum vertex
has degree 1, as in LinkedIn. After the renumbering, the minimum vertex is replaced with a
highest-degree node.
12
10
83% of the
original
8
6
4
2
Wikipedia
0
Original
D1
D2
D3
D4
D5
Minimum node
FIGURE 8.10
Number of iterations vs. the minimum vertex of Wikipedia, for connected
components. D
i
represents the vertex with
i
ith largest degree. Notice that the number of itera-
tions decreased by 17% after renumbering.
8.6.1 C
onneCteD
C
omPonents
oF
r
eal
-w
orlD
n
etworks
Figure 8.11 shows the evolution of connected components of LinkedIn and Wikipedia
graphs. Figure 8.12 shows the distribution of connected components in the YahooWeb
graph. We make the following set of observations.
8.6.1.1 Power Laws in Connected Components Distributions
We observe a power law relation between the count and size of small connected com-
ponents in Figures 8.11a, b and 8.12. This reflects that the connected components in
real networks are formed by preferential attachment processes.
Search WWH ::
Custom Search