When organizing information it is common to use either a hierarchy or tags. An element in a hierarchy is ordered within a predefined category and relates to other elements as above, below or at the same level. The only direct link between elements in an hierarchy is its immediate superior and the elements subordinates.
Tags on the other hand are non-hierarchical keywords assigned to an element. There are no links between tags, and elements can have tags on different hierarchical level which in a strict hierarchy would not be possible.
Paul Heymann and Hector Garcia-Molina wrote a technical report in 2006 on the tag hierarchy topic with the title "Collaborative Creation of Communal Hierarchical Taxonomies in Social Tagging Systems". They came to the conclusion that it is possible to have relations among tags in several hierarchies, linked by top level connections and noisy edges (see image from their paper):
Fig 1: Latent Hierachical Taxonomy. Haymann and Garcia-Molina 2006
At first glance this is a graph representation, which could very well be used on tags in any tagging system. It would place tags in a strict hierarchy (when appropriate) and provide noisy edges or top level connections when linking relational between different hierarchies.
From my point of view it could be used to improve navigation not only using the standard hierarchical navigation and/or tags, but also use a tag hierarchy. It would place tags within a context, which from a usability perspective could improve users ability to find information.
But from what I know, the implementation of this or similar model have not yet been done. Have there been an implementation of a tag hierarchy with graph edge relations?