# 算法代写 | CSCC46 Assignment 3

这个作用是是完成PageRank算法

CSCC46 Assignment 3

1. PageRank Spam Farms [30 pts]

(a) [10 pts] The staggering number of people who use search engines to find information every day

makes having a high PageRank score a valuable asset, which creates an incentive for people to game

the system and artificially inflate their website’s PageRank score. Since the PageRank algorithm is

based on link structure, many PageRank spam attacks use special network configurations to inflate

a target page’s PageRank score. We will explore these configurations, called spam farms, in this part

of the question.

Consider the spam farm shown in Figure 1. The spammer controls a set of boosting pages 1, . . . , k

(where page i has PageRank score pi) and is trying to increase the PageRank of the target page

0. The target page receives λ amount of PageRank from the rest of the graph (represented by the

dotted arrow). This means that λ =

P

i∈S

ri

di

, where S is the set of nodes in the rest of the network

that link to the target page 0, ri

is the PageRank score of node i ∈ S, and di

is the outdegree of

node i ∈ S. Let N denote the number of pages in the entire web, including the boosting pages and

target page, and let β denote the PageRank scaling factor (so that random teleportation happens

1 − β fraction of the time). Calculate the PageRank p0 of the target page with this configuration as

a function of λ, k, β, and N. Your solution should not include other parameters (such as pi).

Hint: You can write an expression for p0 in terms of p1, . . . pk, β, k, and N. You can also write the

PageRanks of the boosting pages in terms of p0, β, k, and N.

(b) [10 pts] It turns out that the structure in Figure 1 is optimal in the sense that it maximizes the

target’s PageRank p0 with the resources available. However, it may still be possible to do better by

joining forces with other spammers. It also turns out that the λ contribution from the rest of the

graph is mathematically equivalent to having some extra number of boosting pages, so for the rest of

this question we will ignore λ. Consider the case where two spammers link their spam farms by each

linking to the other’s target page as well as their own, as shown in Figure 2. Let p

0

0 and q

0

0 denote

the PageRank values of the target pages if the spammers use the individual spam configuration that

we discussed in the previous question (without λ this time). Calculate the PageRanks of the target

pages p0 and q0 with the new configuration as a function of k, m, β, and N (where again N denotes

the number of pages in the web graph and β denotes the PageRank scaling factor). What are p0 −p

0

0

and q0 − q

0

0

? Are the spammers better off than they would be if they operated independently, i.e.,

is p0 + q0 > p0

0 + q

0

0

?

(c) [10 pts] There are other ways spammers can form alliances. Consider the setup shown in Figure 3,

where the spammers only link their target pages together. Again let p

0

0 and q

0

0 denote the PageRank

values of the target pages that the spammers would get on their own. Calculate the PageRank of

the target pages p0 and q0 with this configuration as a function of k, m, β, and N (where again N

denotes the number of pages in the web graph and β denotes the PageRank scaling factor). What are

p0 −p

0

0 and q0 −q

0

0

? Are the spammers better off than they would be if they operated independently,

i.e., is p0 + q0 > p0

0 + q

0

0

?

3. [20 pts] In this question, we’ll develop our skills in finding Nash equilibria of simple two-player games.

In each payoff matrix below the rows correspond to player A’s strategies and the columns correspond to

player B’s strategies. The first entry in each box is player A’s payoff and the second entry is player B’s

payoff.

(a) [5 pts] Find all Nash equilibria for the game described by the payoff matrix below. What are the

players’ strategies and payoffs (or expected payoffs in the case of a mixed-strategy equilibrium) in

each equilibrium?