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. |