Many web-based software systems have been developed in the form of composite services. It is important to accurately predict the Quality of Service (QoS) value of atomic web services because the performance of such composite services depends greatly on the performance of the atomic web service adopted. In recent years, collaborative filtering based methods for predicting the web service QoS values have been proposed. However, they are mainly faced with a cold start problem that is difficult to make reliable prediction due to highly sparse historical data, newly introduced users and web services, and the existing work only deals with the case of newly introduced users. In this article, we propose a Location-based Matrix Factorization using a Preference Propagation method (LMF-PP) to address the cold start problem. LMF-PP fuses invocation and neighborhood similarity, and then the fused similarity is utilized by preference propagation. LMF-PP is compared with existing approaches on the real world dataset. Based on the experimental results, LMF-PP shows better performance than existing approaches in cold start environments as well as in warm start environments.