算法代写 | CSCC46 Assignment 3

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?