Abstract |
: |
[eng] This work presents some general procedures for computing dissimilarities between elements of a database or, more generally, nodes of a weighted, undirected, graph. It is based on a Markov-chain model of random walk through the database. The model assigns transition probabilities to the links between elements, so that a random walker can jump from element to element. A quantity, called the average first-passage time, computes the average number of steps needed by a random walker for reaching element k for the first time, when starting from element i. A closely related quantity, called the average commute time, provides a distance measure between any pair of elements. These quantities, representing dissimilarities between any two elements, have the nice property of decreasing when the number of paths connecting two elements increases and when the "length" of any path decreases. The model is applied on a collaborative filtering task. |