Extracting tag hierarchies

Abstract

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 numerous independent people. Here we present a complete framework for automated tag hierarchy extraction based on tag occurrence statistics. Along with proposing new algorithms, we are also introducing different quality measures enabling the detailed comparison of competing approaches from different aspects. Furthermore, we set up a synthetic, computer generated benchmark providing a versatile tool for testing, with a couple of tunable parameters capable of generating 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 applications.

25 pages with 21 pages of supporting information, 25 figures

References in corpus (15)

• Uncovering the overlapping community structure of complex networks in nature and society
• Statistical physics of social dynamics
• Benchmark graphs for testing community detection algorithms
• Comparing community structure identification
• Hierarchical structure and the prediction of missing links in networks
• Detecting the overlapping and hierarchical community structure of complex networks
• Hierarchical group dynamics in pigeon flocks
• Nonequilibrium phase transition in the coevolution of networks and opinions
• Collaborative Tagging and Semiotic Dynamics
• Generic Absorbing Transition in Coevolution Dynamics
• Consensus formation on adaptive networks
• Random hypergraphs and their applications
• Collective dynamics of social annotation
• Preferential attachment of communities: the same principle, but a higher level
• Measuring the Hierarchy of Feedforward Networks

Cited by in corpus (9)

• Technological novelty profile and invention's future impact
• Eugene Garfield's Scholarly Impact: A Scientometric Review
• Latent geometry of bipartite networks
• Hierarchical networks of scientific journals
• Extraction of Temporal Networks from Term Co-occurrences in Online Textual Sources
• Comparing the hierarchy of keywords in on-line news portals
• Towards a generalization of information theory for hierarchical partitions
• Extracting hierarchical backbones from bipartite networks
• Comparing the hierarchy of author given tags and repository given tags in a large document archive