PageRank (PR) is a challenging and important network ranking algorithm, which plays a crucial role in information technologies and numerical analysis due to its huge dimension and wide range of possible applications. The traditional approach to PR goes back to the pioneering paper of S. Brin and L. Page, who developed the initial method in order to rank websites in the search engine results. Recently, A. Juditsky and B. Polyak proposed a robust formulation of the PageRank model for the case, when links in the network structure may vary, i.e. some links may appear or disappear influencing the transportation matrix defined by the network structure. In this article, 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 (e.g. Internet) and we propose a new robust formulation of the PageRank problem for uncertain networks with fixed growth rate (i.e. the expected number of pages which appear in the future is fixed). Further, we compare our results with the ranks estimated by the method of A. Juditsky and B. Polyak, as well as with the true ranks of tested network structures. We formulate the robust PageRank in terms of non-convex optimization problems and we bound these formulations from above by convex but non-smooth optimization problems. In the numerical part of the article, we propose some smoothening techniques, which allow to obtain the solution accurately and efficiently in case of middle-size networks by the use of the well-known subgradient algorithm avoiding all non-smooth points. Furthermore, we address high-dimensional algorithms by modelling PageRank via the use of the multinomial distribution.
Citation
Available on optimization-online.
Article
View Robust PageRank: Stationary Distribution on a Growing Network Structure