poster

Link analysis using time series of web graphs

Authors:

Lei Yang,

Lei Qi,

Yan-Ping Zhao,

Bin Gao,

Tie-Yan LiuAuthors Info & Claims

CIKM '07: Proceedings of the sixteenth ACM conference on Conference on information and knowledge management

Pages 1011 - 1014

https://doi.org/10.1145/1321440.1321598

Published: 06 November 2007 Publication History

Get Access

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.

Google Scholar

[2]

Boldi, P., Santini, M., and Vigna, S. PageRank as a function of the damping factor. In Proceedings of the 14th International World Wide Web Conference, 2005.

Digital Library

Google Scholar

[3]

Brin, S., and Page, L. The anatomy of a large-scale hypertextual web search engine. In Proceedings of the Seventh International Wide Web Conference, Australia, 1998.

Digital Library

Google Scholar

[4]

Gyongyi, Z., and Garcia-Molina, H. Link spam alliances. Technical Report, Stanford University, 2005.

Google Scholar

[5]

Gyongyi, Z., and Garcia-Molina, H. Web spam Taxonomy. In the First International Workshop on Adversarial Information Retrieval on the Web, 2005.

Google Scholar

[6]

Haveliwala, T. Topic-sensitive PageRank. In Proceedings of the International World Wide Web Conference, 2002.

Digital Library

Google Scholar

[7]

Haveliwala, T., Kamvar, S., and Jeh, G. An analytical comparison of approaches to personalizing PageRank. Technical Report, Stanford University, 2003.

Google Scholar

[8]

Kleinberg, J. Authoritative sources in a hyperlinked environment. In Journal of the ACM, 46(5):604--632, 1999.

Digital Library

Google Scholar

[9]

Langville, A., and Meyer, C. Deeper inside PageRank. Internet Mathematics 1(3):335--380, 2004.

Crossref

Google Scholar

[10]

McSherry, F. A uniform approach to accelerated PageRank computation. In Proceedings of the 14th International World Wide Web Conference, 2005.

Digital Library

Google Scholar

[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.

Google Scholar

[12]

Richardson, M., Prakash, A., and Brill, E. Beyond PageRank: Machine Learning for Static Ranking. In Proceedings of the Fifteenth International World Wide Web Conference, pages: 707--715, 2006.

Digital Library

Google Scholar

[13]

Yu, P.S., Li, X., and Liu, B. Adding the Temporal Dimension to Search - A Case Study in Publication Search. In Proceedings of the 2005 IEEE/WIC/ACM International Conference on Web Intelligence, 2005.

Digital Library

Google Scholar

Cited By

View all

Hossain MSaule E(2022)Postmortem Computation of Pagerank on Temporal GraphsProceedings of the 51st International Conference on Parallel Processing10.1145/3545008.3545055(1-11)Online publication date: 29-Aug-2022
https://dl.acm.org/doi/10.1145/3545008.3545055
Zhang YLiang YZhao JMao FGu LLiao XJin HLiu HGuo SZeng YHu HLi CZhang JWang B(2022)EGraph: Efficient Concurrent GPU-based Dynamic Graph ProcessingIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3171588(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3171588
Byun J(2022)Enabling Time-Centric Computation for Efficient Temporal Graph Traversals From Multiple SourcesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.300567234:4(1751-1762)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TKDE.2020.3005672
Show More Cited By

Index Terms

Link analysis using time series of web graphs
1. Information systems
  1. Information retrieval

Recommendations

Searching the Web

We offer an overview of current Web search engine design. After introducing a generic search engine architecture, we examine each engine component in turn. We cover crawling, local Web page storage, indexing, and the use of link analysis for boosting ...
Time-weighted web authoritative ranking
Abstract
We investigate temporal factors in assessing the authoritativeness of web pages. We present three different metrics related to time: age, event, and trend. These metrics measure recentness, special event occurrence, and trend in revisions, ...
A Googol of Information about Google

Timothy P. Chartier reviews Google's PageRank and Beyond: The Science of Search Engine Rankings by Amy Langville and Carl Meyer.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

CIKM '07: Proceedings of the sixteenth ACM conference on Conference on information and knowledge management

November 2007

1048 pages

ISBN:9781595938039

DOI:10.1145/1321440

Co-chair:
Alberto H. F. Laender,
Conference Chairs:
André O. Falcão
Universidade de Lisboa, Portugal
,
Øystein Haug Olsen,
General Chair:
Mário J. Silva
(Universidade de Lisboa, Portugal)
,
Program Chairs:
Ricardo Baeza-Yates,
Deborah L. McGuinness,
Bjorn Olstad

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 November 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Poster

Conference

CIKM07

Sponsor:

CIKM07: Conference on Information and Knowledge Management

November 6 - 10, 2007

Lisbon, Portugal

Acceptance Rates

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
470
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hossain MSaule E(2022)Postmortem Computation of Pagerank on Temporal GraphsProceedings of the 51st International Conference on Parallel Processing10.1145/3545008.3545055(1-11)Online publication date: 29-Aug-2022
https://dl.acm.org/doi/10.1145/3545008.3545055
Zhang YLiang YZhao JMao FGu LLiao XJin HLiu HGuo SZeng YHu HLi CZhang JWang B(2022)EGraph: Efficient Concurrent GPU-based Dynamic Graph ProcessingIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3171588(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3171588
Byun J(2022)Enabling Time-Centric Computation for Efficient Temporal Graph Traversals From Multiple SourcesIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2020.300567234:4(1751-1762)Online publication date: 1-Apr-2022
https://doi.org/10.1109/TKDE.2020.3005672
Arenas MBahamondes PAghasadeghi AStoyanovich J(2022)Temporal Regular Path Queries2022 IEEE 38th International Conference on Data Engineering (ICDE)10.1109/ICDE53745.2022.00226(2412-2425)Online publication date: May-2022
https://doi.org/10.1109/ICDE53745.2022.00226
Zhang SHuang TWang D(2021)Sequence Contained Heterogeneous Graph Neural Network2021 International Joint Conference on Neural Networks (IJCNN)10.1109/IJCNN52387.2021.9533391(1-8)Online publication date: 18-Jul-2021
https://doi.org/10.1109/IJCNN52387.2021.9533391
Ali FKhusro S(2021)Content and link-structure perspective of ranking webpagesComputer Science Review10.1016/j.cosrev.2021.10039740:COnline publication date: 1-May-2021
https://dl.acm.org/doi/10.1016/j.cosrev.2021.100397
Byun JWoo SKim D(2020)ChronoGraph: Enabling Temporal Graph Traversals for Efficient Information Diffusion Analysis over TimeIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2019.289156532:3(424-437)Online publication date: 1-Mar-2020
https://doi.org/10.1109/TKDE.2019.2891565
Moffitt VStoyanovich JRompf TAlexandrov A(2017)Temporal graph algebraProceedings of The 16th International Symposium on Database Programming Languages10.1145/3122831.3122838(1-12)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1145/3122831.3122838
Vora KGupta RXu G(2016)Synergistic Analysis of Evolving GraphsACM Transactions on Architecture and Code Optimization10.1145/299278413:4(1-27)Online publication date: 25-Oct-2016
https://dl.acm.org/doi/10.1145/2992784
Nguyen TKanhabua NNiederée CZhu XBaeza-Yates RLalmas MMoffat ARibeiro-Neto B(2015)A Time-aware Random Walk Model for Finding Important Documents in Web ArchivesProceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval10.1145/2766462.2767832(915-918)Online publication date: 9-Aug-2015
https://dl.acm.org/doi/10.1145/2766462.2767832
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Searching the Web

Time-weighted web authoritative ranking

A Googol of Information about Google