Agent-based dynamical models have been used successfully to reproduce a range of observed collective behaviors in biological groups. In these models, agents interact with one another and it has been shown that the topology of the interaction network plays a significant role in emergent outcomes and performance at the level of the group. An important challenge is to understand the tradeoffs, sensitivity to parameters, and different regimes of behavior in these biological models from the perspective of evolution by natural selection. Here we focus our attention on collective migration, defined broadly to represent a class of problems in which individuals in a group respond to an environmental cue and to social interactions. Models of collective migration have shown that a small group of leaders (individuals who invest strongly in the environmental cue) is capable of guiding a larger group of followers (individuals that rely on social interactions). Further, evolutionary simulations of migration models have shown that the speciation of a homogeneous group into leaders and followers is a stable evolutionary outcome when the cost of leadership is sufficiently high. Analytical mean-field evolutionary models using the techniques of adaptive dynamics have confirmed the observations in these simulations. We study the role that the interaction topology plays in the evolutionary outcomes of collective migration. As a point of comparison, we show that our model recovers the (qualitative) results of the mean-field analysis in the limit of all-to-all interconnections. We then demonstrate a minimum connectivity threshold for random interconnection graphs to yield speciated outcomes. We also study the adaptation of nodes on fixed graphs and illustrate the influence of graph topology on emergent outcomes in such adaptive systems.