As research in the area of network virtualization continues to advance, there have been numerous efforts to solve the challenge of efficiently mapping virtual networks on top of physical structures. Despite these efforts, current state-of-the-art proposals still suffer from significant amount of rejection of virtual network requests in circumstances where overall resource availability would be sufficient to embed them. This is caused by the exhaustion of resources in certain key points of the infrastructure. In this paper, we propose HIPER - a strategy for expanding physical networks that suggests infrastructure upgrades with the objective of maximizing the acceptance of virtual network requests (and, as a consequence, physical resource utilization). This is achieved through the reconnection of strongly connected components (i.e., recurring partitions) of the infrastructure. Evaluated under realistic workloads, HIPER led to promising results. After the expansion of 10% to 20% of infrastructure resources, HIPER sustained an increase of up to 30% in virtual network acceptance, allowing an additional 52% in resource utilization. View full abstract