ChoiceRank: Identifying Preferences from Node Traffic in Networks

Lucas Maystre, Matthias Grossglauser
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:2354-2362, 2017.

Abstract

Understanding how users navigate in a network is of high interest in many applications. We consider a setting where only aggregate node-level traffic is observed and tackle the task of learning edge transition probabilities. We cast it as a preference learning problem, and we study a model where choices follow Luce’s axiom. In this case, the $O(n)$ marginal counts of node visits are a sufficient statistic for the $O(n^2)$ transition probabilities. We show how to make the inference problem well-posed regardless of the network’s structure, and we present ChoiceRank, an iterative algorithm that scales to networks that contains billions of nodes and edges. We apply the model to two clickstream datasets and show that it successfully recovers the transition probabilities using only the network structure and marginal (node-level) traffic data. Finally, we also consider an application to mobility networks and apply the model to one year of rides on New York City’s bicycle-sharing system.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-maystre17b, title = {{C}hoice{R}ank: Identifying Preferences from Node Traffic in Networks}, author = {Lucas Maystre and Matthias Grossglauser}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {2354--2362}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/maystre17b/maystre17b.pdf}, url = {https://proceedings.mlr.press/v70/maystre17b.html}, abstract = {Understanding how users navigate in a network is of high interest in many applications. We consider a setting where only aggregate node-level traffic is observed and tackle the task of learning edge transition probabilities. We cast it as a preference learning problem, and we study a model where choices follow Luce’s axiom. In this case, the $O(n)$ marginal counts of node visits are a sufficient statistic for the $O(n^2)$ transition probabilities. We show how to make the inference problem well-posed regardless of the network’s structure, and we present ChoiceRank, an iterative algorithm that scales to networks that contains billions of nodes and edges. We apply the model to two clickstream datasets and show that it successfully recovers the transition probabilities using only the network structure and marginal (node-level) traffic data. Finally, we also consider an application to mobility networks and apply the model to one year of rides on New York City’s bicycle-sharing system.} }
Endnote
%0 Conference Paper %T ChoiceRank: Identifying Preferences from Node Traffic in Networks %A Lucas Maystre %A Matthias Grossglauser %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-maystre17b %I PMLR %P 2354--2362 %U https://proceedings.mlr.press/v70/maystre17b.html %V 70 %X Understanding how users navigate in a network is of high interest in many applications. We consider a setting where only aggregate node-level traffic is observed and tackle the task of learning edge transition probabilities. We cast it as a preference learning problem, and we study a model where choices follow Luce’s axiom. In this case, the $O(n)$ marginal counts of node visits are a sufficient statistic for the $O(n^2)$ transition probabilities. We show how to make the inference problem well-posed regardless of the network’s structure, and we present ChoiceRank, an iterative algorithm that scales to networks that contains billions of nodes and edges. We apply the model to two clickstream datasets and show that it successfully recovers the transition probabilities using only the network structure and marginal (node-level) traffic data. Finally, we also consider an application to mobility networks and apply the model to one year of rides on New York City’s bicycle-sharing system.
APA
Maystre, L. & Grossglauser, M.. (2017). ChoiceRank: Identifying Preferences from Node Traffic in Networks. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:2354-2362 Available from https://proceedings.mlr.press/v70/maystre17b.html.

Related Material