  Many information systems use tags and keywords to describe and annotate
content. These allow for efficient organization and categorization of items, as
well as facilitate relevant search queries. As such, the selected set of tags
for an item can have a considerable effect on the volume of traffic that
eventually reaches an item. In settings where tags are chosen by an item's
creator, who in turn is interested in maximizing traffic, a principled approach
for choosing tags can prove valuable. In this paper we introduce the problem of
optimal tagging, where the task is to choose a subset of tags for a new item
such that the probability of a browsing user reaching that item is maximized.
We formulate the problem by modeling traffic using a Markov chain, and asking
how transitions in this chain should be modified to maximize traffic into a
certain state of interest. The resulting optimization problem involves
maximizing a certain function over subsets, under a cardinality constraint. We
show that the optimization problem is NP-hard, but nonetheless has a simple
(1-1/e)-approximation via a simple greedy algorithm. Furthermore, the structure
of the problem allows for an efficient implementation of the greedy step.To
demonstrate the effectiveness of our method, we perform experiments on three
tagging datasets, and show that the greedy algorithm outperforms other
baselines.
