Extracting tag hierarchies

Tagging items with descriptive annotations or keywords is a very natural way to compress and highlight information about the properties of the given entity. Over the years several methods have been proposed for extracting a hierarchy between the tags for systems with a ”flat”, egalitarian organization of the tags, which is very common when the tags correspond to free words given by numer-ous independent people. Here we present a complete framework for automated tag hierarchy extraction based on tag occurrence statistics. Along with propos-ing new algorithms, we are also introducing different quality measures enabling the detailed comparison of competing approaches from different aspects. Fur-thermore, we set up a synthetic, computer generated benchmark providing a versatile tool for testing, with a couple of tunable parameters capable of gener-ating a wide range of test beds. Beside the computer generated input we also use real data in our studies, including a biological example with a pre-defined hierarchy between the tags. The encouraging similarity between the pre-defined and reconstructed hierarchy, as well as the seemingly meaningful hierarchies obtained for other real systems indicate that tag hierarchy extraction is a very promising direction for further research with a great potential for practical ap-plications. Tags have become very prevalent nowadays in various online platforms rang-ing from blogs through scientific publications to protein databases. Further-more, tagging systems dedicated for voluntary tagging of photos, films, books, etc. with free words are also becoming popular. The emerging large collections of tags associated with different objects are often referred to as folksonomies, highlighting their collaborative origin and the “flat ” organization of the tags opposed to traditional hierarchical categorization. Adding a tag hierarchy cor-responding to a given folksonomy can very effectively help narrowing or broad-ening the scope of search. Moreover, recommendation systems could also benefit from a tag hierarchy