Abstract. Twitter users get the latest tweets of their followees on their timeline. In this work we present a tweet recommendation approach, which takes advantage of the semantic relatedness of concepts that interest users. Our approach could be leveraged to build an efficient and online tweet recommender. We construct a Concept Graph (CG), containing a variety of concepts and use graph theory algorithms not yet applied in social network analysis in order to produce ranked recommendations. The usage of the Concept Graph allows us to avoid problems such as over-recommendation and over-specialization, because our method takes into account the true and objective relations between a user’s Topics of Interest (ToIs) and the Concept Graph itself. We test our method by applying it on a dataset and evaluate it by comparing the results to various state-of-the-art approaches.