Faced with the problem of information overload on the Internet, recommender systems have been paid more and more attention. At present, many recommendation algorithms have been proposed. However, there are two problems in these recommendation methods which must be solved. Most of them are studied in a single round of recommendation, but lots of complex systems in reality are evolving with time. Besides, the cold-start problem has always been intractable in the recommender system. Therefore, in this paper, we propose two recommendation methods (i.e., Method I and Method II) to solve the movie cold-start problem for the evolving user-movie network which is comprised of users and movies, and then examine the recommendation performance and long-term effects of these two methods in evolving networks, and evaluate influence factors through the numerical simulation. The experiment results show that the network structure, the movie attributes and the length of the recommendation list affect the recommendation accuracy and its novelty. The effects of Method I and Method II are better than those of other recommendation methods in previous works. Moreover, in Method Iwe should lay more emphasis on the relation between nodes, while in Method II we should focus on node attributes.