Design of Biased Random Walks on a Graph with Application to Collaborative Recommendation
(2020) , 32 pages
Files
2020-06_PierreLeleuxetSylvainCourtain_conf.pdf
Closed Access - Adobe PDF
- 531.92 KB
Details
- Authors
Courtain, Sylvain 
- Abstract
- This work investigates a paths-based statistical physics formalism for the design of random walks on a graph in which the transition probabilities (the policy) are optimally biased in favor of some node features. More precisely, given a weighted directed graph $G$ and a nonnegative cost assigned to each edge, the biased random walk is defined as the policy minimizing the expected cost rate along the walks while maintaining a constant relative entropy rate. The model is formulated by assigning a Gibbs-Boltzmann distribution to the set of infinite walks and allows to recover some known results from the literature, derived from a different perspective. Examples of quantities of interest are the partition function of the system, the optimal transition probabilities, the cost rate, etc. In addition, the same formalism allows to introduce capacity constraints on the expected visit rates to the nodes and an algorithm for computing the optimal policy subject to capacity constraints is developed. Simulation results indicate that the proposed procedure can be effectively used in order to define a Markov chain driving the walk towards nodes having some specific properties, like seniority, education level or low node degree (hub-avoiding walk). An application relying on this last property is proposed as a tool for improving serendipity in collaborative recommendation, and is tested on the MovieLens data.
- Affiliations
Citations
Leleux, P., Courtain, S., Françoisse, K., & Saerens, M. (2020). Design of Biased Random Walks on a Graph with Application to Collaborative Recommendation (Louvain Research Institute in Management and Organizations Working Paper Series 2020/06). https://hdl.handle.net/2078.5/167509