ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2017, Vol. 54 ›› Issue (7): 1426-1438.doi: 10.7544/issn1000-1239.2017.20160302

Previous Articles     Next Articles

An Efficient Collaborative Filtering Algorithm Based on Graph Model and Improved KNN

Meng Huanyu1, Liu Zhen1, Wang Fang2, Xu Jiadong1, Zhang Guoqiang3   

  1. 1(School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044);2(Information Technology Center, Beijing Jiaotong University, Beijing 100044);3(School of Computer Science and Technology, Nanjing Normal University, Nanjing 210023)
  • Online:2017-07-01

Abstract: With the rapid development of Internet, recommender system has been considered as a typical method to deal with the over-loading of Internet information. The recommender system can partially alleviate user’s difficulty on information filtering and discover valuable information for the active user. Collaborative filtering algorithm has the advantages of domain independence and supports users’ potential interests. For these reasons, collaborative filtering has been widely used. Because the user item rating matrix is sparse and in large-scale, recommender system is facing big challenges of precision and performance. This paper puts forward a GK-CF algorithm. By building a graph-based rating data model, the traditional collaborative filtering, graph algorithms and improved KNN algorithm have been integrated. Through the message propagation in the graph and the improved user similarity calculation model, candidate similar users will be selected firstly before the calculation of users similarity. Based on the topology of bipartite graph, the GK-CF algorithm ensures the quick and precise location of the candidate items through the shortest path algorithm. Under the parallel graph framework, GK-CF algorithm has been parallelized design and implement. The experiments on real world clusters show that: compared with the traditional collaborative filtering algorithm, the GK-CF algorithm can better improve recommendation precision and the rating accuracy. The GK-CF algorithm also has good scalability and real-time performance.

Key words: collaborative filtering, social network, graph model, KNN, shortest path

CLC Number: