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 optimisation Correct
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.