Database Reference
In-Depth Information
10
7
Degree of
the original
minimum node
LinkedIn
10
6
10
5
10
4
10
3
10
2
10
1
10
0
10
0
Degree of
the new
minimum node
10
1
10
2
10
3
Degree (k)
10
4
10
5
FIGURE 8.7
Degree distribution of LinkedIn. Notice that the original minimum vertex has
degree 1, which is highly probable given the power law behavior of the degree distribution.
After the renumbering, the minimum vertex is replaced with a highest-degree node.
16
14
12
10
8
6
4
2
0
81% of the
original
LinkedIn
D4
Original
D1
D3
Minimum node
D2
D5
FIGURE 8.8
Number of iterations vs. the minimum vertex of LinkedIn, for connected com-
ponents. D
i
represents the vertex with
i
ith largest degree. Notice that the number of iterations
decreased by 19% after renumbering.
decreased the number of iterations to 81% of the original. Similar results are
observed for the Wikipedia graph in Figures 8.9 and 8.10. The original minimum
vertex has degree 1, and the number of iterations decreased to 83% of the original
after renumbering.
8.6 PEGASUS AT WORK
In this section, we evaluate PEGASUS on real-world networks. Specifically, Section
8.6.1 presents our findings with respect to connected components of real-world
networks. Section 8.6.2 presents our findings on the PageRank scores and Section
8.6.3 presents our findings on the diameter and radii distribution of real-world
networks.
Search WWH ::
Custom Search