Web recommendation system based on a markov-chain model

Fouss, François [UCL] Faulkner, Stéphane [FUNDP] Kolp, Manuel [UCL] Pirotte, Alain [UCL] Saerens, Marco [UCL]

This work presents some general procedures for computing dissimilarities between nodes of a weighted, undirected, graph. It is based on a Markov-chain model of random walk through the graph. This method is applied on the architecture of a Multi Agent System (MAS), in which each agent can be considered as a node and each interaction between two agents as a link. The model assigns transition probabilities to the links between agents, so that a random walker can jump from agent to agent. A quantity, called the average first-passage time, computes the average number of steps needed by a random walker for reaching agent k for the first time, when starting from agent i. A closely related quantity, called the average commute time, provides a distance measure between any pair of agents. Yet another quantity of interest, closely related to the average commute time, is the pseudoinverse of the Laplacian matrix of the graph, which represents a similarity measure between the nodes of the graph. These quantities, representing dissimilarities (similarities) between any two agents, have the nice property of decreasing (increasing) when the number of paths connecting two agents increases and when the "length" of any path decreases. The model is applied on a collaborative filtering task where suggestions are made about which movies people should watch based upon what they watched in the past. For the experiments, we build a MAS architecture and we instantiated the agents belief-set from a real movie database. Experimental results show that the Laplacian-pseudoinverse based similarity outperforms all the other methods.