An ever increasing use of virtualization in various emerging scenarios, e.g.: Cloud Computing, Software Defined Networks, Data Streaming Processing, asks Infrastructure Providers (InPs) to optimize the allocation of the virtual network requests (VNRs) into a substrate network while satisfying QoS requirements. In this work, we propose MCRM, a two-stage virtual network embedding (VNE) algorithm with delay and placement constraints. Our solution revolves around a novel notion of similarity between virtual and physical nodes. To this end, taking advantage of Markov Reward theory, we define a set of metrics for each physical and virtual node which captures the amount of resources in a node neighborhood as well as the degree of proximity among nodes. By defining a notion of similarity between nodes we then simply map virtual nodes to the most similar physical node in the substrate network. We have thoroughly evaluated our algorithm through simulation. Our experiments show that MCRM achieves good performance results in terms of blocking probability and revenues for the InP, as well as a high and uniform utilization of resources, while satisfying the delay and placement requirements.