Beyond Shortest Paths: Node Fairness in Route Recommendation

Traditionally, route recommendation systems focused on minimizing distance (or time) to travel between two points. However, recent attention has shifted to other factors beyond mere length. This paper addresses the challenge of ensuring a fair distribution of visits among network nodes when handling a high volume of point-to-point path queries. In doing so, we adopt a Rawlsian notion of individual-level fairness exploiting the power of randomization. Specifically, we aim to create a probabilistic distribution over paths that maximizes the minimum probability of any eligible node being included in the recommended path.

A key idea of our work is the notion of forward paths , i.e., paths where travelling along any edge decreases the distance to the destination. In unweighted graphs forward paths and shortest paths coincide, but in weighted graphs forward paths provide a richer set of alternative routes, involving many more nodes while remaining close in length to the shortest path. Thus, they offer diversity and a wider basis for fairness, while maintaining near-optimal path lengths. We devise an algorithm that extracts a directed acyclic graph (DAG) containing all the forward paths in the input graph, with the same computational runtime as solving a single shortest-path query. This avoids enumerating all possible forward paths, which can be exponential in the number of nodes. We then design a flow problem on this DAG to derive the probabilistic distribution over forward paths with the desired fairness property, solvable in polynomial time through a sequence of small linear programs.

Our experiments on real-world datasets validate our theoretical results, demonstrating that our technique provides individual node satisfaction while maintaining near-optimal path lengths. Moreover, our experiments show that our method can handle networks with millions of nodes and edges on a commodity laptop, and scales better than the baselines when there is a large volume of path queries for the same source and destination pair.