NCA-GENL - Core Machine Learning and AI Knowledge (30% of the exam) - Section 1.5
Apply graph algorithms to analyse complex networks.
Understand how graphs represent entities and relationships, and apply algorithms such as breadth-first search, shortest path, and community detection to analyse complex networks. Recognise the use cases - fraud detection, recommendation systems, and knowledge graphs - where graph-based methods outperform tabular approaches.
Graph algorithms
Practice question for this objective
lock_openFree sampleCore Machine Learning and AI Knowledgemedium
A recommendation system models users and items as nodes, with edges representing interactions. Which graph algorithm is most appropriate for identifying tightly connected communities of users who share similar item preferences?
ADijkstra's shortest-path algorithm applied to weighted interaction edges
BPageRank centrality computed iteratively across the bipartite graph
CBreadth-first search traversal seeded from a single high-degree user node
DA community detection algorithm such as Louvain modularity optimisationcheck_circle Correct
Understand how community detection algorithms partition graph networks to reveal clusters of related nodes. Louvain modularity optimisation and similar community detection methods (such as Girvan-Newman or label propagation) operate by evaluating the modularity metric, which measures the density of edges within communities relative to a random baseline. They iteratively merge or split groups to maximise this metric, producing partitions that correspond to real-world communities. This is the standard approach for finding user or item clusters in recommendation graphs, where shortest-path or ranking algorithms address different analytical questions.
Why A is wrong: Shortest-path algorithms find optimal routes between two nodes, not groupings of densely connected nodes. Applying Dijkstra's here would reveal how closely two specific users are connected but would not partition the graph into coherent communities of similar preference.
Why B is wrong: PageRank scores nodes by their relative importance based on incoming link weight, which is useful for ranking items by popularity. It does not group nodes into communities, so it would not reveal clusters of users with overlapping preferences.
Why C is wrong: Breadth-first search explores nodes layer by layer from a starting point and is useful for reachability and level-order traversal. It does not optimise any clustering criterion and therefore cannot reliably partition users into communities of shared preference.
Why D is correct: Community detection algorithms like Louvain partition a graph by maximising modularity, the degree to which edges fall within groups rather than between them. This directly identifies clusters of users whose interaction patterns are more similar to each other than to the rest of the network.
Exam traps in Core Machine Learning and AI Knowledge
Answers that look right on this material and are not. Each one is a distractor from a different question in the NCA-GENL bank for this domain.
The number of distinct shortest paths between the seed user and that user
errorWhy it is wrong: Counting distinct shortest paths requires accumulating path counts across predecessors during the traversal; the layer index alone does not carry this count, so this confuses the path total with the distance.
The layer numbers give the minimum total edge weight from the start account to each account.
errorWhy it is wrong: This sounds right but the graph is unweighted, so there are no edge weights to minimise; weighted shortest paths need Dijkstra, not plain BFS.
BFS always uses less memory than DFS because it never needs to store more than one path at a time.
errorWhy it is wrong: This reverses reality. BFS stores the entire frontier and can use more memory than DFS, which only keeps the current path on its stack, so the memory claim is incorrect even though both are valid traversals.