The words that children learn can be characterized as a semantic network, with links connecting related words. Recent analyses have shown these networks to have small-world structure, with a few highly-connected hub words facilitating short paths between otherwise distant words. This structure contributes to network robustness, and differences in structure can predict differences in language learning outcomes. While previous studies have shown that semantic network structure reflects linguistic input structure, we provide the first evidence that it is related also to children’s own language learning biases. Two-year old children who show a mutual-exclusivity bias have significantly more hub-like networks than children who do not, even when they know the same number of words. This finding contributes to our understanding of both semantic networks and the origins of mutual exclusivity.