Question

Supplementary problem. In this problem we explore the myopic scarch algorithm for short paths in a one dimensional small world model with q=1. Specifically, consider the ring network studied in section 20.7, where each node has two local contacts and one remote contact. Each node, say node v, establishes a directed link to node w with a probability proportional to d(v,w)−q. Assume that q=1 and that the number of nodes n is large. Answer the following questions. a) Find the normalization constant in order to make d(v,w)−q a probability distribution. That is, suppose that D is the length of a randomly selected long-range link. Find Z such that P(D=x)=Zx−Q​,x=1,2,… is a probability mass function. b) Give an intuitive argument that explains why the myopic search is not efficient when q<1. c) If q<1, show that there is a set K around the destination node t that myoptic search find it difficult to penetrate. The set K has nc/2 nodes on each side of node t, as shown in Figure 1. Find the constant c as a function of q. d) Give an intuitive argument that explains why the myopic search is not efficient when q>1. e) Suppose that q>1. Find the expected length of a long-range link according to the probability distribution obtained in part a). That is, find E[D].

Answer 1

In this problem, we explore the myopic search algorithm for short paths in a one-dimensional small world model with a specific ring network. We find the normalization constant Z to make d(v,w)−q a probability distribution and solve for it. We discuss the efficiency of myopic search when q<1 and q>1, and show that there is a set K around the destination node where the myopic search finds it difficult to penetrate when q<1. Lastly, we calculate the expected length of a long-range link when q>1.

Step-by-step explanation:

Problem a)

To find the normalization constant Z, we need to make sure that the sum of the probabilities for all possible values of x (1, 2, ...) is equal to 1. This can be represented as the equation:

∑[x=1 to ∞] Zx^-1 = 1

Simplifying the equation, we get:

Z ∑[x=1 to ∞] x^-1 = 1

Taking the sum using the formula for the sum of the reciprocals of positive integers, we get:

Z (1 + 1/2 + 1/3 + ...) = 1

This sum is known as the harmonic series, which diverges to infinity. To make the equation solvable, we need to define the series as the natural logarithm of a certain value. In this case, we define it as the natural logarithm of Z. The equation now becomes:

Z ln(Z) = 1

Solving this equation numerically, we find the value of Z to be approximately 1.7632228.

Problem b)

A myopic search is not efficient when q<1 because the probability of finding a short path decreases as q decreases. Since the algorithm is based on the probability of establishing a link proportional to d(v,w)−q, a smaller q value reduces the likelihood of finding a short path. Therefore, the algorithm becomes less efficient in finding short paths when q<1.

Problem c)

When q<1, there is a set K around the destination node t where the myopic search finds it difficult to penetrate. The set K consists of nc/2 nodes on each side of node t. The constant c in set K can be defined as a function of q, but the specific formula for c depends on the details of the model and is not provided in the given information.

Problem d)

A myopic search is not efficient when q>1 because the probability of finding a short path increases as q increases. When q>1, the algorithm tends to favor longer links, which increases the likelihood of finding a longer path. Therefore, the algorithm becomes less efficient in finding short paths when q>1.

Problem e)

When q>1, the expected length of a long-range link (E[D]) can be found using the probability distribution obtained in part a). The probability mass function P(D=x) is given by Zx^-1. To find E[D], we need to calculate the sum of the products of x and the corresponding probability P(D=x) for all possible values of x. This can be represented as the equation:

E[D] = ∑[x=1 to ∞] x * P(D=x)

Simplifying the equation, we get:

E[D] = Z ∑[x=1 to ∞] x * x^-1

Taking the sum using the formula for the sum of the reciprocals of positive integers, we get:

E[D] = Z (1/1 + 1/2 + 1/3 + ...)

The sum is again the harmonic series, which diverges to infinity. Therefore, the expected length of a long-range link is infinite when q>1.