Biased random walk improving fairness through group constraints on expected visit rates

Details

Supervisors

Saerens, Marco

Faculty

Louvain School of Management

Degree label

Master [60] en sciences de gestion

Abstract

The purpose of this work is to improve the study of fairness for the PageRank algorithm. The proposed concept draws inspiration from an existing random walk model. The design of this random walk model was inspired from the bag-of-paths framework. Given a weighted directed graph G and a non-negative cost assigned to each node, the random walk is defined as the policy minimizing the expected cost rate while maintaining a constant relative entropy rate. Furthermore, this particular model is supplied with specific capacity constraints that restrict the expected visit rate of nodes. This study extends the existing model by generalizing the individual constraints to incorporate group capacity constraints. Additionally, a biased random walk model with lower bounds on expected visit rates of node groups were also derived. Moreover, a third model was developed that integrates both sorts of constraints. Ultimately, algorithms were developed to compute the optimal policy while taking into account the aforementioned constraints. In order to emphasize the fairness of the derived models, they were employed in a collaborative recommendation issue using the well-known ItemRank algorithm.