Mutualistic interactions between plants and pollinators play an essential role in the organization and persistence of biodiversity. The structure of interaction networks mediates the resilience of local communities and ecosystem functioning to environmental changes. Hence, network structure conservation may be more critical for maintaining biodiversity and ecological services than the preservation of isolated species in changing landscapes. Here, we intensively surveyed seven 36 km landscapes to empirically investigate the effects of forest loss and landscape configuration on the structure of plant-pollinator networks in understory vegetation of Brazilian Atlantic Forest. Our results indicate that forest loss and isolation affect the structure of the plant-pollinator networks, which were smaller in deforested landscapes, and less specialized as patch isolation increased. Lower nestedness and degree of specialization (H') indicated that the remaining plant and bee species tend to be generalists, and many of the expected specialized interactions in the network were already lost. Because generalist species generate a cohesive interaction core in these networks, these simplified networks might be resistant to loss of peripheral species, but may be susceptible to the extinction of the most generalist species. We suggest that such a network pattern is an outcome of landscapes with a few remaining isolated patches of natural habitat. Our results add a new perspective to studies of plant-pollinator networks in fragmented landscapes, showing that those interaction networks might also be used to indicate how changes in natural habitat affect biodiversity and biotic interactions.