Abstract: To obtain information quickly and accurately from Internet is very important. Recommendation according to trust relationship between users is a very effective method to get information rapidly, however trust relationship is usually very sparse, it is hard to achieve appropriate trust relationship, which influences the recommendation results. This paper proposes a method which converts the process of extending trust relationship into the problem of maximum flow match of trust, and calculates the trust relationship based on the maximum flow between users. The experimental results in Epinions dataset show that the method for finding trust relationship based on maximum flow is more accurate than the probability-based matrix decomposition, social recommendation, trust and distrust-based recommendation methods.

Key words: trust relationship, maximum flow, bipartite graph

摘要： 从互联网海量信息中快速准确地获取有效的信息变得非常重要。依据用户间信任关系给出推荐是一种非常有效的快速获取信息的方法，然而用户间信任关系通常非常的稀疏，很难为用户找到合适的信任关系，极大地影响了推荐效果。提出将扩展用户信任关系的过程转化成求解用户间信任最大流的问题，通过求解用户集合中的最大流得到用户信任关系。在Epinions数据集上的实验结果表明，基于最大流求解的信任关系给出的推荐比基于概率的矩阵分解、社会推荐、基于信任和不信任推荐方法有更好的效果。

关键词: 信任关系, 最大流, 二分图