NCA-ADS - Advanced Data Structures (7% of the exam) - Section 7.3
Evaluate node importance.
Evaluate node importance in a graph using centrality metrics such as degree centrality, betweenness centrality, and PageRank. Compare these measures and choose the one that best reflects the domain definition of influence or connectivity in the specific graph.
Practice question for this objective
lock_openFree sampleAdvanced Data Structureshard
An analyst is scoring nodes in an undirected social influence network, where a node should receive a high score when its neighbours are themselves high-scoring, and no random-walk or teleportation behaviour is required. After building the graph with cuGraph, which centrality algorithm should the analyst apply?
APageRank
BBetweenness centrality
CDegree centrality
DEigenvector centralitycheck_circle Correct
Distinguish eigenvector centrality from PageRank and degree centrality when recursive neighbour prestige must drive node importance scores. Eigenvector centrality is the appropriate measure when a node's importance should be a linear function of the importance of the nodes pointing to it - the classic recursive-prestige or authority model. It is defined as the principal eigenvector of the adjacency matrix, found iteratively: each node's score is updated to be proportional to the sum of its neighbours' current scores until convergence. PageRank is a closely related but distinct algorithm that adds a damping factor (teleportation) to handle dangling nodes and convergence issues in web-scale directed graphs; it is not pure eigenvector centrality. Degree centrality is non-recursive. Betweenness centrality measures path-bridging, not prestige. In cuGraph, eigenvector centrality is available via cugraph.eigenvector_centrality, accepting a cuGraph DiGraph and a maximum-iterations parameter.
Why A is wrong: PageRank is a popular centrality and so is tempting, but it augments eigenvector centrality with a damping and teleportation factor designed for directed web link graphs; on a plain undirected influence network that random-walk behaviour is unnecessary and is not what the important-neighbours criterion asks for.
Why B is wrong: Betweenness centrality counts shortest-path passage frequency and is suited to finding structural bridges. It does not account for whether a node's neighbours are themselves important, so it cannot model the recursive prestige the question describes.
Why C is wrong: Degree centrality for a directed graph can be split into in-degree and out-degree counts. In-degree measures raw incoming link count but treats all source nodes as equally valuable, ignoring the recursive importance of those sources entirely.
Why D is correct: Eigenvector centrality assigns each node a score proportional to the sum of its neighbours' scores, solved iteratively as the principal eigenvector of the adjacency matrix. This directly encodes the recursive property that a node is important if its in-neighbours are important, matching the authority-scoring requirement.
Answers that look right on this material and are not. Each one is a distractor from a different question in the NCA-ADS bank for this domain.
Switch from a directed graph to an undirected graph so that each edge is traversed only once, which halves the number of shortest paths the algorithm must enumerate.
errorWhy it is wrong: Tempting because undirected graphs do have fewer distinct paths, but changing directedness changes the meaning of the centrality result rather than approximating it, and it does not reduce the dominant cost of computing shortest paths from every source.
HITS, computing hub and authority scores so that accounts pointing to the watchlist become hubs and the watchlist members become authorities.
errorWhy it is wrong: Tempting because HITS also propagates importance and would highlight accounts linked to the watchlist, but it has no teleportation vector to personalise; it solves a different mutual hub-authority recurrence and cannot be biased by seeding a restart distribution as the scenario specifies.
GPUs have higher single-core clock speeds than CPUs, so each edge inspection executes faster
errorWhy it is wrong: GPUs typically run at lower clock speeds than modern CPUs; their advantage comes from massively parallel execution across thousands of cores, not faster individual clock cycles