Invasive species that form mutualistic interactions can perturb resident communities by creating new interactions, or weakening the strength of existing interactions via competition. We hypothesized that introducing a super-generalist plant species to bee-plant networks would lead to (1) increases in the weighted and unweighted average degree, nestedness, and connectance and (2) decreases in the modularity. We constructed visitation networks of bees to five native plant species in experimental research plots, in the presence and absence of an invasive thistle and while varying thistle abundance and time/duration of introduction. Species introduction did not change the visitation rate of bees to co-occurring native plants, or the interaction structure between the native plant species and bee visitors; seed set of a focal native plant species was also unaffected. We found the number of bee species with which the introduced species interacted (generality) correlated with significant increases in unweighted and weighted average degree, nestedness, and connectance, but not modularity. When comparing the impact of the introduced species either early or late in the season, we found similar relationships between introduced species generality and weighted and unweighted average degree and connectance; there was a significant negative relationship between introduced species generality and modularity early in the season, and a significant positive relationship with nestedness late in the season, suggesting introduction timing within a season may affect some measures differently. Overall, the native community was robust to the introduction of the super-generalist; our experimental test of network theory predictions demonstrates an improving mechanistic understanding of how mutualistic networks respond to ecological perturbations.