The ability to predict the collapse of ecological communities is of significant concern in light of global patterns of rapid species extinctions. Here, we use a recently developed dynamic Boolean network-based model of mutualistic plant-pollinator community formation to investigate the stability of simulated ecological communities in the face of sequential species extinctions. We assess communities in terms of the relative change in biodiversity after species loss, and find that communities that experience a significant loss of biodiversity differ from more robust communities according to a number of topological characteristics. Notably, we show that high nestedness, a property commonly believed to promote community stability, may in extreme circumstances promote a critical over-reliance on individual species. Furthermore, the species important to the survival of the rest of the ecosystem occupy different positions in the network than less important species. Our results suggest that network measures may be applied to real ecosystems to yield insight into both their stability and the identity of potentially critical species.