The explosive growth of the World Wide Web leads to fast advancing of E-Commerce techniques. Recommender systems, which use personalized information filtering techniques to generate a set of items suitable to a given user, have received considerable attention. User- and item-based algorithms are two popular techniques for the design of recommender systems. Both types are known to have Cold-Start problems – i.e., they are unable to effectively handle Cold-Start users who have an extremely limited number of purchase records. In this paper, we develop TrustRank, a novel recommender system which tackles the cold-start problem by leveraging the user-trust networks commonly available for recommender systems. A user-trust network is formed by friendships or trust relationships that users specify among themselves. While it is straightforward to conjecture that a user-trust network is helpful for improving the accuracy of recommendations, a key challenge for using such a network to facilitate Cold-Start users is that these users also tend to have a very limited number of trust relationships specified in the network. To address this challenge, we propose a pre-processing propagation of the cold-start user’s trust network. In particular, by applying the personalized PageRank algorithm, we expand the trustees of a given user to include others with similar purchase records to the user as well as its original trustees. To make such a propagation algorithm scalable to a large amount of users, as required by real-world recommender systems, we devise an efficiency-improving enhancement of the original personalized TrustRank algorithm which shortens the computational overhead by orders of magnitude through decomposing the personalized trust vector into partial vectors and hubs skeleton vi computations. We conduct extensive experiments to demonstrate the significant improvement provided by our proposed algorithm over the existing ones on the accuracy of recommendations for Cold-Star users