WorksheetsWeb Mining 5.1: Link Analysis
Total questions: 78
Worksheet time: 39mins
Name
Class
Date
1.
Which link analysis problem is primarily concerned with identifying tightly-knit groups of nodes that are more densely connected internally than with the rest of the network?
a)
Graph Ranking
b)
Community Detection
c)
Link Prediction
d)
Graph Classification
e)
Node Role Analysis
2.
Predicting the evolution of a graph over time by inferring the likelihood of future connections is the main goal of which link analysis task?
a)
Graph Ranking
b)
Community Detection
c)
Link Prediction
d)
Graph Classification
e)
Graph Traversal
3.
Based on the lecture's table of contents, which topic serves as a foundational element for the others listed?
a)
Community detection
b)
Graph representation learning
c)
Graph ranking
d)
Link prediction
e)
Graph traversal algorithms
4.
Which of the following is NOT explicitly listed as a main section in the lecture's content overview?
a)
Graph Ranking
b)
Community Detection
c)
Link Prediction
d)
Graph Representation Learning
e)
Graph Visualization
5.
What fundamental property distinguishes the directed graph (b) from the undirected graph (a) shown on the slide?
a)
Edges in graph (b) have a defined source and destination, implying a one-way relationship.
b)
Graph (b) contains a cycle, whereas graph (a) is acyclic.
c)
Graph (a) represents symmetric relationships, which is impossible in directed graphs.
d)
The number of edges in graph (b) must be greater than in graph (a) for the same number of nodes.
e)
Graph (a) allows self-loops, while graph (b) does not.
6.
In the undirected graph (a), what does the loop on node 1 signify?
a)
Node 1 is the most important node in the graph.
b)
Node 1 has a relationship or connection with itself.
c)
Node 1 is the starting point for any traversal of the graph.
d)
Node 1 has the highest degree in the graph.
e)
Node 1 is an isolated component.
7.
According to the provided definition for the adjacency matrix of the undirected graph, what does the value at a[1,1] signify?
a)
The weight of the edge connected to node 1 is 2.
b)
Node 1 has a degree of 2.
c)
An edge exists from node 1 to itself.
d)
There are two distinct paths starting from node 1.
e)
Node 1 is connected to node 2.
8.
According to the provided adjacency matrix on slide 5, which statement accurately describes the connectivity of node 4?
a)
Node 4 is connected to nodes 3, 5, and 6.
b)
Node 4 is connected to nodes 3 and 5 only.
c)
Node 4 has the highest degree in the graph.
d)
Node 4 has a self-loop.
e)
Node 4 is only connected to node 3.
9.
For a directed graph, what is the key distinction between the in-degree d_i(i) and the out-degree d_o(i) of a node i?
a)
In-degree counts incoming edges, while out-degree counts outgoing edges.
b)
In-degree is for source nodes, while out-degree is for sink nodes.
c)
In-degree is always less than or equal to out-degree.
d)
In-degree sums the weights of incoming edges, while out-degree sums outgoing weights.
e)
Out-degree counts self-loops, while in-degree does not.
10.
In the example directed graph on slide 6, the node labeled "2,2" has an in-degree of 2 and an out-degree of 2. What does this imply?
a)
It receives links from two nodes and points to two other nodes.
b)
It has two self-loops.
c)
It is connected to only two other nodes in total.
d)
It is the undisputed central node of the network.
e)
It lies on exactly two distinct cyclic paths.
11.
In the description of Dijkstra's algorithm, what is the primary purpose of Step 3, which involves updating the distance d(v) for each neighbor v of a selected node u?
a)
To check if a shorter path to v has been found by going through u.
b)
To add all neighbors of u to the priority queue Q.
c)
To mark u as visited so it is not processed again.
d)
To initialize the distances of all neighbors of u to infinity.
e)
To immediately identify the final shortest path to v.
12.
What is the significance of initializing d(s) = 0 and d(v) = infinity for all other vertices v at the beginning of Dijkstra's algorithm?
a)
It establishes the source as the starting point with zero cost and all other nodes as currently unreachable.
b)
It ensures that the algorithm explores nodes in alphabetical order.
c)
It prevents the algorithm from entering an infinite loop in graphs with cycles.
d)
It assigns a preliminary high weight to all paths to avoid negative cycles.
e)
It sets up the graph for a breadth-first search traversal.
13.
In the initial state of the Dijkstra's algorithm example, what does "inf" inside a node represent?
a)
The node's distance from the source 's' is currently considered infinite or uncalculated.
b)
The node has an infinite number of connections.
c)
The node is an invalid or unreachable part of the graph.
d)
The node is the final destination of the path.
e)
The capacity of the node is infinite.
14.
From the initial state of the graph for the Dijkstra example, which nodes will have their distance values updated first?
a)
Nodes 'a' and 'b', as they are directly connected to the source 's'.
b)
All nodes will be updated simultaneously.
c)
Only node 'a', because it has the lowest edge weight from the source 's'.
d)
Nodes 'c' and 'd', as they are the furthest from the source.
e)
Only node 's' has its value updated from 'inf' to 0.
15.
In the initial table for the Dijkstra's algorithm example, what does the value 'nil' in the pred[v] row signify?
a)
No predecessor has been assigned yet in the shortest path tree.
b)
The node is the starting node 's'.
c)
The node is unreachable from the source.
d)
The node has no outgoing edges.
e)
The path calculation for this node has resulted in an error.
16.
What is the likely purpose of the 'color[v]' attribute, initialized to 'W' (white), in the context of the Dijkstra's algorithm execution shown?
a)
To track the status of each node: unvisited (W), visited but not finished (G), or finished (B).
b)
To classify nodes into different communities.
c)
To indicate the weight of the node.
d)
To store the final output color for a graph visualization.
e)
To mark nodes that are part of a negative weight cycle.
17.
After processing the starting node 's' in the Dijkstra example, why is the distance to node 'a' updated to 2 and node 'b' to 7?
a)
These are the weights of the direct edges from 's' to 'a' and 's' to 'b'.
b)
These are the sum of edge weights along the initial path.
c)
These are arbitrary values assigned before the main loop.
d)
It's the number of hops from the source 's'.
e)
It's a result of relaxing the edges from all other nodes.
18.
After the first step of Dijkstra's algorithm (processing node 's'), which node would be selected to visit next?
a)
Node 'a', because its current distance (2) is the minimum among all unvisited nodes.
b)
Node 'b', because its label is alphabetically after 'a'.
c)
Node 'c', as it is the next node in the queue.
d)
The algorithm terminates as a path has been found.
e)
Node 's' is processed again to check for shorter paths.
19.
In the first update to the Dijkstra progress table, what does `pred[v] = s` for nodes 'a' and 'b' indicate?
a)
The current shortest known path to both 'a' and 'b' is directly from 's'.
b)
s' is the only node that can reach 'a' and 'b'.
c)
The algorithm has finished processing nodes 'a' and 'b'.
d)
s', 'a', and 'b' form a cycle.
e)
The paths to 'a' and 'b' are of equal length.
20.
In the Dijkstra progress table, the color for node 's' is changed to 'B' (black). What does this signify?
a)
Node 's' has been visited and its final shortest distance is determined.
b)
Node 's' is the starting node.
c)
Node 's' is part of the final shortest path.
d)
An error was found related to node 's'.
e)
Node 's' has been removed from the graph.
21.
During the execution of Dijkstra's algorithm, the distance to node 'b' is updated from 7 to 5. What is the logic behind this update?
a)
A shorter path to 'b' was found via node 'a' (path s->a->b has weight 2+3=5).
b)
The edge weight from 's' to 'b' was dynamically changed.
c)
The algorithm detected a negative edge and corrected the path.
d)
The initial distance of 7 was a temporary placeholder.
e)
Node 'b' was visited twice and the lower value was kept.
22.
After node 'a' has been processed, which unvisited node has the smallest current distance estimate and will be processed next?
a)
Node 'b' with a distance of 5.
b)
Node 'd' with a distance of 7.
c)
Node 'c' with a distance of 10.
d)
Node 's' as it is the source.
e)
The algorithm picks a node at random.
23.
In the Dijkstra table after processing node 'a', the `pred[v]` for node 'b' is updated from 's' to 'a'. What does this change signify?
a)
The shortest path to 'b' is now understood to come from 'a' instead of directly from 's'.
b)
The path from 's' to 'a' is no longer the shortest.
c)
There are multiple shortest paths to 'b'.
d)
Node 'a' has a higher priority than node 's'.
e)
The edge between 's' and 'b' has been removed.
24.
After node 'a' is processed, the distances to nodes 'c' and 'd' are 10 and 7 respectively. How were these values calculated?
a)
d(c) = d(a)+w(a,c) = 2+8=10; d(d) = d(a)+w(a,d) = 2+5=7
b)
They are the direct edge weights from the source 's'.
c)
d(c) = 10 and d(d) = 7 are initial default values.
d)
These are calculated based on the path through node 'b'.
e)
The values are the sum of all edge weights leading to them.
25.
After node 'b' is processed, the distance to node 'c' is updated from 10 to 6. Why does this update occur?
a)
A shorter path to 'c' was found via node 'b' (path s->a->b->c has weight 2+3+1=6).
b)
The previous path to 'c' with weight 10 was incorrect.
c)
The weight of the edge from 'b' to 'c' was reduced.
d)
The algorithm is backtracking from node 'c' to 'b'.
e)
Node 'c' is now the new source node.
26.
After node 'b' is processed, which unvisited node has the smallest current distance estimate?
a)
Node 'c' with a distance of 6.
b)
Node 'd' with a distance of 7.
c)
Node 'a' with a distance of 2.
d)
Node 'b' with a distance of 5.
e)
Both 'c' and 'd' are equally small.
27.
The `pred[v]` for node 'c' is now 'b'. What is the full shortest path from 's' to 'c' implied by the predecessor chain?
a)
s -> a -> b -> c
b)
s -> b -> c
c)
s -> c
d)
s -> a -> c
e)
s -> d -> c
28.
Based on the state of the table on slide 15, which two nodes remain unvisited (color 'W')?
a)
c and d
b)
s and a
c)
b and c
d)
a and d
e)
d and s
29.
When node 'c' is processed in the Dijkstra's algorithm example, are the distances to any of its neighbors updated?
a)
No, because the path through 'c' does not offer a shorter route to its neighbors.
b)
Yes, the distance to 'd' is updated to a shorter value.
c)
Yes, the distance to 'b' is updated.
d)
Yes, all adjacent nodes are updated regardless of path length.
e)
No, because 'c' has no outgoing edges.
30.
What is the next node to be selected from the queue for processing after node 'c' is visited?
a)
Node 'd'
b)
Node 'a'
c)
Node 'b'
d)
Node 's'
e)
The queue is now empty.
31.
The Dijkstra table on slide 17 shows the color for all nodes except 'd' is 'B'. What does this indicate?
a)
All nodes except 'd' have had their final shortest path distance calculated.
b)
The algorithm has encountered an error at node 'd'.
c)
Node 'd' is the final destination node.
d)
Node 'd' is not connected to the rest of the graph.
e)
The algorithm will now process node 'd' next.
32.
The value for d[d] remains 7 throughout the process after its initial update. Why was it not updated when node 'c' was processed?
a)
The path s->a->c->d has weight 2+8+4=14, which is greater than the existing path's weight of 7.
b)
Node 'c' and node 'd' are not connected.
c)
The edge between 'c' and 'd' is a one-way edge from d to c.
d)
The algorithm had already terminated before processing 'c'.
e)
The distance of 7 is the absolute minimum possible.
33.
According to the final state of the graph, what is the shortest distance from the source 's' to node 'c'?
a)
6
b)
8
c)
10
d)
5
e)
7
34.
In the final Dijkstra's table, the condition `Q = empty` is mentioned. What does this signify?
a)
The algorithm has processed all reachable nodes and has terminated.
b)
The priority queue 'Q' could not be initialized.
c)
No path was found from the source to any other node.
d)
The graph is disconnected.
e)
The algorithm is ready to begin its first iteration.
35.
What is the primary intuition behind Closeness Centrality as defined by the formula C_C(i) = (n-1) / sum(d(i,j))?
a)
A node is central if its average distance to all other nodes is small.
b)
A node is central if it has the highest number of direct connections.
c)
A node is central if it lies on many shortest paths between other nodes.
d)
A node is central if it is connected to other central nodes.
e)
A node is central if removing it disconnects the graph.
36.
A node has a very high Closeness Centrality score compared to other nodes in the network. What does this imply?
a)
The node can efficiently reach all other nodes in the network.
b)
The node has the maximum possible number of edges.
c)
The node is a gatekeeper of information flow between communities.
d)
The node is part of a densely connected clique.
e)
The node has a high PageRank score.
37.
In the star graph example for Betweenness Centrality, why is the score for node 1 high (15) while all other nodes have a score of 0?
a)
Every shortest path between any two peripheral nodes must pass through the central node 1.
b)
Node 1 has the highest degree in the graph.
c)
Node 1 is the only node with a self-loop.
d)
The calculation is based on the sum of edge weights, which are all centered at 1.
e)
The peripheral nodes are not connected to each other at all.
38.
What does the term `p_jk(i) / p_jk` represent in the formula for Betweenness Centrality?
a)
The proportion of shortest paths between nodes j and k that pass through node i.
b)
The probability that a random walk from j to k will go through i.
c)
The distance of the shortest path from j to k that includes i.
d)
The number of edges on the path from j to k.
e)
The ratio of node i's degree to the total number of paths.
39.
How is "Degree Importance" P_D(i) as defined on the slide fundamentally different from a simple in-degree count d_I(i)?
a)
It is normalized by the total number of other nodes in the graph (n-1).
b)
It only considers incoming links from important nodes.
c)
It uses out-degree instead of in-degree.
d)
It is a recursive definition that depends on the importance of its neighbors.
e)
It is calculated using the shortest path distances.
40.
In a directed network of 21 nodes, if node 'i' has an in-degree of 5, what is its Degree Importance P_D(i)?
a)
5 / 20 = 0.25
b)
5/21
c)
(21-1) / 5 = 4
d)
5
e)
It cannot be calculated with the given information.
41.
What is the role of the term `I_i` in the formula for Neighborhood Importance?
a)
It represents the set of all nodes that can reach node i.
b)
It is the importance score of node i.
c)
It is the in-degree of node i.
d)
It is the identity matrix of the graph.
e)
It represents all nodes that are immediate neighbors of i.
42.
How does Neighborhood Importance differ from Degree Importance?
a)
It considers the distances from nodes that point to i, not just their count.
b)
It uses out-degree instead of in-degree.
c)
It is only applicable to undirected graphs.
d)
It requires a damping factor for calculation.
e)
It is a simpler, non-normalized version of degree importance.
43.
According to the slide, what is a key disadvantage of the PageRank algorithm?
a)
Its ranking is query-independent.
b)
It only works on very small graphs.
c)
It requires manual tuning for each website.
d)
It is computationally too slow for modern use.
e)
It cannot handle graphs with cycles.
44.
How is the rank of nodes calculated in large graphs when using PageRank, as described on the slide?
a)
It is approximated using an iterative algorithm based on a 'random walk' model.
b)
It is calculated directly by solving a system of linear equations.
c)
It is based solely on the in-degree of each node.
d)
It is determined by running Dijkstra's algorithm from every node.
e)
It is found by identifying the principal eigenvector of the adjacency matrix.
45.
In the transition matrix on slide 26, what is the principle of the normalization applied to get the final matrix A?
a)
Each row's elements are divided by the row sum, so each row sums to 1.
b)
Each column's elements are divided by the column sum, so each column sums to 1.
c)
Each element is divided by the total number of edges in the graph.
d)
A damping factor is applied to every element in the matrix.
e)
The diagonal elements are set to zero and the matrix is renormalized.
46.
In the normalized transition matrix on slide 26, why is the value at the position for a transition from node 3 to node 4 equal to 1?
a)
Node 3 has only one outgoing link, which points to node 4.
b)
Node 4 has only one incoming link, which is from node 3.
c)
The path from 3 to 4 is the shortest in the graph.
d)
Nodes 3 and 4 have the highest importance scores.
e)
This represents the maximum possible transition probability.
47.
What is the primary role of the damping factor `d` in the PageRank formula?
a)
It represents the probability that a user will click a link on the page rather than navigating to a random page.
b)
It is the total number of documents in the collection.
c)
It normalizes the rank scores to be between 0 and 1.
d)
It is the out-degree of a specific page B.
e)
It is a constant used to speed up algorithm convergence.
48.
What does the term `(1-d)/N` in the PageRank formula represent?
a)
A baseline probability of a random surfer landing on any page, distributed uniformly.
b)
The penalty for pages that have no incoming links.
c)
The total rank that is lost from the system in each iteration.
d)
The probability of a surfer getting stuck on a page with no outgoing links.
e)
The normalization factor for the out-degree of a page.
49.
In the PageRank example with d=1, node A has a rank of 0.4. How is this value derived from its incoming links?
a)
Node A receives the full rank of node C (0.4), which has only one outgoing link.
b)
Node A's rank is the sum of the ranks of its neighbors (B+C = 0.2+0.4 = 0.6), then normalized.
c)
The ranks are arbitrarily assigned to sum to 1.0.
d)
Node A's rank is the average rank of all nodes pointing to it.
e)
It is calculated as d*R(C) = 1*0.4.
50.
In the simple 3-node example with d=1, if the link from B to C were reversed to be from C to B, what would be the most likely impact on node C's PageRank?
a)
Node C's PageRank would become 0.
b)
Node C's PageRank would increase.
c)
Node C's PageRank would remain unchanged.
d)
Node A's PageRank would become 0.
e)
All nodes would have equal PageRank.
51.
In the more complex PageRank example (d=0.85), node B has the highest rank (38.4%). What is a plausible reason for this?
a)
It receives links from many other nodes, including the other high-ranking node C.
b)
It has the most outgoing links, distributing its influence widely.
c)
It is the only node without any outgoing links.
d)
It is positioned in the geometric center of the diagram.
e)
Its rank is artificially inflated by the damping factor.
52.
Despite having several incoming links, node E (8.1%) has a much lower rank than nodes B (38.4%) and C (34.3%). What is a plausible explanation for this based on the PageRank concept?
a)
The nodes linking to E have low PageRank themselves and/or have many outgoing links.
b)
Node E has too many outgoing links, which dilutes its own rank.
c)
Node E is part of a cycle that traps rank within a small group of nodes.
d)
The damping factor d=0.85 penalizes nodes like E.
e)
Node E is a new page that has not been fully indexed.
53.
What is the purpose of the `repeat ... until convergence` loop in the PageRank algorithm pseudocode?
a)
To iteratively refine the rank scores until they stabilize and no longer change significantly.
b)
To process each page in the graph exactly once.
c)
To ensure the total sum of all PageRank scores equals 1.
d)
To randomly walk the graph a fixed number of times.
e)
To eliminate nodes with no incoming links before calculation.
54.
How is the rank of a page A at iteration `i`, denoted R^(i)(A), calculated based on the ranks from the previous iteration `i-1`?
a)
It's a sum of the distributed ranks from all pages B that link to A, plus a base value.
b)
It's the average of the ranks of all pages B that link to A.
c)
It's simply the rank from the previous iteration, R^(i-1)(A), plus a small constant.
d)
It's the in-degree of A divided by the total number of pages N.
e)
It's calculated by multiplying the transition matrix with the rank vector from iteration i-1.
55.
What does the Y-axis, "Total Difference from Previous Iteration," represent in the convergence graph?
a)
The sum of the absolute changes in every page's PageRank score between two consecutive iterations.
b)
The number of pages whose rank order changed in the last iteration.
c)
The error rate of the PageRank calculation.
d)
The total number of links being processed by the algorithm.
e)
The time taken to complete the previous iteration.
56.
According to the convergence graph, how does a larger number of links (322 Million vs. 161 Million) affect the PageRank computation?
a)
It results in a larger initial difference but converges at a similar logarithmic rate.
b)
It causes the algorithm to converge in fewer iterations.
c)
It causes the algorithm to converge in significantly more iterations.
d)
It has no significant impact on the convergence speed.
e)
It prevents the algorithm from converging at all.
57.
How does PageRank, an algorithm that is query-independent, contribute to the relevance of the search engine results shown?
a)
It provides a general measure of a page's importance, which is then combined with query-specific relevance scores.
b)
It ranks pages based on how many times the query term appears on the page.
c)
It is not used for web search, but for citation analysis only.
d)
It dynamically re-ranks pages for every new query.
e)
It clusters search results into different topics.
58.
The percentages next to each search result (e.g., 74.79%) in the example likely represent what?
a)
A final relevance score combining PageRank and other query-dependent factors.
b)
The raw PageRank score of the page, scaled to 100.
c)
The percentage of query keywords found on the page.
d)
The click-through rate of the search result.
e)
A randomly assigned value for display purposes.
59.
How is the PageRank concept applied to citation analysis?
a)
Papers are treated as nodes and citations as directed links, where a highly-cited paper gets a higher rank.
b)
It is used to count the number of publications for each author.
c)
It determines the topics of scientific papers based on their citations.
d)
It predicts which papers are likely to be cited in the future.
e)
It is used to find the shortest citation path between two papers.
60.
In the citation analysis diagram, what do the different concentric circles (Internal, ISI Database, All Citations) likely represent?
a)
Different scopes of the citation network being analyzed, from a small local set to a global one.
b)
The age of the publications, with older ones in the center.
c)
The quality of the publications, as judged by different metrics.
d)
Different academic disciplines.
e)
The different steps of the PageRank algorithm.
61.
On the academic influence chart, "Academic Influence" is measured by Average PageRank. What does a high value on the Y-axis signify?
a)
The country's publications are, on average, cited by other influential publications.
b)
The country produces the highest absolute number of publications.
c)
The country's research has the highest funding.
d)
The country's researchers collaborate internationally the most.
e)
The country focuses on a very narrow field of research.
62.
According to the chart plotting Productivity vs. Academic Influence, which statement best describes the position of the US?
a)
It has the highest productivity and one of the highest academic influence scores.
b)
It has moderate productivity but the highest academic influence.
c)
It has the highest productivity but a relatively low academic influence score.
d)
It is average in both productivity and academic influence.
e)
It has low productivity but high academic influence.
63.
What is a key difference between the HITS algorithm and PageRank regarding their execution, as shown in the table on slide 35?
a)
HITS is executed online (at query time), while PageRank is executed offline.
b)
PageRank is used for spam filtering, while HITS is not.
c)
HITS is faster than PageRank.
d)
PageRank produces a single score, while HITS produces two.
e)
HITS only works for academic papers, while PageRank is for web pages.
64.
The name HITS stands for Hypertext Induced Topic Search. How does this name suggest a difference from PageRank?
a)
It implies the search results are tailored to a specific topic or query.
b)
It suggests the algorithm is induced from hypertext, unlike PageRank.
c)
It means the search is faster than PageRank.
d)
It implies the algorithm only works on text documents.
e)
It refers to the "hits" or visits a webpage receives.
65.
What defines a node as a good "authority" in the context of the HITS algorithm?
a)
A page that is pointed to by many good hub pages.
b)
A page that points to many other pages.
c)
A page with a high PageRank score.
d)
A page that contains the query terms most frequently.
e)
A page that is at the center of the graph.
66.
The slide states that authorities and hubs have a mutually reinforcing relationship. Which statement best describes this?
a)
A good hub points to many good authorities, and a good authority is pointed to by many good hubs.
b)
Hubs and authorities are mutually exclusive; a node cannot be both.
c)
Hubs link to other hubs, and authorities link to other authorities.
d)
The more authorities a hub points to, the lower its own authority score becomes.
e)
The authority score and hub score of a single page must always be equal.
67.
How does the concept of a bipartite graph apply to the relationship between hubs and authorities in the HITS algorithm?
a)
The graph can be viewed as two sets of nodes, hubs and authorities, with links going between the sets.
b)
The algorithm physically separates the graph into two disjoint subgraphs before processing.
c)
Every edge in the web graph must connect a hub to an authority.
d)
The adjacency matrix of the web graph must be bipartite.
e)
Hubs can only link to authorities, and not to other hubs.
68.
In the HITS model, if you consider a graph of web pages, what do the two disjoint sets of nodes (like U and V) in a bipartite view represent?
a)
The same set of pages, viewed once as potential hubs and once as potential authorities.
b)
Pages that contain the query and pages that do not.
c)
Pages from the root set and pages from the base set.
d)
Academic papers and web pages.
e)
Pages with high PageRank and pages with low PageRank.
69.
What is the first step of the HITS algorithm when processing a user query `q`?
a)
Submit the query to a search engine to retrieve an initial set of relevant pages.
b)
Build a complete link map of the entire web.
c)
Calculate the PageRank for all pages.
d)
Initialize hub and authority scores for all pages to 1.
e)
Identify all pages that point to the pages containing the query.
70.
What is the primary purpose of the "Graph Expansion" step in the HITS algorithm?
a)
To create a larger, more focused subgraph that includes not just relevant pages but also pages that link to or are linked by them.
b)
To increase the density of the entire web graph.
c)
To add random edges to the graph to improve connectivity.
d)
To find all pages that are within two hops of the query pages.
e)
To convert the graph into a bipartite graph.
71.
What is the "root set W" in the first phase of the HITS algorithm?
a)
A set of the top k pages returned by a search engine for a given query.
b)
The set of all pages on the web that are considered authorities.
c)
The initial set of pages from which the graph expansion begins.
d)
A manually curated list of important websites.
e)
All pages that have no incoming links.
72.
Why is it necessary to use an existing search engine in the information retrieval step of HITS?
a)
To efficiently find a small, query-relevant starting set of pages from the vastness of the web.
b)
The HITS algorithm cannot process textual content, so it relies on another engine.
c)
To get pre-calculated PageRank scores for the root set.
d)
To ensure the root set is free of spam pages.
e)
This step is not necessary and can be skipped.
73.
How is the "base set S" constructed from the "root set W" during the graph expansion phase of HITS?
a)
It starts with the root set and adds all pages that point to a page in the root set and all pages pointed to by a page in the root set.
b)
It is a random subset of the root set.
c)
It includes all pages on the same web server as the pages in the root set.
d)
It consists of the root set and all pages that are two links away.
e)
It is constructed by removing all low-PageRank pages from the root set.
74.
What is the main goal of expanding the root set to create the base set in HITS?
a)
To find good hub pages that may not be in the root set but point to good authorities within it.
b)
To make the graph large enough for the iterative algorithm to converge.
c)
To include pages on a wider variety of topics.
d)
To slow down the algorithm for better accuracy.
e)
To ensure the base set contains at least a specified number of pages.
75.
According to the formulas on slide 41, how is the authority score `a(i)` of a node `i` calculated?
a)
It is the sum of the hub scores of all nodes that point to node i.
b)
It is the sum of the authority scores of all nodes that node i points to.
c)
It is the in-degree of node i.
d)
It is the PageRank score of node i.
e)
It is a constant value of 1 normalized by the total number of nodes.
76.
What is the relationship between the hub score `h(i)` of a node `i` and the authority scores of other nodes?
a)
The hub score of node i is the sum of the authority scores of all nodes that node i points to.
b)
The hub score of node i is the sum of the hub scores of its neighbors.
c)
A node's hub score is independent of all authority scores.
d)
The hub score is inversely proportional to the authority scores of the nodes it points to.
e)
The hub score and authority score for any given node are always equal.
77.
The iterative update rule for the authority score is `a_k <- L^T * L * a_{k-1}`. What is the conceptual meaning of this operation?
a)
It reinforces the principle that a good authority is pointed to by pages that themselves point to good authorities.
b)
It calculates the distance between a node and all other nodes.
c)
It is a mathematical simplification of the PageRank algorithm.
d)
It identifies the nodes with the highest out-degree.
e)
It converts the graph into a symmetric, undirected form.
78.
What is the purpose of the normalization steps (e.g., `a_k <- a_k / ||a_k||_1`) within the HITS iteration loop?
a)
To prevent the authority and hub scores from growing infinitely large with each iteration.
b)
To convert the scores into a probability distribution.
c)
To speed up the convergence of the algorithm.
d)
To ensure that hub scores and authority scores are equal.
e)
To eliminate negative scores from the vectors.
100 %
