Journal of Data and Information Science ›› 2017, Vol. 2 ›› Issue (2): 56-75.doi: 10.1515/jdis-2017-0008

• Research Paper • Previous Articles     Next Articles

Enhancing Navigability: An Algorithm for Constructing Tag Trees

Chen Chong1,(),Luo Pengcheng2   

  1. 1 Department of Information Management, School of Government Management, Beijing Normal University, Beijing 100875, China
    2 Peking University Library, Beijing 100871, China
  • Online:2017-02-25 Published:2017-02-25


Purpose: This study introduces an algorithm to construct tag trees that can be used as a user-friendly navigation tool for knowledge sharing and retrieval by solving two issues of previous studies, i.e. semantic drift and structural skew.

Design/methodology/approach: Inspired by the generality based methods, this study builds tag trees from a co-occurrence tag network and uses the h-degree as a node generality metric. The proposed algorithm is characterized by the following four features: (1) the ancestors should be more representative than the descendants, (2) the semantic meaning along the ancestor-descendant paths needs to be coherent, (3) the children of one parent are collectively exhaustive and mutually exclusive in describing their parent, and (4) tags are roughly evenly distributed to their upper-level parents to avoid structural skew.

Findings: The proposed algorithm has been compared with a well-established solution Heymann Tag Tree (HTT). The experimental results using a social tag dataset showed that the proposed algorithm with its default condition outperformed HTT in precision based on Open Directory Project (ODP) classification. It has been verified that h-degree can be applied as a better node generality metric compared with degree centrality.

Research limitations: A thorough investigation into the evaluation methodology is needed, including user studies and a set of metrics for evaluating semantic coherence and navigation performance.

Practical implications: The algorithm will benefit the use of digital resources by generating a flexible domain knowledge structure that is easy to navigate. It could be used to manage multiple resource collections even without social annotations since tags can be keywords created by authors or experts, as well as automatically extracted from text.

Originality/value: Few previous studies paid attention to the issue of whether the tagging systems are easy to navigate for users. The contributions of this study are twofold: (1) an algorithm was developed to construct tag trees with consideration given to both semantic coherence and structural balance and (2) the effectiveness of a node generality metric, h-degree, was investigated in a tag co-occurrence network.

Key words: Semantic coherence, Structural balance, Tag tree, Resources navigation, Algorithm