Figures
2.1 Comparison of convergence rate for the standard Power Method on the LARGEWEB dataset for c = 0.90 and c = 0.95.
5.1 Comparison of convergence rate for unaccelerated Power Method and Aitken Extrapolation on the STANFORD.EDU dataset, for c = 0.99. Extrapolation was applied at the 10th iteration.
5.2 Comparison of convergence rates for Power Method and Quadratic Extrapolation on LARGEWEB for c = 0.90. Quadratic Extrapolation was applied the first 5 times that 3 successive power iterates were available.
5.3 Comparison of convergence rates for Power Method and Quadratic Extrapolation on LARGEWEB for c = 0.95. Quadratic Extrapolation was applied 5 times.
5.4 Comparison of convergence rates for Power Method and Quadratic Extrapolation on LARGEWEB when c = 0.99. Quadratic Extrapolation was applied all 11 times possible.
5.5 Comparison of wallclock times taken by Power Method and Quadratic Extrapolation on LARGEWEB for c = {0.90, 0.95, 0.99}. For c = {0.90, 0.95}, the residual tolerance 
was set to 0.001, and for c = 0.99, it was set to 0.01.
5.6 Comparison of convergence rates for Power Method, Aitken Extrapolation, and Quadratic Extrapolation on the STANFORD.EDU dataset for c = 0.99. Aitken Extrapolation was applied at the 10th iteration, Quadratic Extrapolation was applied every 15th iteration. Quadratic Extrapolation performs the best by a considerable degree. Aitken suffers from a large spike in the residual when first applied.
5.7 Comparison of convergence rates for Quadratic Extrapolation on LARGEWEB for c = 0.95, under two scenarios: Extrapolation was applied the first 5 possible times in one case, and all 14 possible times in the other. Applying it only 5 times achieves nearly the same benefit in this case.
5.8 Comparison of convergence rates for Power Method and Simple Extrapolation on LARGEWEB for c = 0.85.
5.9 Comparison of convergence rates for Power Method and A2 Extrapolation on LARGEWEB for c = 0.85.
5.10 Convergence rates for A6 Extrapolation, for d {1, 2, 4, 6, 8}, compared with standard Power Method.
5.11 Comparison of convergence rates for Power Method, A6 Extrapolation, and Quadratic Extrapolation on LARGEWEB for c = 0.85.
5.12 Comparison of the L1 residual versus KDist and Kmin for PageRank iterates. Note that the two curves nearly perfectly overlap, suggesting that in the case of PageRank, the easily calculated L1 residual is a good measure for the convergence of query-result rankings.
6.1 Experiments on STANFORD.EDU dataset. (a) Profile of bar graph where each bar represents a page i, and its height represents its convergence time ti. (b) Bar graph where the x-axis represents the discrete convergence time t, and the height of ti represents the number of pages that have convergence time t. (c) Bar graph where the height of each bar represents the average PageRank of the pages that converge in a given convergence time. (d) Bar graph where the height of each bar represents the average PageRank of the pages that converge in a given interval.
6.2 Experiments on the LARGEWEB dataset. (a) Bar graph where the x-axis represents the convergence time t in number of iterations, and the height of bar ti represents the proportion of pages that have convergence time t. (b) Cumulative plot of convergence times. The x-axis gives the time t in number of iterations, and the y-axis gives the proportion of pages that have a convergence time ≤ t.
6.3 Average PageRank versus convergence time (in number of iterations) for the LARGEWEB dataset. Note that pages that are slower to converge to a relative tolerance of .001 tend to have high PageRank.
6.4 Experiments on LARGEWEB dataset depicting total cost for computing the PageRank vector to an L1 residual threshold of 10-3 and 10-4. (a) FLOPS; (b) wallclock time; (c) number of iterations.
7.1 A view of four different slices of the Web: (a) the IBM domain; (b) all the hosts in the Stanford and Berkeley domains; (c) the first 50 Stanford domains, alphabetically; and (d) the host-graph of the Stanford and Berkeley domains.
7.2 Histogram of distribution over host sizes of the Web. The x-axis gives bucket sizes for the log10 of the size of the host-blocks, and the y-axis gives the fraction of host-blocks that are that size.
7.3 Distribution over interconnectivity of host-blocks for the DNR- LARGEWEB dataset. The x-axis shows percentile buckets for intrahost linkage density (the percent of edges originating or terminating in a given host that are intrahost links), and the y-axis shows the fraction of hosts that have that linkage density (a) for all hosts; (b) for all hosts that have more than 1 page; (c) for all hosts that have 5 or more pages.
7.4 Local PageRank convergence rates for hosts in DNR-LARGEWEB. The x-axis is the number of iterations until convergence to a tolerance of 10-1, and the y-axis is the fraction of hosts that converge in a given number of iterations.
7.5 Convergence rates for standard PageRank (solid line) versus BlockRank (dotted line). The x-axis is the number of iterations, and the y-axis is the log of the L1 residual. STANFORD/BERKELEY data set; c = 0.85.
7.6 Convergence of personalized PageRank computations using standard PageRank and personalized BlockRank.
8.1 Query propagation.
8.2 Share of uploads and files in a P2P network.
9.1 EigenTrust convergence.
9.2 Two-dimensional CAN hash space.
9.3 Load distribution in a network using deterministic download source selection versus a non-trust-based network. The load distribution is heavily skewed; peer 2 will eventually accumulate all reputation in the network.
9.4 Load distribution in a network using probabilistic download source selection versus a non-trust-based network. The load distribution does not deviate too much from the load distribution in a network based on random, non-trust-based download source selection and is thus close to the natural load distribution in a normal Gnutella network.
9.5 Reduction of inauthentic downloads by basing download source selection on global trust values in a network where independent malicious peers are present. Upon activation of our reputation scheme, the number of inauthentic downloads in the network is significantly decreased to around 10% of all downloads in the system; malicious peers in the network are essentially banned from uploading inauthentic files.
9.6 Trust-based reduction of inauthentic downloads in a network where a fraction of peers form a malicious collective and always upload authentic files. Forming a malicious collective does not boost the trust values of malicious peers significantly; they are still essentially banned from uploading inauthentic files, similar to Figure 9.5.
9.7 Trust-based reduction of inauthentic downloads in a network where a fraction of peers form a malicious collective and return authentic files with certain probabilities. When malicious peers partly provide authentic uploads, they receive more positive local trust values and will be selected as download sources more often, also increasing their chances to upload inauthentic files. However, uploading authentic files may be associated with a cost for malicious peers. 102Inauthentic downloads versus authentic uploads provided by malicious peers with trust-based and non-trust-based download source selection. When malicious peers provide authentic files in more than 20% of the cases when selected as download source, the increase in authentic files uploaded by malicious peers exceeds the increase in inauthentic downloads in the network, hence possibly coming at a higher cost than benefit for malicious peers.
9.8 Inauthentic downloads versus authentic uploads provided by malicious peers with trust-based and non-trust-based download source selection in a network populated by type D and type B peers. As with threat model C, malicious peers have to provide a number of authentic uploads in order to increase their global trust values. But as compared to Figure 9.8, fewer authentic uploads by malicious peers are necessary to achieve equal numbers of in- authentic downloads in the network: 5000 inauthentic downloads cost 400 authentic uploads with this strategy as compared to more than 1000 authentic uploads with threat model C.
10.1 Hidden malicious attack.
10.2 Average characteristic path (cycle 0).
10.3 Average characteristic path (cycle 95).
10.4 Characteristic path length (cycle 0-100).
10.5 Characteristic path length based on file uploads.
10.6 Connections versus shared data volume.
10.7 Connections versus authentic uploads.
10.8 Authentic response ratio.
10.9 Network traffic.
10.10 Authentic responses.
10.11 Authentic response ratio.
10.12 Malicious query responses based on TTL.
10.13 Cluster coefficient.
10.14 Link ratio based on local trust.
10.15 Link ratio based on content similarity.
10.16 Node model for threat models A and B.
10.17 Threat model A malicious connections.
10.18 Threat model B malicious connections.
10.19 Threat model B inauthentic downloads.
10.20 Node model for threat model C.
10.21 Threat model C malicious connections.