Re-ranking search results using network analysis a case study with google: a case study with Google

ABSTRACT

In this paper we review methods of structured search for information on the World Wide Web. We propose new methods based on co-citation and network analysis. We describe a set of 21 measures based on these methods and examine the factor structure of those measures. We then report on a recent study that we have conducted at the University of Toronto. Human judges rated the relevance of a selection of Web pages returned by the Google search engine for each of seven queries. We compared the average judged relevance of the top 20 search results selected by Google vs. the top 20 results as selected by each of the 21 network analysis measures. All but one of the network analysis measures ("inlink") showed significantly (p<.05) better (as compared to Google) average judged relevance amongst their top 20 selections. Stepwise regression analysis was then used to identify a linear model with three network analysis measures as predictors, which accounted for roughly 17% of the variance in relevance judgments. While these results need to be extended with more detailed analysis of a wide range of queries and topics, they suggest that network analysis of search output adjacency matrices (where adjacency/proximity is based on web-wide co-citations) may significantly improve search engine rankings.

REFERENCES

• 1: Brian Amento , Loren Terveen , Will Hill, Does “authority” mean quality? predicting expert quality ratings of Web documents, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.296-303, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345603]
• 2: Allan Borodin , Gareth O. Roberts , Jeffrey S. Rosenthal , Panayiotis Tsaparas, Finding authorities and hubs from link structures on the World Wide Web, Proceedings of the 10th international conference on World Wide Web, p.415-429, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372096]
• 3: {3} Borgatti S., Everett M. and Freeman L. UCINET5, Software for social Network Analysis: User Guide, 2001.
• 4: 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
• 5: Coen Bron , Joep Kerbosch, Algorithm 457: finding all cliques of an undirected graph, Communications of the ACM, v.16 n.9, p.575-577, Sept. 1973 [doi>10.1145/362342.362367]
• 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: 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]
• 8: {8} Everett Martin G. and Borgatti Stephen P. Analyzing Clique Overlap. Connections, 21 (1), 49-61, 1998.
• 9: {9} Google Search Engine: www.google.com
• 10: Michael Gordon , Praveen Pathak, Finding information on the World Wide Web: the retrieval effectiveness of search engines, Information Processing and Management: an International Journal, v.35 n.2, p.141-180, March 1999 [doi>10.1016/S0306-4573(98)00041-7]
• 11: 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]
• 12: {12} Hanneman, Robert. Introduction to Social Network Methods. Self published at: http://faculty.ucr.edu/~hanneman/Soc157/TEX T/TextIndex.html. 2000
• 13: David Hawking , Nick Craswell , Paul Thistlewaite , Donna Harman, Results and challenges in Web search evaluation, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1321-1330, May 17, 1999
• 14: 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]
• 15: 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]
• 16: {16} Larson R. Bibliometrics of the World Wide Web: An Exploratory Analysis of the Intellectual Structure of Cyberspace, Proceedings of ASIS' 1996.
• 17: {17} Small H. and Griffith B. The structure of scientific literatures: identifying and graphing specialties. Science Studies, 4 (17), 17-40, 1974.
• 18: {18} Yaltaghian B. and Chignell M. Facilitation of Browsing the Search Engine Results: Using Co-Citation Analysis to Organize & Present the Search Results, Knowledge Network Conference - Beyond The Edge: Road Mapping Innovation, CITO, Ottawa, Oct. 2000
• 19: {19} Yaltaghian B. and Chignell M. How Good is Search Engine Ranking?: A Validation Study with Human Judges, To appear in the Annual Meeting of the Human Factors and Ergonomics Society, Baltimore, MD, Sep 2002.
• 20: Mingfang Wu , Michael Fuller , Ross Wilkinson, The role of a judge in a user based retrieval experiment (poster session), Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.331-333, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345628]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Information networks
          Nouns: World Wide Web (WWW)
  H.4 INFORMATION SYSTEMS APPLICATIONS
      H.4.3 Communications Applications
          Subjects: Information browsers

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory