Link analysis using time series of web graphs

ABSTRACT

Link analysis is a key technology in contemporary web search engines. Most of the previous work on link analysis only used information from one snapshot of web graph. Since commercial search engines crawl the Web periodically, they will naturally obtain time series data of web graphs. The historical information contained in the series of web graphs can be used to improve the performance of link analysis. In this paper, we argue that page importance should be a dynamic quantity, and propose defining page importance as a function of both PageRank of the current web graph and accumulated historical page importance from previous web graphs. Specifically, a novel algorithm named TemporalRank is designed to compute the proposed page importance. We try to use a kinetic model to interpret this page importance and show that it can be regarded as the solution to an ordinary differential equation. Experiments on link analysis using web graph data in five snapshots show that the proposed algorithm can outperform PageRank in many measures, and can effectively filter out newly appeared link spam websites.

REFERENCES

• 1: Berberich, K., Vazirgiannis, M., and Weikum, G. T-Rank: Time-aware Authority Ranking. In Algorithms and Models for the Web-Graph: Third International Workshop, WAW 2004, pages: 131--141, Springer-Verlag, 2004.
• 2: Paolo Boldi , Massimo Santini , Sebastiano Vigna, PageRank as a function of the damping factor, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060827]
• 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: Gyongyi, Z., and Garcia-Molina, H. Link spam alliances. Technical Report, Stanford University, 2005.
• 5: Gyongyi, Z., and Garcia-Molina, H. Web spam Taxonomy. In the First International Workshop on Adversarial Information Retrieval on the Web, 2005.
• 6: 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]
• 7: Haveliwala, T., Kamvar, S., and Jeh, G. An analytical comparison of approaches to personalizing PageRank. Technical Report, Stanford University, 2003.
• 8: 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]
• 9: Langville, A., and Meyer, C. Deeper inside PageRank. Internet Mathematics 1(3):335--380, 2004.
• 10: Frank McSherry, A uniform approach to accelerated PageRank computation, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060829]
• 11: Page, L., Brin, S., Motwani, R., and Winograd, T. The PageRank citation ranking: Bringing order to the web. Technical Report, Stanford University, Stanford, CA, 1998.
• 12: Matthew Richardson , Amit Prakash , Eric Brill, Beyond PageRank: machine learning for static ranking, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135881]
• 13: Philip S. Yu , Xin Li , Bing Liu, Adding the Temporal Dimension to Search " A Case Study in Publication Search, Proceedings of the 2005 IEEE/WIC/ACM International Conference on Web Intelligence, p.543-549, September 19-22, 2005 [doi>10.1109/WI.2005.21]

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:
link analysis, page importance, pagerank, search engine, temporal information