NCA-ADS - Advanced Data Structures (7% of the exam) - Section 7.2
Represent and analyse graph-based data.
Represent graph-based data using nodes and edges and apply graph analytics techniques such as shortest-path search, community detection, and centrality measures. Recognise when graph analytics expresses relationships that tabular data structures cannot capture efficiently.
Graph analytics
Practice question for this objective
lock_openFree sampleAdvanced Data Structureshard
An analyst scores nodes in a directed citation network with cuGraph, where a paper should be ranked highly when it is cited by other highly ranked papers, and where the random-walk model must include a teleportation (damping) term so that papers with no outgoing citations do not trap the walk and so that disconnected components still receive a non-zero score. Which centrality algorithm matches these requirements?
ADegree centrality, because counting the number of incoming citations directly measures how often a paper is referenced and needs no iterative random-walk model.
BEigenvector centrality, because it ranks a node by the eigenvector of the adjacency matrix and so accounts for the quality of the nodes pointing to it.
CPageRank, because it models a random walker with a damping factor whose teleportation term redistributes score from dangling nodes and guarantees every node a non-zero rank.check_circle Correct
DBetweenness centrality, because it measures how many shortest paths pass through a node and therefore captures the influence a paper exerts across the citation network.
Recognise that PageRank uses a damped random walk with teleportation to rank nodes cited by important nodes while handling dangling nodes and disconnected components. PageRank defines a node's score as a damped sum of the scores of nodes linking to it; the teleportation probability redistributes rank mass from dangling nodes and from disconnected components, guaranteeing convergence and a strictly positive score for every node, which plain eigenvector centrality cannot promise on directed graphs.
Why A is wrong: Tempting because in-degree does count citations, but it weights every citing paper equally and has no damping or teleportation term, so it cannot satisfy the requirement that citations from highly ranked papers count more or that dangling nodes be handled by a random walk.
Why B is wrong: Tempting because eigenvector centrality also rewards being linked to by important nodes, but it has no teleportation term, can fail to converge on directed graphs with dangling nodes, and may assign zero score to nodes outside the dominant component, which the scenario explicitly rules out.
Why C is correct: Correct: PageRank's recursive definition rewards being cited by high-scoring nodes, and its damping or teleportation parameter is exactly what handles dangling nodes and disconnected components, which is what the scenario specifies.
Why D is wrong: Tempting because betweenness is a well-known importance measure, but it quantifies bridging on shortest paths rather than being cited by important nodes, and it uses no random-walk or damping model at all, so it does not fit the stated 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.
Degree centrality, because a person with many direct contacts can infect more people in a single step, which is the fastest possible spread.
errorWhy it is wrong: Tempting because high degree does speed the first hop, but degree counts only immediate neighbours and ignores how far the rest of the network is, so it does not measure average shortest-path distance to all reachable nodes as the scenario requires.
Convert the cuDF DataFrame to a pandas DataFrame, pass it to networkx.from_pandas_edgelist, then call the NetworkX connected components function so cuGraph can intercept the call transparently
errorWhy it is wrong: cuGraph does not intercept NetworkX calls; the graph must be constructed natively in cuGraph, and converting 50 million edges to pandas would move data off the GPU and lose the memory and compute advantages of RAPIDS
Harmonic centrality, which sums the reciprocals of shortest-path distances and so remains well defined even when some nodes are unreachable from others.
errorWhy it is wrong: Tempting because harmonic centrality also avoids the zero-score and divergence problems of its base measure, but it is a distance-based variant of closeness, not of eigenvector centrality, and it uses no attenuation factor or additive baseline over paths as described.