Timezone: »

ChoiceRank: Identifying Preferences from Node Traffic in Networks
Lucas Maystre · Matthias Grossglauser

Mon Aug 07 08:30 PM -- 08:48 PM (PDT) @ C4.1

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.

Author Information

Lucas Maystre (EPFL)
Matthias Grossglauser (EPFL)

Matthias Grossglauser is Associate Professor in the School of Computer and Communication Sciences at EPFL. His current research interests are in machine learning for large social systems, stochastic models and algorithms for graph and mobility mining, and recommender systems. He is also the current director of the Doctoral School in Computer and Communication Sciences. From 2007-2010, he was with the Nokia Research Center (NRC) in Helsinki, Finland, serving as head of the Internet Laboratory, and later as head of a tech-transfer program focused on data mining, analytics, and machine learning. In addition, he served on Nokia's CEO Technology Council, a technology advisory group reporting to the CEO. Prior to this, he was Assistant Professor at EPFL, and a Research Scientist in the Networking and Distributed Systems Laboratory at AT&T Research in New Jersey. He received the 1998 Cor Baayen Award from the European Research Consortium for Informatics and Mathematics (ERCIM), the 2006 CoNEXT/SIGCOMM Rising Star Award, and two best paper awards. He served on the editorial board of IEEE/ACM Transactions on Networking, and on numerous Technical Program Committees.

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors