WEB RECOMMENDATION SYSTEM BASED ON A MARKOV-CHAIN MODEL

Francois Fouss, Stephane Faulkner, Manuel Kolp, Alain Pirotte, Marco Saerens

2005

Abstract

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.

Paper Citation

in Harvard Style

Fouss F., Faulkner S., Kolp M., Pirotte A. and Saerens M. (2005). WEB RECOMMENDATION SYSTEM BASED ON A MARKOV-CHAIN MODEL . In Proceedings of the Seventh International Conference on Enterprise Information Systems - Volume 4: ICEIS, ISBN 972-8865-19-8, pages 56-63. DOI: 10.5220/0002550700560063

in Bibtex Style

@conference{iceis05,
author={Francois Fouss and Stephane Faulkner and Manuel Kolp and Alain Pirotte and Marco Saerens},
title={WEB RECOMMENDATION SYSTEM BASED ON A MARKOV-CHAIN MODEL},
booktitle={Proceedings of the Seventh International Conference on Enterprise Information Systems - Volume 4: ICEIS,},
year={2005},
pages={56-63},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002550700560063},
isbn={972-8865-19-8},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Seventh International Conference on Enterprise Information Systems - Volume 4: ICEIS,
TI - WEB RECOMMENDATION SYSTEM BASED ON A MARKOV-CHAIN MODEL
SN - 972-8865-19-8
AU - Fouss F.
AU - Faulkner S.
AU - Kolp M.
AU - Pirotte A.
AU - Saerens M.
PY - 2005
SP - 56
EP - 63
DO - 10.5220/0002550700560063