MMiDS 7.5: Self-Assessment Quiz

Consider a random walk on the following graph:

G = nx.Graph()
G.add_edges_from([(0, 1), (1, 2), (2, 0)])

What is the transition matrix for this random walk?

• a) \(\begin{bmatrix} 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \\ 1/3 & 1/3 & 1/3 \end{bmatrix}\)
• b) \(\begin{bmatrix} 0 & 1/2 & 1/2 \\ 1/2 & 0 & 1/2 \\ 1/2 & 1/2 & 0 \end{bmatrix}\)
• c) \(\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\)
• d) \(\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix}\)

In the context of random walks on graphs, what does the out-degree \(\delta^+(i)\) of a vertex \(i\) represent?

• a) The number of incoming edges to vertex \(i\).
• b) The number of outgoing edges from vertex \(i\).
• c) The total number of edges connected to vertex \(i\).
• d) The probability of transitioning from vertex \(i\) to any of its neighbors.

In a random walk on a directed graph, the transition probability from vertex \(i\) to vertex \(j\) is given by:

• a) \(p_{i,j} = \frac{1}{\delta^-(j)}\) for all \(j \in N^-(i)\)
• b) \(p_{i,j} = \frac{1}{\delta^+(j)}\) for all \(j \in N^+(i)\)
• c) \(p_{i,j} = \frac{1}{\delta^-(i)}\) for all \(j \in N^-(i)\)
• d) \(p_{i,j} = \frac{1}{\delta^+(i)}\) for all \(j \in N^+(i)\)

The transition matrix \(P\) of a random walk on a directed graph can be expressed in terms of the adjacency matrix \(A\) as:

• a) \(P = AD^{-1}\)
• b) \(P = A^TD^{-1}\)
• c) \(P = D^{-1}A\)
• d) \(P = D^{-1}A^T\)

In a random walk on an undirected graph, the stationary distribution \(\pi\) satisfies:

• a) \(\pi_i = \frac{\delta^+(i)}{\sum_{j \in V} \delta^+(j)}\) for all \(i \in V\)
• b) \(\pi_i = \frac{1}{\delta(i)}\) for all \(i \in V\)
• c) \(\pi_i = \frac{1}{|V|}\) for all \(i \in V\)
• d) \(\pi_i = \frac{\delta(i)}{\sum_{j \in V} \delta(j)}\) for all \(i \in V\)

A transition matrix \(P\) is reversible with respect to a probability distribution \(\pi\) if:

• a) \(\pi_j p_{i,j} = \pi_i p_{j,i}\) for all \(i,j\)
• b) \(\sum_{i \in V} \pi_i p_{i,j} = \pi_j\) for all \(i,j\)
• c) \(\pi_i p_{i,j} = \pi_j p_{j,i}\) for all \(i,j\)
• d) \(\pi_i = \pi_j\) for all \(i,j\)

Which of the following conditions guarantees the irreducibility of a random walk on an undirected graph \(G\)?

• a) \(G\) is a complete graph.
• b) \(G\) is a bipartite graph.
• c) \(G\) is a connected graph.
• d) \(G\) has self-loops on all vertices.

What is the primary goal of the PageRank algorithm?

• a) To determine the shortest path between two nodes in a graph.
• b) To identify communities or clusters of nodes in a graph.
• c) To rank nodes in a graph based on their centrality or importance.
• d) To visualize the structure of a graph.

The PageRank algorithm models the behavior of a random surfer who:

• a) Always clicks on the most prominent link on the current page
• b) Clicks on a random outgoing link with probability \(\alpha\) and jumps to a random page with probability \(1-\alpha\)
• c) Always jumps to a random page
• d) Clicks on a random incoming link with probability \(\alpha\) and jumps to a random page with probability \(1-\alpha\)

In the PageRank algorithm, what is the purpose of the damping factor \(\alpha\)?

• a) To control the rate at which the random walk converges to its stationary distribution.
• b) To introduce a probability of jumping to a random node, ensuring irreducibility.
• c) To adjust the relative importance of different nodes in the graph.
• d) To account for the weights of edges in the graph.

How is the transition matrix \(Q\) for the modified random walk in the PageRank algorithm defined?

• a) \(Q = \alpha P + (1 - \alpha) I\)
• b) \(Q = \alpha P + (1 - \alpha) \frac{1}{n} 11^T\)
• c) \(Q = \alpha P + (1 - \alpha) D^{-1} A\)
• d) \(Q = \alpha P^T + (1 - \alpha) A\)

Personalized PageRank differs from standard PageRank in that:

• a) It considers the user's browsing history
• b) It jumps to a non-uniform distribution when teleporting
• c) It uses a different damping factor
• d) It only considers a subset of the graph

In the MathWorld dataset example, the Personalized PageRank vector focused on the "Normal Distribution" page primarily includes:

• a) Graph theory concepts
• b) Geometry concepts
• c) Statistical concepts
• d) Number theory concepts

In the context of the MathWorld graph example, what does a high PageRank value for a node (representing a mathematical concept) indicate?

• a) The concept is frequently used in mathematical proofs.
• b) The concept is relatively new and unexplored.
• c) The concept is linked to many other important concepts.
• d) The concept has a long and complex definition.