Extracting tag hierarchies
arXiv:1401.5741 · doi:10.1371/journal.pone.0084133
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.
arXiv comment25 pages with 21 pages of supporting information, 25 figures
References in corpus (29)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- Community structure in social and biological networks
- Community detection in graphs
- Uncovering the overlapping community structure of complex networks in nature and society
- Hierarchical organization of modularity in metabolic networks
- 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
- Self-similar community structure in organisations
- Hierarchical group dynamics in pigeon flocks
- Recommender Systems
- 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
- Cooperation and the Emergence of Role Differentiation in the Dynamics of Social Networks
- Hierarchy measure for complex networks
- On the Origins of Hierarchy in Complex Networks
- Collective dynamics of social annotation
- Hierarchy Measures in Complex Networks
- Hypergraph topological quantities for tagged social networks
- Preferential attachment of communities: the same principle, but a higher level
- Collaborative tagging as a tripartite network
- Measuring the Hierarchy of Feedforward Networks
- Ontologies and tag-statistics
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