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) $\left[\begin{array}{ccc}1/3& 1/3& 1/3\\ 1/3& 1/3& 1/3\\ 1/3& 1/3& 1/3\end{array}\right]$
• b) $\left[\begin{array}{ccc}0& 1/2& 1/2\\ 1/2& 0& 1/2\\ 1/2& 1/2& 0\end{array}\right]$
• c) $\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$
• d) $\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\end{array}\right]$

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=A{D}^{-1}$
• b) $P=A^T{D}^{-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.