代写COMP4880/8880 Semester 1, 2024 Assignment 2代写留学生Matlab语言

COMP4880/8880 Semester 1, 2024

Assignment 2

Problem 1 (10 points). 80-20 rule in distributions. Consider some real-world quantity x – say, wealth of individuals, or the number of likes on an instagram post.  We assume that x takes values on the positive real line x e b+  and follows a probability density function p(x) ≥ 0.  The goal of this question is to ascertain what kind of pdf p(x) will lead to the so-called 80-20 rule of imbalanced inputs and outputs.

To do so, let us first define population quantile 0 ≤ α ≤ 1 in a population ranked by x, i.e. α = 0.8 will mean that there are 80% of the population that takes a valueless or equal to some xα . We also define activity quantile 0 ≤ β ≤ 1, which can represent wealth, or fraction of likes, etc, that β = 0.2 means that all the activities below a threshold xβ accounts for 20% of the total activity.

1.  (2 points) Write an analytical expression that relates α , p(x) and xα .  Write an ana- lytical expression that relates β , p(x) and xβ .

2.  Let us assume that x follows a uniform distribution p(x) = 0.1 for 0 ≤ x ≤ 10, zero elsewhere. What is the value of α such that α + β = 1 and xα = xβ ?

3.  (2 points) For a power law distribution p(x) = Cx−γ , x ≥ 1 and γ > 1.  What is the

value of γ that will make α-β exactly 80-20, such that α + β = 1 and xα = xβ ?

4.  For 2 < γ < 3, what is the range of α-β as described in the last question?

5.  Suppose random variable z follows a normal distribution z … Ⅵ(µ,σ2 ),thenx = exp(z) follows a log-normal distribution

Is the expectation of x smaller or larger than exp(E[z]), or exp(µ)?  Explain how you obtained your conclusion.

6. For x following a log-normal distribution with fixed µ = ln2, what values of σ will lead to a 80-20 rule?

7.  (2 points)  Can we have a ”equalized” distribution p(x), where α  = β  =  0.5 when xα = xβ ?  If so, specify one such p(x) along with the key steps of how you obtain the results.

Problem 2 (10 + 1 points). HITs and PageRank

In this question, we will work with three toy web graphs, specified in Figure 2.

1.  (1  point) Intuitions for PageRank.   Figure 2.1 shows a small web graph with some proposed values of the PageRank of each node.  Without computing the PageRank, can you tell whether the proposed values are correct. Why or why not?

2.  (3 point) Compute PageRank vector x, hub score h and authority score a for the web graphs shown in (2.1) (2.2) (2.3).  For PageRank, assume a teleportation probability α = 0.1.

3. (4 points) Denote the affinity matrix of a web graph with n nodes as A, with aij ∈ {0, 1}. Consider an “average” webgraph with fixed outdegrees {oi} ni=1, whose Hub matrixΦ = AAT happens to be Φij = oioj/(n − 1) when i = j. Show that its hub score induces the same page ranking (from high to low) as the outdegree of each node. Hint: It is fine to assume that the outdegrees {oi} n i=1 are distinct to get full marks. You could use the following theorem without proof:

Lemma  1 (Theorem  8.4.3,  Matrix  Computation  (4th  edition),  Golub  &  Van  Loan, 2013). Suppose D = diag(d1 ,..., dn ) ∈ Rn ×n  and the diagonal entries satisfy d1   > ...  >  dn.   For  some  constant  ρ 0  and  the z  ∈  Rn   has  no zero components.   If V ∈ Rn ×n  is orthogonal such that

VT (D + ρzzT )V = diag(λ1 ,...,λn )                                    (2)

with λ1  ≥ ... ≥ λn  then

. If ρ > 0, then λ1  > d1  > λ2  > ... > λn  > dn.

. If ρ < 0, then λ1  > d1  > λ2  > ... > λn  > dn.

4.  (1 point) One of the basic ideas behind the computation of hubs and authorities is to distinguish between pages that have multiple reinforcing endorsements and those that simply have high in-degree or out-degree. Comment on page rankings of the hubs and authority scores for the three toy graphs from Question 2.2, and the reason for such differences.

5.  (1 point) If one is  allowed to add one edge to the graph shown in (2.1) in order to increase the PageRank of node B. Which edge will you add, and why?

6.  (0.5  bonus point) Sensitivity of PageRank vectors.   Consider an ergodic Markovian matrix W representing a  (weighted) directed graph, and v being its corresponding PageRank vector, i.e. vTW = vT .   We  say that values  of v are  more  sensitive to changes in the link i,j is than that of the link k,l, when a small change in wij  incurs more change in |v| 2  than a small change in wkl .  How should we find the most sensitive link?  describe your method in terms of an algebraic expression (as opposed to, say,

empirically changing each wij  and identifying the maximum change). Hint: You may use the following lemma without proof:

Lemma 2 (Golub & Meyer,  1986). For matrices P0 , F  ∈ Rn ×n , if P(t) = P0  + tF is row stochastic and irreducible for t ∈ [0,β), then the derivative of the stationary distribution π(t) associated with P(t) is given by

fort ∈ [0,β),where A0(♯) is the group inverse of A0  = I − P0 .

To apply this lemma, you may need to construct appropriate F. Also, you may need to find algorithms to efficiently compute the group inverses.  You may assume irre- ducibility whenever needed.

7.  (0.5 bonus point) Graph design.  Building on the results above.  Given a desired page rank vector v∗ , specify an algorithm that finds the webgraph that has such PageRank values.