Paper 2009/557

Towards a Theory of Trust Based Collaborative Search

Yacov Yacobi

Abstract

We developed three new theoretical insights into the art of hierarchical clustering in the context of web-search. A no- table example where these results may be useful is Trust Based Collaborative Search, where an active user consults agents that in the past performed a similar search. We pro- ceed with this as an example throughout the paper, even though the results are more broadly applicable. The …rst result is that under plausible conditions, trust converges to the extremes, creating clusters of maximal trust. The trust between any two agents, whose initial mutual trust is not maximal, eventually vanishes. In practice there is uncer- tainty about data, hence we have to approximate the …rst result with less than maximal trust. We allow clustering tolerance equal to the uncertainty at each stage. The sec- ond result is that in the context of search, under plausible assumptions, this uncertainty converges exponentially fast as we descend the clustering tree. The third observation is that Shannon's cryptography may help estimate that uncer- tainty.