Counting ancestors to estimate authority

ABSTRACT

The AncestorRank algorithm calculates an authority score by using just one characteristic of the web graph-the number of ancestors per node. For scalability, we estimate the number of ancestors by using a probabilistic counting algorithm. We also consider the case in which ancestors which are closer to the node have more influence than those farther from the node. Thus we further apply a decay factor delta on the contributions from successively earlier ancestors. The resulting authority score is used in combination with a content-based ranking algorithm. Our experiments show that as long as delta is in the range of [0.1, 0.9], AncestorRank can greatly improve BM25 performance, and in our experiments is often better than PageRank.

REFERENCES

• 1: Luca Becchetti , Carlos Castillo , Debora Donato , Ricardo Baeza-YATES , Stefano Leonardi, Link analysis for Web spam detection, ACM Transactions on the Web (TWEB), v.2 n.1, p.1-42, February 2008 [doi>10.1145/1326561.1326563]
• 2: 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
• 3: 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]
• 4: Philippe Flajolet , G. Nigel Martin, Probabilistic counting algorithms for data base applications, Journal of Computer and System Sciences, v.31 n.2, p.182-209, Sept. 1985 [doi>10.1016/0022-0000(85)90041-8]
• 5: Christopher R. Palmer , Phillip B. Gibbons , Christos Faloutsos, ANF: a fast and scalable tool for data mining in massive graphs, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775059]
• 6: Kalervo Järvelin , Jaana Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM Transactions on Information Systems (TOIS), v.20 n.4, p.422-446, October 2002 [doi>10.1145/582415.582418]
• 7: 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]
• 8: S. E. Robertson. Overview of the OKAPI projects. Journal of Documentation, 53(1):3--7, 1997.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
PageRank, link analysis, probabilistic counting