Abstract
Motivated by numerous models of representing trust and distrust within a graph ranking system, we examine a quantitative vertex ranking with consideration of the influence of a subset of nodes. An efficient algorithm is given for computing Dirichlet PageRank vectors subject to Dirichlet boundary conditions on a subset of nodes. We then give several algorithms for various trust-based ranking problems using Dirichlet PageRank with boundary conditions, showing several applications of our algorithms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Andersen, R., Borgs, C., Chayes, J., Feige, U., Flaxman, A., Kalai, A., Mirrokni, V., Tennenholtz, M.: Trust-based recommendation systems: an axiomatic approach. In: WWW 2008 (2008)
Baeza-Yates, R., Castillo, C., López, V.: PageRank increase under different collusion topologies. In: Proceedings of the 1st International Workshop on Adversarial Information Retrieval on the Web (2005)
Benczur, A., Csalogany, K., Sarlos, T., Uher, M.: SpamRank — fully automatic link spam detection. In: Proceedings of the 1st International Workshop on Adversarial Information Retrieval on the Web (2005)
Borgs, C., Chayes, J., Kalai, A.T., Malekian, A., Tennenholtz, M.: A novel approach to propagating distrust. In: Saberi, A. (ed.) WINE 2010. LNCS, vol. 6484, pp. 87–105. Springer, Heidelberg (2010)
Brin, S., Page, L.: The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems 30(1-7), 107–117 (1998)
Cheng, A., Friedman, E.: Sybilproof reputation mechanisms. In: Proceedings of Third Workshop on Economics of Peer-to-Peer Systems (2005)
Chung, F.: PageRank as a discrete Green’s function. Geometry and Analysis I ALM 17, 285–302 (2010)
Chung, F.: Spectral Graph Theory. AMS Publications, Providence (1997)
Chung, F., Yau, S.-T.: Discrete Green’s functions. J. Combinatorial Theory (A) 91, 191–214 (2000)
Chung, F., Zhao, W.: A sharp PageRank algorithm with applications to edge ranking and graph sparsification. In: Kumar, R., Sivakumar, D. (eds.) WAW 2010. LNCS, vol. 6516, pp. 2–14. Springer, Heidelberg (2010)
Guha, R., Kumar, R., Raghavan, P., Tomkins, A.: Propagation of trust and distrust. In: WWW 2004 (2004)
Gyöngyi, Z., Garcia-Molina, H., Pedersen, J.: Combating Web spam with TrustRank. In: VLDB 2004 (2004)
Haveliwala, T.: Topic-sensitive PageRank: A context-sensitive ranking algorithm for Web search. IEEE Transactions on Knowledge and Data Engineering 15, 784–796 (2004)
Jeh, G., Widom, J.: Scaling personalized Web search. In: WWW 2003 (2003)
Kamvar, S., Schlosser, M., Garcia-Molina, H.: The EigenTrust algorithm for reputation management in P2P networks. In: WWW 2003 (2003)
de Kerchove, C., Dooren, P.: The PageTrust algorithm: how to rank Web pages when negative links are allowed? In: Proceedings of the SIAM International Conference on Data Mining (2008)
Spielman, D.A., Teng, S.-H.: Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems (2008), http://arxiv.org/abs/cs.NA/0607105
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chung, F., Tsiatas, A., Xu, W. (2011). Dirichlet PageRank and Trust-Based Ranking Algorithms. In: Frieze, A., Horn, P., Prałat, P. (eds) Algorithms and Models for the Web Graph. WAW 2011. Lecture Notes in Computer Science, vol 6732. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21286-4_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-21286-4_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21285-7
Online ISBN: 978-3-642-21286-4
eBook Packages: Computer ScienceComputer Science (R0)