Computing trusted authority scores in peer-to-peer web search networks

ABSTRACT

Peer-to-peer (P2P) networks have received great attention for sharing and searching information in large user communities. The open and anonymous nature of P2P networks is one of its main strengths, but it also opens doors to manipulation of the information and of the quality ratings.

In our previous work (J. X. Parreira, D. Donato, S. Michel and G. Weikum in VLDB 2006) we presented the JXP algorithm for distributed computing PageRank scores for information units (Web pages, sites, peers, social groups, etc.) within a link- or endorsement-based graph structure. The algorithm builds on local authority computations and bilateral peer meetings with exchanges of small data structures that are relevant for gradually learning about global properties and eventually converging towards global authority rankings.

In the current paper we address the important issue of cheating peers that attempt to distort the global authority values, by providing manipulated data during the peer meetings. Our approach to this problem enhances JXP with statistical techniques for detecting suspicious behavior. Our method, coined Trust JXP, is again completely decentralized, and we demonstrate its viability and robustness in experiments with real Web data.

REFERENCES

• 1: Zoë Abrams , Robert McGrew , Serge Plotkin, A non-manipulable trust system based on EigenTrust, ACM SIGecom Exchanges, v.5 n.4, p.21-30, July, 2005 [doi>10.1145/1120717.1120721]
• 2: Luca Becchetti, Carlos Castillo, Debora Donato, and Adriano Fazzone. A comparison of sampling techniques for web characterization. In LinkKDD, 2006.
• 3: András A. Benczúr, Károly Csalogány, Tamás Sarlós, and Máté Uher. Spamrank: fully automatic link spam detection. In AIRWeb, 2005.
• 4: Matthias Bender , Sebastian Michel , Peter Triantafillou , Gerhard Weikum , Christian Zimmer, MINERVA: collaborative P2P search, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 5: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 6: Andrei Z. Broder , Ronny Lempel , Farzin Maghoul , Jan Pedersen, Efficient pagerank approximation via graph aggregation, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA [doi>10.1145/1013367.1013537]
• 7: Steve Chien, Cynthia Dwork, Ravi Kumar, Daniel R. Simon, and D. Sivakumar. Link evolution: Analysis and algorithm. Internet Mathematics, 1(3):277--304, 2004.
• 8: Jason V. Davis , Inderjit S. Dhillon, Estimating the global pagerank of web communities, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150419]
• 9: Stephen Dill , Ravi Kumar , Kevin S. Mccurley , Sridhar Rajagopalan , D. Sivakumar , Andrew Tomkins, Self-similarity in the web, ACM Transactions on Internet Technology (TOIT), v.2 n.3, p.205-223, August 2002 [doi>10.1145/572326.572328]
• 10: AnHai Doan, Raghu Ramakrishnan, Fei Chen, Pedro DeRose, Yoonkyong Lee, Robert McCann, Mayssam Sayyadian, and Warren Shen. Community information management. IEEE Data Eng. Bull., 29(1):64--72, 2006.
• 11: Micah Dubinko , Ravi Kumar , Joseph Magnani , Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, Visualizing tags over time, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135810]
• 12: Ronald Fagin , Ravi Kumar , D. Sivakumar, Comparing top k lists, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 13: R. Guha , Ravi Kumar , Prabhakar Raghavan , Andrew Tomkins, Propagation of trust and distrust, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988727]
• 14: Zoltán Gyöngyi and Hector Garcia-Molina. Web spam taxonomy. In AIRWeb, 2005.
• 15: S. Kamvar, T. Haveliwala, C. Manning, and G. Golub. Exploiting the block structure of the web for computing pagerank. Technical report, Stanford University, 2003.
• 16: Sepandar D. Kamvar , Mario T. Schlosser , Hector Garcia-Molina, The Eigentrust algorithm for reputation management in P2P networks, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775242]
• 17: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
• 18: Ravi Kumar , Jasmine Novak , Andrew Tomkins, Structure and evolution of online social networks, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150476]
• 19: Amy N. Langville , Carl D. Meyer, Updating Markov Chains with an Eye on Google's PageRank, SIAM Journal on Matrix Analysis and Applications, v.27 n.4, p.968-987, 2006 [doi>10.1137/040619028]
• 20: Amy N. Langville and Carl D. Meyer. Deeper inside pagerank. Internet Mathematics, 1(3):335--380, 2003.
• 21: Amy Nicole Langville and Carl Dean Meyer. Deeper inside pagerank. Internet Mathematics, 1(3):335--400, 2004.
• 22: Lucien M Le Cam, Asymptotic methods in statistical theory, Springer-Verlag New York, Inc., New York, NY, 1986
• 23: Sergio Marti , Hector Garcia-Molina, Taxonomy of trust: categorizing P2P reputation systems, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.50 n.4, p.472-484, 15 March 2006 [doi>10.1016/j.comnet.2005.07.011]
• 24: Carl D. Meyer, Matrix analysis and applied linear algebra, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 25: Nikos Ntarmos , Peter Triantafillou, SeAl: Managing Accesses and Data in Peer-to-Peer Sharing Networks, Proceedings of the Fourth International Conference on Peer-to-Peer Computing (P2P'04), p.116-123, August 25-27, 2004 [doi>10.1109/P2P.2004.46]
• 26: Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank citation ranking: bringing order to the Web. Technical report, Stanford Digital Library Technologies Project, 1998.
• 27: Josiane Xavier Parreira, Debora Donato, and Gerhard Weikum. Efficient and decentralized pagerank approximation in a peer-to-peer web search network. In VLDS, 2006.
• 28: Josiane Xavier Parreira and Gerhard Weikum. Jxp: Global authority scores in a p2p network. In WebDB, 2005.
• 29: Sergej Sizov, Martin Theobald, Stefan Siersdorfer, Gerhard Weikum, Jens Graupmann, Michael Biwer, and Patrick Zimmer. The bingo! system for information portal generation and expert web search. In CIDR, 2003.
• 30: Natalia Stakhanova , Samik Basu , Johnny Wong , Oleg Stakhanov, Trust Framework for P2P Networks Using Peer-Profile Based Anomaly Technique, Proceedings of the Second International Workshop on Security in Distributed Computing Systems (SDCS) (ICDCSW'05), p.203-209, June 06-10, 2005 [doi>10.1109/ICDCSW.2005.137]
• 31: Ralf Steinmetz , Klaus Wehrle, Peer-to-Peer Systems and Applications (Lecture Notes in Computer Science), Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 32: Torsten Suel, Chandan Mathur, Jo wen Wu, Jiangong Zhang, Alex Delis, Mehdi Kharrazi, Xiaohui Long, and Kulesh Shanmugasundaram. Odissea: A peer-to-peer architecture for scalable web search and information retrieval. In WebDB, 2003.
• 33: Yuan Wang and David J. DeWitt. Computing pagerank in a distributed internet search system. In VLDB, 2004.
• 34: PeerTrust: Supporting Reputation-Based Trust for Peer-to-Peer Electronic Communities, IEEE Transactions on Knowledge and Data Engineering, v.16 n.7, p.843-857, July 2004 [doi>10.1109/TKDE.2004.1318566]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.4 INFORMATION SYSTEMS APPLICATIONS

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Algorithms, Security

Keywords:
P2P networks, decentralized PageRank, trust