Metaheuristics are excellent tools for solving difficult optimization problems. Parallel metaheuristic models serve to increase the diversity of the search and to avoid premature convergence. Usually, the topologies of the island neighborhood are simple (fully connected, torus, ring); however, network science informs us that there are certain families of graphs (e.g. the Erdős-Rényi random networks) that have interesting features (e.g., limited average path length due to the “small world” property) that could be used as novel neighborhood models. In this paper, we take the first step in exploring the use of topologies informed by network science and study Erdős-Rényi networks in the case of Parallel Evolutionary Algorithms. The benefits of such an approach are presented and discussed.