  The success of "infinite-inventory" retailers such as Amazon.com and Netflix
has been largely attributed to a "long tail" phenomenon. Although the majority
of their inventory is not in high demand, these niche products, unavailable at
limited-inventory competitors, generate a significant fraction of total revenue
in aggregate. In addition, tail product availability can boost head sales by
offering consumers the convenience of "one-stop shopping" for both their
mainstream and niche tastes. However, most of existing recommender systems,
especially collaborative filter based methods, can not recommend tail products
due to the data sparsity issue. It has been widely acknowledged that to
recommend popular products is easier yet more trivial while to recommend long
tail products adds more novelty yet it is also a more challenging task. In this
paper, we propose a novel suite of graph-based algorithms for the long tail
recommendation. We first represent user-item information with undirected
edge-weighted graph and investigate the theoretical foundation of applying
Hitting Time algorithm for long tail item recommendation. To improve
recommendation diversity and accuracy, we extend Hitting Time and propose
efficient Absorbing Time algorithm to help users find their favorite long tail
items. Finally, we refine the Absorbing Time algorithm and propose two
entropy-biased Absorbing Cost algorithms to distinguish the variation on
different user-item rating pairs, which further enhances the effectiveness of
long tail recommendation. Empirical experiments on two real life datasets show
that our proposed algorithms are effective to recommend long tail items and
outperform state-of-the-art recommendation techniques.
