Information Retrieval Under Network Uncertainty: Robust Internet Ranking

Anna Timonina-Farkas () and Ralf W. Seifert ()
Additional contact information
Anna Timonina-Farkas: École Polytechnique Fédérale de Lausanne (EPFL), EPFL-CDM-TOM, CH-1015 Lausanne, Switzerland
Ralf W. Seifert: École Polytechnique Fédérale de Lausanne (EPFL), EPFL-CDM-TOM, CH-1015 Lausanne, Switzerland; International Institute for Management Development, CH-1003 Lausanne, Switzerland

Operations Research, 2023, vol. 71, issue 6, 2328-2351

Abstract: Internet ranking algorithms play a crucial role in information technologies and numerical analysis due to their efficiency in high dimensions and wide range of possible applications, including scientometrics and systemic risk in finance (SinkRank, DebtRank, etc.). The traditional approach to internet ranking goes back to the seminal work of Sergey Brin and Larry Page, who developed the initial method PageRank (PR) in order to rank websites in search engine results. Recent works have studied robust reformulations of the PageRank model for the case when links in the network structure may vary; that is, some links may appear or disappear influencing the transportation matrix defined by the network structure. We make a further step forward, allowing the network to vary not only in links, but also in the number of nodes. We focus on growing network structures and propose a new robust formulation of the PageRank problem for uncertain networks with fixed growth rate. Defining the robust PageRank in terms of a nonconvex optimization problem, we bound our formulation from above by a convex but nonsmooth optimization problem. Driven by the approximation quality, we analyze the resulting optimality gap theoretically and demonstrate cases for its reduction. In the numerical part of the article, we propose some techniques which allow us to obtain the solution efficiently for middle-size networks avoiding all nonsmooth points. Furthermore, we propose a coordinate-wise descent method with near-optimal step size and address high-dimensional cases using multinomial transition probabilities. We analyze the impact of the network growth on ranking and numerically assess the approximation quality using real-world data sets on movie repositories and on journals on computational complexity.

Keywords: Optimization; information retrieval; robust ranking; robust optimization; uncertain networks; PageRank; World Wide Web (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2298 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:71:y:2023:i:6:p:2328-2351

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().