Efficient searching mechanism for trust-aware recommender systems based on scale-freeness of trust networks

One fundamental requirement of the trust-aware recommender system (TARS) is to efficiently find as many recommenders as possible for the active users. Existing approaches of TARS choose to search the entire trust network, which have very high computational cost. Though the trust network is the scale-free network, we show via experiments that TARS cannot find satisfactory number of recommenders by directly applying the classical searching mechanism of the scale-free network. This is because it chooses the local highest-degree node at each step of the trust propagation. Since the power of the trust network's degree distribution is not big enough, the selected nodes cannot cover superior number of users. In this paper, we propose an efficient searching mechanism, named S-Searching, for TARS based on the scale-freeness of trust networks: choosing the global highest-degree nodes to construct a Skeleton, and searching the recommenders via this Skeleton. Benefiting from the superior outdegrees of the nodes in the Skeleton, S-Searching can find the recommenders very efficiently. Experimental results show that S-Searching can find almost the same number of recommenders as that of conducting full search, which is much more than that of applying the classical searching mechanism in the scale-free network, while the computational complexity and cost is much less.