Topical link analysis for web search

ABSTRACT

Traditional web link-based ranking schemes use a single score to measure a page's authority without concern of the community from which that authority is derived. As a result, a resource that is highly popular for one topic may dominate the results of another topic in which it is less authoritative. To address this problem, we suggest calculating a score vector for each page to distinguish the contribution from different topics, using a random walk model that probabilistically combines page topic distribution and link structure. We show how to incorporate the topical model within both PageRank and HITS without affecting the overall property and still render insight into topic-level transition. Experiments on multiple datasets indicate that our technique outperforms other ranking approaches that incorporate textual analysis.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: Krishna Bharat , Monika R. Henzinger, Improved algorithms for topic distillation in a hyperlinked environment, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.104-111, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290972]
• 3: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 4: Deng Cai , Xiaofei He , Ji-Rong Wen , Wei-Ying Ma, Block-level link analysis, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009068]
• 5: Soumen Chakrabarti , Byron E. Dom , S. Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins , David Gibson , Jon Kleinberg, Mining the Web's Link Structure, Computer, v.32 n.8, p.60-67, August 1999 [doi>10.1109/2.781636]
• 6: Soumen Chakrabarti , Byron Dom , Prabhakar Raghavan , Sridhar Rajagopalan , David Gibson , Jon Kleinberg, Automatic resource compilation by analyzing hyperlink structure and associated text, Proceedings of the seventh international conference on World Wide Web 7, p.65-74, April 1998, Brisbane, Australia
• 7: Google, Inc. Google information for webmasters. Retrieved 9 November 2005 from the Google Website: http://www.google.com/webmasters/4.html, 2005.
• 8: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 9: IBM Almaden Research Center. The CLEVER Project. Home page: htmladdnormallinkfamily http://www.almaden.ibm.com/cs/k53/clever.html, 2000.
• 10: K. M. Jiang, G. R. Xue, H. J. Zeng, X. Chen, W. Song, and W.-Y. Ma. Exploiting PageRank analysis at different block level. In Proceedings of the 5th Conference on Information Systems Engineering, 2004.
• 11: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 12: R. Lempel , S. Moran, The stochastic approach for link-structure analysis (SALSA) and the TKC effect, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.387-401, June 2000, Amsterdam, The Netherlands
• 13: Open Directory Project (ODP), 2006. http://www.dmoz.com/.
• 14: L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the Web. Unpublished draft, 1998.
• 15: Sankar K. Pal , B. L. Narayan , Soumitra Dutta, A Web Surfer Model Incorporating Topic Continuity, IEEE Transactions on Knowledge and Data Engineering, v.17 n.5, p.726-729, May 2005 [doi>10.1109/TKDE.2005.69]
• 16: Rainbow: text classification tool. http://www.cs.umass.edu/~mccallum/bow/rainbow/.
• 17: M. Richardson and P. Domingos. The intelligent surfer: Probabilistic combination of link and content information in PageRank. In Advances in Neural Information Processing Systems 14. MIT Press, 2002.
• 18: S. E. Robertson. Overview of the OKAPI projects. Journal of Documentation, 53:3--7, 1997.
• 19: Baoning Wu , Brian D. Davison, Identifying link farm spam pages, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062762]
• 20: Yahoo!, Inc. Yahoo! http://www.yahoo.com/ 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Performance

Keywords:
HITS, link analysis, pagerank, web search engine