WorksheetsWeb Mining 5.1
Total questions: 79
Worksheet time: 40mins
Name
Class
Date
1.
What is the main focus of link analysis in web mining
a)
Using links to assess relationships and importance
b)
Compressing web pages for storage
c)
Encrypting web traffic
d)
Detecting malware signatures
e)
Optimizing CPU cache usage
2.
In a web graph what does a directed edge usually represent
a)
A hyperlink from one page to another
b)
A shared IP address between pages
c)
A similarity in page layout
d)
A user clicking behavior record
e)
A common file extension
3.
In an adjacency matrix what does a_ij equal to 1 typically mean
a)
There is a link from node i to node j
b)
There is a link from node j to node i
c)
Nodes i and j are the same node
d)
Node i has no outgoing links
e)
Node j has no incoming links
4.
What is the out degree of a node in a directed graph
a)
Number of outgoing links
b)
Number of incoming links
c)
Number of triangles containing the node
d)
Number of shortest paths through the node
e)
Number of connected components
5.
What is the in degree of a node in a directed graph
a)
Number of incoming links
b)
Number of outgoing links
c)
Number of neighbors at distance two
d)
Number of hubs that cite it
e)
Number of iterations to converge
6.
What is the shortest path between two nodes
a)
A path with minimum total cost or weight
b)
A path with maximum number of edges
c)
A path that visits all nodes
d)
A path that avoids all hubs
e)
A path with random choices each step
7.
Which algorithm is presented for computing shortest paths from a source
a)
Dijkstra algorithm
b)
Floyd Warshall algorithm
c)
Kruskal algorithm
d)
Apriori algorithm
e)
K means algorithm
8.
Dijkstra algorithm assumes which condition on edge weights
a)
All edge weights are non negative
b)
All edge weights are negative
c)
All edge weights are equal
d)
Edge weights are ignored
e)
Edge weights are random variables
9.
In Dijkstra algorithm what does d(v) represent
a)
Current best distance estimate from the source to v
b)
Final hub score of v
c)
Number of incoming links to v
d)
Probability of teleportation from v
e)
Index of v in the adjacency matrix
10.
In Dijkstra algorithm what does pred(v) represent
a)
Predecessor of v on the current best path
b)
Out degree of v
c)
Final PageRank of v
d)
Set of nodes that point to v
e)
Number of iterations performed
11.
In Dijkstra algorithm what does Q represent
a)
Set of unvisited vertices
b)
Set of authority vertices
c)
Set of dangling vertices
d)
Set of connected components
e)
Set of adjacency matrix rows
12.
What is the next step after initialization in Dijkstra algorithm
a)
Select the vertex with smallest current distance
b)
Reverse all edges in the graph
c)
Sort vertices by in degree
d)
Compute authority scores
e)
Delete all dangling nodes
13.
What is relaxation in shortest path algorithms
a)
Updating a neighbor distance using a shorter discovered path
b)
Removing cycles from the graph
c)
Converting directed edges to undirected edges
d)
Normalizing PageRank values
e)
Choosing a random starting node
14.
Centrality measures in this lecture are mainly based on what structure
a)
Shortest paths in the network
b)
File sizes of pages
c)
HTML tag counts
d)
Screen positions of links
e)
Exact pixel colors in figures
15.
What does closeness centrality try to capture
a)
How near a node is to many others via short paths
b)
How many outgoing links a node has
c)
How many pages a node contains
d)
How often a node is a sink
e)
How many triangles a node forms
16.
What does betweenness centrality try to capture
a)
How often a node lies on shortest paths between others
b)
How many keywords a page contains
c)
How many outgoing links a node has
d)
How fast power iteration converges
e)
How many random jumps occur
17.
In a directed network degree prestige is most directly based on what
a)
In degree of the node
b)
Out degree of the node
c)
Average path length from the node
d)
Page title length
e)
Number of iterations to convergence
18.
What does proximity prestige incorporate beyond simple in degree
a)
Reachability and distances from other nodes
b)
Only the number of outgoing links
c)
Only the number of triangles
d)
Only page content similarity
e)
Only link text length
19.
What is PageRank used for in link analysis
a)
Ranking nodes based on link structure
b)
Compressing the adjacency matrix
c)
Sorting pages by file size
d)
Labeling images in pages
e)
Detecting hardware faults
20.
Which model motivates PageRank in the lecture
a)
Random surfer random walk model
b)
Shortest path tree model
c)
Decision tree classification model
d)
Neural network backpropagation model
e)
Hash table lookup model
21.
What does the damping factor represent in PageRank
a)
Chance to follow a link rather than teleport
b)
Chance to choose the lowest distance vertex
c)
Chance to delete a node
d)
Chance to reverse an edge
e)
Chance to duplicate a link
22.
What is a key property of the PageRank transition matrix
a)
Each row sums to 1
b)
Each column sums to 0
c)
It is always diagonal
d)
It contains only negative values
e)
It is not based on links
23.
What is a dangling node in the PageRank context
a)
A node with no outgoing links
b)
A node with no incoming links
c)
A node with zero weight edges
d)
A node with a self loop
e)
A node in a cycle of length two
24.
How is a dangling node commonly handled in the transition matrix
a)
Replace its transitions with uniform probabilities
b)
Remove it permanently from the graph
c)
Force it to point only to itself
d)
Set all ranks to zero
e)
Convert all edges to undirected
25.
How is PageRank typically computed in practice
a)
By iterative updates until convergence
b)
By drawing the graph layout
c)
By sorting nodes by ID
d)
By computing only shortest paths
e)
By counting HTML tags
26.
When should power iteration for PageRank usually stop
a)
When rank values change very little between iterations
b)
When every node has the same in degree
c)
When the graph becomes undirected
d)
When all edges are removed
e)
When the matrix becomes diagonal
27.
What does the stationary distribution in PageRank represent
a)
Long run visit probabilities of the random surfer
b)
Shortest path distances from a source
c)
Number of outgoing links per node
d)
Exact link positions in a figure
e)
File sizes of pages
28.
What does HITS stand for
a)
Hyperlink Induced Topic Search
b)
High Impact Topic Scoring
c)
Hierarchical Indexing Tree System
d)
Hybrid Information Transfer Scheme
e)
Heuristic Iterative Text Search
29.
What are the two scores produced by HITS
a)
Authority score and hub score
b)
In degree and out degree
c)
Closeness and betweenness
d)
Precision and recall
e)
Mean and variance
30.
In HITS what characterizes an authority page
a)
It is pointed to by good hubs
b)
It points to many pages
c)
It has no outgoing links
d)
It has the smallest shortest path distance
e)
It has the largest file size
31.
In HITS what characterizes a hub page
a)
It points to good authorities
b)
It is never pointed to by others
c)
It has no incoming links
d)
It minimizes the graph diameter
e)
It is always a dangling node
32.
What is the core idea of mutual reinforcement in HITS
a)
Hubs and authorities strengthen each other through links
b)
Shortest paths always define importance
c)
Only content similarity determines rank
d)
Random jumps remove the need for links
e)
Graphs must be acyclic
33.
Which application is explicitly linked to PageRank in the slides
a)
Ordering web search results
b)
Image color correction
c)
Audio noise removal
d)
CPU scheduling
e)
Packet routing by IP tables
34.
In a citation network what does a directed edge commonly represent
a)
One paper cites another paper
b)
Two papers share the same author
c)
Two papers have the same length
d)
One paper was published later
e)
Two papers are in the same journal issue
35.
In citation analysis which node type resembles an authority in HITS
a)
A highly cited paper
b)
A paper with many references
c)
A paper with large PDF size
d)
A paper with many equations
e)
A paper with many figures
36.
In citation analysis which node type resembles a hub in HITS
a)
A paper that cites many important papers
b)
A paper that is never cited
c)
A paper with no references
d)
A paper that is unpublished
e)
A paper with the shortest abstract
37.
Which representation is repeatedly used for link based computation
a)
Adjacency matrix
b)
Pixel grid of images
c)
Audio spectrogram
d)
Heap memory dump
e)
CPU instruction trace
38.
Why do we normalize by out degree in random walk based ranking
a)
To convert outgoing links into probabilities
b)
To remove all incoming links
c)
To ensure all nodes have zero rank
d)
To maximize shortest path length
e)
To eliminate the need for iteration
39.
Which statement best describes a Markov chain in this context
a)
Next state depends only on current state
b)
Next state depends on all past states
c)
Next state ignores the current state
d)
Next state is always the start state
e)
Next state is always random without probabilities
40.
What is a basic normalization rule for PageRank scores
a)
They sum to 1 across all nodes
b)
They must be integers
c)
They must be negative
d)
They must equal in degree
e)
They must equal out degree
41.
Which statement best matches the HITS output compared with PageRank
a)
HITS separates hub and authority while PageRank is a single score
b)
HITS uses only shortest paths while PageRank uses only content
c)
HITS requires negative edge weights while PageRank does not
d)
HITS forbids directed edges while PageRank requires them
e)
HITS removes iteration while PageRank is iterative
42.
If a page has many outgoing links how does it pass rank to its neighbors in PageRank
a)
It splits its contribution across its outgoing links
b)
It gives the full contribution to every neighbor
c)
It gives rank only to its incoming neighbors
d)
It keeps all rank for itself
e)
It removes rank from neighbors
43.
What happens when the damping factor is decreased in the random surfer model
a)
Random jumps become more likely
b)
Following hyperlinks becomes more likely
c)
Shortest paths become shorter
d)
In degree becomes equal to out degree
e)
The adjacency matrix becomes diagonal
44.
Why can Dijkstra algorithm give incorrect results with negative edge weights
a)
The greedy finalization step can be violated by a later cheaper path
b)
Negative edges make the graph undirected
c)
Negative edges remove all cycles
d)
Negative edges force uniform probabilities
e)
Negative edges guarantee convergence in one step
45.
A node with high betweenness but low degree most likely plays what role
a)
A bridge connecting different parts of the network
b)
A sink that absorbs all rank
c)
A dangling node with no links
d)
A node isolated from the graph
e)
A node that always has highest authority
46.
Which pairing correctly contrasts closeness and betweenness
a)
Closeness focuses on average distance while betweenness focuses on brokerage on shortest paths
b)
Closeness counts incoming links while betweenness counts outgoing links
c)
Closeness measures randomness while betweenness measures file size
d)
Closeness is only for trees while betweenness is only for cliques
e)
Closeness requires negative weights while betweenness forbids weights
47.
Why is in degree a natural basis for prestige in a directed network
a)
Incoming links represent endorsements or citations from others
b)
Outgoing links represent being endorsed by others
c)
Shortest paths always point inward
d)
Only hubs can have incoming links
e)
Teleportation removes the meaning of links
48.
If very few nodes can reach a node in a directed graph what happens to proximity prestige
a)
It tends to be low because reachability into the node is limited
b)
It becomes maximal because the node is exclusive
c)
It is unchanged because distances are ignored
d)
It becomes identical to out degree
e)
It forces PageRank to be zero everywhere
49.
Why must dangling nodes be handled in PageRank computation
a)
To keep the transition probabilities well defined for every node
b)
To ensure the graph has no incoming links
c)
To guarantee the shortest paths are unique
d)
To remove the need for normalization
e)
To turn HITS into PageRank
50.
How does teleportation help with rank sinks in PageRank
a)
It allows the random surfer to escape trapped regions
b)
It forces the surfer to stay in the sink
c)
It removes all edges leading out of the sink
d)
It makes all nodes have the same in degree
e)
It prevents any iteration
51.
What is a practical sign that PageRank iteration has not converged yet
a)
Rank values keep changing noticeably between iterations
b)
All nodes have identical out degree
c)
The graph has no directed edges
d)
Every node becomes a dangling node
e)
The adjacency matrix contains only zeros
52.
Two pages have the same number of incoming links which is more likely to have higher PageRank
a)
The one linked by higher ranked pages
b)
The one with more outgoing links
c)
The one with fewer incoming links
d)
The one with the longest URL
e)
The one with the smallest node ID
53.
Why do we normalize outgoing links when building a transition matrix
a)
To interpret each row as a probability distribution over next hops
b)
To ensure each column is all zeros
c)
To maximize the number of edges
d)
To compute shortest paths faster
e)
To eliminate the need for random jumps
54.
In iterative HITS updates why is normalization typically applied each round
a)
To prevent scores from growing without bound and stabilize comparison
b)
To remove all hubs from the graph
c)
To force authorities to equal hubs
d)
To ensure negative weights are allowed
e)
To guarantee all nodes get score zero
55.
A strong hub page tends to link to what type of pages in HITS
a)
Pages that are strong authorities on the topic
b)
Pages with the highest out degree regardless of topic
c)
Pages that are dangling nodes
d)
Pages with the smallest distance labels
e)
Pages that have no incoming links
56.
A strong authority page tends to be linked by what type of pages in HITS
a)
Pages that are strong hubs
b)
Pages with no outgoing links only
c)
Pages with the lowest betweenness
d)
Pages with uniform transition rows
e)
Pages that are isolated
57.
In PageRank what does the stationary distribution conceptually represent
a)
Long run probability of being at each page
b)
Number of shortest paths through each page
c)
Exact pixel area of each node icon
d)
Number of iterations used
e)
Total file size of each site
58.
If the damping factor is set to 1 what risk increases on graphs that are not strongly connected
a)
The walk can get trapped in a component and ranking can depend on start
b)
The walk always visits every node equally
c)
All nodes become dangling nodes
d)
All edges become bidirectional
e)
The algorithm no longer uses links
59.
In Dijkstra algorithm when is a vertex distance label considered final under its assumptions
a)
When the vertex is selected as the smallest distance among unvisited vertices
b)
When the vertex first appears in Q
c)
When the vertex has highest in degree
d)
When the vertex becomes a hub
e)
When the vertex has no incoming links
60.
Why can betweenness change drastically if a single bridge edge is removed
a)
Many shortest paths may reroute away from the former bridge node
b)
Out degree becomes negative
c)
Teleportation probability becomes zero
d)
The adjacency matrix becomes symmetric
e)
Closeness becomes undefined for all nodes
61.
Which node would closeness centrality typically favor
a)
A node that has short path distances to many other nodes
b)
A node that has no outgoing links
c)
A node that has the highest file size
d)
A node that is never on any shortest path
e)
A node that has only self loops
62.
How is PageRank different from simple in degree as a prestige measure
a)
PageRank weights endorsements by the importance of the linking pages
b)
PageRank ignores direction of links
c)
PageRank counts only outgoing links
d)
PageRank is based only on shortest paths
e)
PageRank requires negative edge weights
63.
Which statement best summarizes a key structural difference between HITS and PageRank
a)
HITS produces hub and authority scores while PageRank produces one rank score
b)
HITS requires undirected graphs while PageRank requires directed graphs
c)
HITS removes normalization while PageRank forbids iteration
d)
HITS is purely content based while PageRank is purely image based
e)
HITS uses only in degree while PageRank uses only out degree
64.
Adding teleportation tends to make the PageRank Markov chain have what desirable property
a)
A unique stable long run distribution for ranking
b)
Negative edge weights for shortest paths
c)
Exact shortest paths between all pairs
d)
Perfect resistance to link manipulation
e)
Zero need for any matrix normalization
65.
Which limitation is most consistent with link based ranking methods like PageRank
a)
They can be manipulated by creating artificial link structures
b)
They require inspecting colors and shapes in figures
c)
They cannot be computed iteratively
d)
They only work on undirected trees
e)
They ignore the existence of hyperlinks
66.
If a graph has dangling nodes and you do not fix them what can break in PageRank computation
a)
Transition probabilities are undefined for those nodes and rank can leak or get stuck
b)
Shortest paths become negative
c)
In degree becomes equal to out degree
d)
HITS no longer needs normalization
e)
Dijkstra becomes correct with negative edges
67.
Which choice best describes a core difference between PageRank and HITS in typical use
a)
PageRank is a single global score while HITS separates hubs and authorities and is often topic focused
b)
HITS is computed by shortest paths while PageRank is computed by sorting node IDs
c)
PageRank needs negative weights while HITS forbids iteration
d)
HITS only uses in degree while PageRank only uses out degree
e)
PageRank requires visual inspection of diagrams while HITS does not
68.
Why can a damping factor below 1 help ensure a stable ranking even on disconnected graphs
a)
Teleportation lets probability flow between components and reduces trapping
b)
It forces all edges to reverse direction
c)
It makes the adjacency matrix all zeros
d)
It guarantees every node has the same degree
e)
It removes the need for a transition matrix
69.
A page that links to many authorities may get a high hub score but still have low authority score under what condition
a)
It is not pointed to by other good hubs
b)
It has the highest in degree in the graph
c)
It is a dangling node with no outgoing links
d)
It is the unique node in the network
e)
It has negative edge weights
70.
In Dijkstra algorithm with non negative weights why is a selected minimum distance vertex final
a)
Any alternative path to it would have to go through a vertex with distance at least as large
b)
Because the graph is always acyclic
c)
Because all edges are unweighted
d)
Because teleportation removes longer paths
e)
Because adjacency matrices force symmetry
71.
Which outcome is most likely if HITS is run on a very large unfocused graph without topic restriction
a)
Scores can drift toward generally popular nodes rather than a specific topic
b)
All nodes get identical hub and authority scores in one step
c)
The algorithm becomes equivalent to sorting by file size
d)
Shortest paths are computed exactly for every pair
e)
Negative edges are automatically removed
72.
In PageRank what is the conceptual effect of teleportation on the link graph
a)
It adds a small chance of jumping from any page to any page
b)
It deletes all outgoing links from hubs
c)
It forces every page to link only to itself
d)
It replaces the adjacency matrix with an identity matrix
e)
It makes in degree irrelevant to any ranking
73.
Why is normalization important in iterative rank updates like PageRank or HITS
a)
It keeps scores comparable across iterations and prevents uncontrolled growth or drift
b)
It guarantees the graph has no cycles
c)
It ensures all nodes have the same degree
d)
It removes the need for convergence checks
e)
It makes negative weights acceptable
74.
Which statement captures an advanced implication of PageRank compared with raw in degree
a)
One strong endorsement can outweigh many weak endorsements
b)
PageRank always equals in degree after one iteration
c)
PageRank ignores the source of incoming links
d)
PageRank depends only on outgoing links
e)
PageRank requires reading values from charts
75.
For proximity prestige why is it reasonable to consider only nodes that can reach the target
a)
Nodes that cannot reach would imply infinite or undefined distances and should not raise prestige
b)
Because unreachable nodes always increase prestige
c)
Because reachability is identical to out degree
d)
Because teleportation replaces distances
e)
Because shortest paths are never used
76.
Which scenario best illustrates a rank sink problem that teleportation addresses
a)
A set of nodes that only link within the set can trap random walkers
b)
All nodes have equal out degree
c)
Every node has at least one outgoing link
d)
The graph has no directed edges
e)
The adjacency matrix is symmetric
77.
Which statement best explains why PageRank may fail to have a unique meaningful solution when damping is 1 on a non strongly connected graph
a)
The random walk can have multiple limiting behaviors depending on start and trapped regions
b)
The transition matrix is always diagonal
c)
The graph becomes a tree
d)
All nodes become authorities
e)
Betweenness becomes identical to closeness
78.
Which option is the most defensible choice for an offline global importance score across the whole web graph
a)
PageRank because it is designed as a global link based prestige score
b)
HITS because it always ignores link structure
c)
Dijkstra because it ranks pages by shortest path to all others
d)
Betweenness because it outputs hub and authority pairs
e)
Closeness because it requires query dependent subgraphs
79.
Which statement best describes a subtle weakness of HITS compared with PageRank for ranking pages
a)
HITS can over emphasize pages that are good link directories as hubs even if they are not authoritative
b)
HITS cannot represent directed graphs
c)
HITS does not use iteration
d)
HITS requires negative weights
e)
HITS is computed by inspecting figure layouts
100 %
