In the last few years social networks have reached an ubiquitous diffusion. Facebook, LinkedIn and Twitter now have billions of users that daily interact together and establish new connections. Users and interactions among them can be naturally represented as data graphs, whose vertices denote users and whose edges are labelled with information about the different interactions. In this paper, the authors sketch a novel approach for processing regular path queries on very large graphs. Their approach exploits Brzozowski's derivation of regular expressions to allow for a vertex-centric, message-passing-based evaluation of path queries on top of Apache Giraph.