Over the last years, network virtualization has become one of the most promising solutions for sustainability towards the ongoing increase of data demand in mobile networks. Within that context, the virtual network embedding problem has recently been studied extensively and many different solutions have been proposed; but, mainly these studies have focused on wired networks. The main purpose of this paper is to provide an optimization framework for optimal virtual network embedding, including a heuristic algorithm with low computational complexity, by explicitly considering the effect of supporting the actual user mobility, assuming the emerging Distributed Mobility Management (DMM) scheme as well as a traditional Centralized Mobility Management (CMM) scheme. In addition to that, service differentiation is introduced, giving higher priority to time-critical over-the-top (OTT) services compared to more traditional elastic Internet applications. The performance of the proposed framework is compared to mobility agnostic greedy algorithms as well as virtual network embedding algorithms from the literature. Numerical investigations reveal that the effect of user mobility has a significant impact on the design of virtual networks. Additionally, the mobility aware scheme can provide tangible gains in the overall performance compared with the previous proposed schemes that do not take explicitly into account the effect of user mobility.