Dirichlet PageRank and Ranking Algorithms Based on Trust and Distrust
Fan Chung, Alexander Tsiatas, Wensong Xu · Internet Mathematics · 2013
Motivated by numerous models of representing trust and distrust within a network ranking system, we examine a quantitative vertex ranking with consideration of the influence of a subset of nodes. We propose and analyze a general ranking metric, called _Dirichlet PageRank_, which gives a ranking of vertices in a subset _S_ of nodes subject to some specified conditions on the vertex boundary of _S_. In addition to the usual Dirichlet boundary condition (which disregards the influence of nodes outside of _S_), we consider general boundary conditions allowing the presence of negative (distrustful) nodes or edges. We give an efficient approximation algorithm for computing Dirichlet PageRank vectors. Furthermore, we give several algorithms for solving various trust-based ranking problems using Dirichlet PageRank with general boundary conditions.