Fully personalized PageRank and algebraic methods to distribute a random walker

Gonzalo Contreras-Aso, Regino Criado, Miguel Romance · 2025

Read Fully personalized PageRank and algebraic methods to distribute a random walker by Gonzalo Contreras-Aso, Regino Criado, Miguel Romance (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-19927.txt.

Introduction

Gonzalo Contreras-Aso, Regino Criado, and Miguel Romance ask how fully a random walker's resting distribution can be controlled. Their 2025 paper works with PageRank-like centralities, where a walker wanders a network and the share of time spent at each node becomes its importance score. Control can come from editing the network or from tuning the walk's parameters.

The team gathers and extends what is known about both levers. They characterize when every node's score can be set at will, and the weaker goal of setting only the ranking, with bounds on the parameters needed. Alongside classic PageRank they treat two generalizations, one with damping that varies by node and one with a personalization vector that varies by node, the latter new in the literature. They also study rivals and leaders in the rankings, showing how parameter shifts reorder importance. The work maps the algebra of steering attention in networks.

Catalog record

CREATORGonzalo Contreras-Aso, Regino Criado, Miguel Romance
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-19927

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fully personalized PageRank and algebraic methods to distribute a random walker Gonzalo Contreras-Aso, Regino Criado, Miguel Romance Abstract We present a comprehensive analysis of algebraic methods for controlling the stationary distribution of PageRank-like random walkers. Building upon existing literature, we compile and extend results regarding both structural control (through network modifications) and parametric control (through measure parameters) of these centralities. We characterize the conditions for complete control of centrality scores and the weaker notion of ranking control, establishing bounds for the required parameters. Our analysis includes classical PageRank alongside two generalizations: node-dependent dampings and node-dependent personalization vector, with the latter being a novel idea in the literature. We examine how their underlying random walk structures affect their controllability, and we also investigate the concepts of competitors and leaders in centrality rankings, providing insights into how parameter variations can influence node importance hierarchies. These results advance our understanding of the interplay between algebraic control and stochastic dynamics in network centrality measures. keywords Graph theory, PageRank, random walker 1 Introduction Network centrality measures have emerged as fundamental tools in the analysis of complex systems, providing crucial insights into node importance across diverse applications ranging from social network analysis to biological systems Boccaletti et al. 2006 ; Newman 2010 . Among these measures, spectral centralities Vigna 2016 - and particularly PageRank Page et al. 1998 and its variants - hold special significance due to their deep connection to stochastic processes, while still retaining algebraic tractability. PageRank can be interpreted as the stationary distribution of a random walk on a graph, where a “random surfer” moves through the network following edges with probability \alpha and teleports to random nodes with probability 1- \alpha . This interpretation through the lens of Markov processes provides both theoretical elegance and practical robustness to the measure Langville and Meyer 2006 . The stochastic nature of PageRank raises intriguing questions about the controllability and manipulation of such measures. How much can we influence the outcome of a random process while maintaining its essential probabilistic character? This tension between deterministic control and stochastic behavior lies at the heart of our investigation. In this paper, we conduct a comprehensive study of the controllability of PageRank scores and rankings through both structural modifications of the underlying network and parametric adjustments of the centrality measures themselves. Our analysis encompasses not only the classical PageRank algorithm but also two important variants, which introduce personalized rules for the random walk at each node: on the one hand, we consider the node-dependent damping discussed in Avrachenkov et al. 2014 , which allows for heterogeneous teleportation probabilities across the network; on the other hand we consider a novel notion of personalization in PageRank, considering a node-dependent personalization vector, something equivalent to using a “personalization matrix”. These variants introduce additional degrees of freedom in the underlying stochastic process, potentially affecting the controllability of the resulting centrality measures. Through careful application of algebraic and analytical techniques, we establish bounds on parameter regions that enable various degrees of control over these measures. We differentiate between localization (the ranges of the possible centralities attainable for each node for a fixed damping factor) García et al. 2013 , complete control (the ability to achieve specific centrality scores for all nodes) and the weaker notion of ranking control (the ordered relationship between nodes) Contreras-Aso et al. 2023 . This investigation not only advances our theoretical understanding of spectral centralities but also has practical implications for applications where influencing node importance is crucial, from search engine optimization Chaffey et al. 2009 to even biology Morrison et al. 2005 ; Gleich 2015 . By examining how the stochastic foundation of these measures interacts with our ability to control their outcomes, we provide insights into both the possibilities and limitations of centrality manipulation in complex networks. This article is structured as follows: we begin with a review of some basic concepts of spectral centrality measures and their relation to Markovian processes in Section 2 . We then discuss some novel results of structural controllability in PageRank, mainly weight tuning and self-loop score increases, in Section 3 . Section 4 provides an overview of some foundational results in the parametric controllability of PageRank (localization, complete and ranking control), which we then extend to some of its generalizations. We finish with some conclusions and outlook. A note on Search Engine Optimization Something which we have not studied is the possibility of adding new links among existing nodes, however this is a very realistic possibility in human-made networks such as the Internet: a webpage can choose which hyperlinks it creates, bridging it to other webpages. As a matter of fact, this problem has been thoroughly studied by the Computer Science community, to the point where its practice has been dubbed Search Engine Optimization or SEO Langville and Meyer 2006 , for short. Studies in this area exploded in popularity during the first decade of the 2000’s, after PageRank made its appearance and thanks to it Google became the predominant search engine, and before Google moved on to more sophisticated and modified versions of the algorithm (with several link spam filters and using Machine Learning, for instance). Plenty of websites tried to attract as much attention as possible, and therefore needed to be highly positioned in Google’s ranking. There were many attempts to mischievously exploit the algorithm via link farms or the so-called “Google bombs” Bar-Ilan 2007 ; Langville and Meyer 2006 , but there was also a vast and genuine attempt to understand thoroughly and quantitatively how did changes affect the PageRank centrality. For the interested reader, we refer them to Avrachenkov and Litvak 2006 ; Olsen 2010 ; Sheldon 2010 ; Fercoq et al. 2013 ; Csáji et al. 2014 and the references therein. 2 Preliminary notions Centrality measures are fundamental tools in network analysis, used to identify the most influential nodes in a graph. These measures quantify a node’s importance based on its position and relationships within the network structure. Centrality can be interpreted in various ways, leading to diverse metrics such as degree centrality, and betweenness centrality, each capturing different aspects of influence. Among these, spectral centrality measures leverage the eigenvalues and eigenvectors of matrices representing the network, most notably the adjacency matrix. Spectral centralities are particularly interesting for their mathematical tractability as well as for their computational efficiency, as compared to, for instance, the betweenness centrality. In this section we are going to briefly summarize the most relevant spectral centralities in graphs, with a particular focus on PageRank and two of its variants, which can be understood through the lens of both linear algebra as well as stochastic processes. 2.1 Spectral centrality measures in graphs Let G=(V,E) be a graph with node set V and edge set E\subseteq V\times V . We denote as N=|V| the number of nodes, L=|E| the number of edges. If for each edge (i,j)\in E (j,i)\in E , then the graph is undirected, otherwise directed. We will often consider weighted graphs as well, i.e. we endow the graph with a function w:E\rightarrow\mathbb{R} . For reasons which will be clear soon, we will only consider positive weightings, w(i,j)>0 . Lastly, we will at one point consider multigraphs as well: these can

Read the complete text