To act adaptively in a complex and dynamic social landscape, humans must continually make inferences about who might be connected to whom. How do they solve this fundamental problem of social link prediction: inferring the existence of unobserved or potential relationships in their social network from noisy, limited information? We propose that people generate principled inferences by learning cognitive maps that systematically abstract over direct relations (friends) and multistep relations (e.g., friends-of-friends). We show that such abstracted cognitive maps enable a flexible solution for link prediction and provide a natural explanation for a variety of otherwise puzzling empirical observations in social psychology. Our proposal generalizes the theory of cognitive maps to the fundamental computational problem of social link prediction and presents a powerful framework for understanding the workings of a predictive mind operating within a complex social world.