Network virtualization allows multiple tenant networks to coexist on a shared infrastructure. Core to its realization is the embedding of virtual networks onto the underlying substrate. Existing approaches are not suitable for cloud environments as they lack a fundamental requirement: elasticity. To address this issue we explore the capacity of flexibly changing the topology of a virtual network by proposing an embedding solution that adds elasticity to the tenant's virtual infrastructures. For this purpose, we introduce four primitives to tenants' virtual networks - including scale in and scale out - and propose new algorithms to materialize them. The main challenge is to enable these new services while maximizing resource efficiency and without impacting service quality. Instead of further improving existing online embedding algorithms - always limited by the inability to predict future demand - we follow a different approach. Specifically, we leverage network migration for our embedding procedures and to introduce a new reconfiguration primitive for the infrastructure provider. As migration introduces network churn, our solution uses this technique judiciously, to limit the impact to running services. Our solution improves on network efficiency over the state-of-the-art, while reducing the migration footprint by at least one order of magnitude.