Enhancing Navigability: An Algorithm for Constructing Tag Trees

doi:10.1515/jdis-2017-0008

Abstract

Abstract:

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

Chen Chong,Luo Pengcheng. "Enhancing Navigability: An Algorithm for Constructing Tag Trees." Journal of Data and Information Science, vol.2, no.2, 2017, pp.56-75. DOI: 10.1515/jdis-2017-0008

References

[1]	Almoqhim F., Millard D.E.,& Shadbolt, N.(2013). An approach to building high-quality tag hierarchies from crowdsourced taxonomic tag pairs. In A. Jatowt et al. (Eds.), Social Informatics (pp. 129-138). Berlin: Springer International Publishing.
[2]	Agrawal R., Gollapudi S., Halverson A., & Ieong S. (2009). Diversifying search results.In Proceedings of the Second ACM International Conference on Web Search and Data Mining (pp. 5-14). New York: ACM.
[3]	Begelman G., Keller P., & Smadja F. (2006. Automated tag clustering: Improving search and exploration in the tag space. In Collaborative Web Tagging Workshop at WWW2006, Edinburgh, Scotland. Retrieved on February 4, 2017, from .
[4]	Benz D., Hotho A., Stützer S., & Stumme G. (2010. Semantics made by you and me: Self-emerging ontologies can capture the diversity of shared knowledge. In Proceedings of the 2nd Web Science Conference (WebSci10), Raleigh, NC, USA. Retrieved on February 4, 2017, from .
[5]	Cami?a, S.L. (2010. A comparison of taxonomy generation techniques using bibliometric methods: Applied to research strategy formulation. Retrieved on January 10, 2017, from .
[6]	Candan K.S., Di Caro L., & Sapino M.L. (2008). Creating tag hierarchies for effective navigation in social media .In Proceedings of the 2008 ACM Workshop on Search in Social Media - SSM ’08 (pp. 75-82). New York: ACM.
[7]	Carbonell J., &Goldstein J. (1998). The use of MMR, diversity-based reranking for reordering documents and producing summaries .In Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (pp. 335-336). New York: ACM.
[8]	Chen C., Luo P., Liu X., & Lu Y. (2012). The structure patterns of Web resources’ hierarchical organization(in Chinese). Journal of Library Science in China, 38(202), 72-80
[9]	Dellschaft, K., & Staab, S. (2006). On how to perform a gold standard based evaluation of ontology learning .In The Semantic Web-ISWC 2006 (pp. 228-241). Berlin: Springer-Verlag.
[10]	Gemmell J., Shepitsen A., Mobasher B., & Burke R. (2008). Personalizing navigation in folksonomies using hierarchical tag clustering .In Proceedings of Data Warehousing and Knowledge Discovery (pp. 196-205). Berlin: Springer-Verlag.
[11]	Golub,K., & Lykke,M.(2009). Automated classification of web pages in hierarchical browsing .Journal of Documentation, 65(6), 901-925.
[12]	Halpin H., Robu V., & Shepherd H. (2007). The complex dynamics of collaborative tagging .In Proceedings of the 16th International Conference on World Wide Web (pp. 211-220). New York: ACM.
[13]	Helic D., Trattner C., Strohmaier M., & Andrews K. (2010). On the navigability of social tagging systems .In 2010 IEEE Second International Conference on Social Computing (pp. 161-168). Washington, DC: IEEE Computer Society.
[14]	Helic D., Strohmaier M., Trattner C., Muhr M., & Lerman K. (2011). Pragmatic evaluation of folksonomies .In Proceedings of the 20th International Conference on World Wide Web (pp. 417-426). New York: ACM.
[15]	Helic,D., & Strohmaier, M. (2011). Building directories for social tagging systems .In Proceedings of the 20th ACM International Conference on Information and Knowledge Management (pp. 525-534). New York: ACM.
[16]	Heymann, P., & Garcia-Molina, H. (2006. Collaborative creation of communal hierarchical taxonomies in social tagging systems. Info Lab Technical Report 2006-10. Retrieved on January 10, 2016, from .
[17]	Hirsch, J.E. (2005). An index to quantify an individual’s scientific research output .In Proceedings of the National Academy of Sciences of the United States of America, 102(46), 16569-16572.
[18]	Huang H., Gao Y., Chen L., Li R., Chiew K., & He Q. (2013). Browse with a social web directory .In Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval (pp. 865-868). New York: ACM.
[19]	Li R., Bao S., Yu Y., Fei B., & Su Z. (2007). Towards effective browsing of large scale social annotations .In Proceedings of the 16th International Conference on World Wide Web (pp. 943-952). New York: ACM.
[20]	Luo, P., & Chen, C. (2013). Resource organization systems from folksonomy to hierarchical: Constructing the tag tree by exploiting clustering information(in Chinese). Journal of Library and Information Service, 57(22), 120-125
[21]	Markines B., Cattuto C., Menczer F., Benz D., Hotho A., & Stumme G. (2009). Evaluating similarity measures for emergent semantics of social tagging .In Proceedings of the 18th International Conference on World Wide Web (pp. 641-650). New York: ACM.
[22]	Rafiei D., Bharat K., & Shukla A. (2010). Diversifying web search results .In Proceedings of the 19th International Conference on World Wide Web (pp. 781-790). New York: ACM.
[23]	Rousseau, R., & Zhao, S.X. (2015). A general conceptual framework for characterizing the ego in a network .Journal of Informetrics, 9(1), 145-149.
[24]	Si X., Liu Z., & Sun M. (2010). Explore the structure of social tags by subsumption relations .In Proceedings of the 23rd International Conference on Computational Linguistics (pp. 1011-1019). Stroudsburg, PA: Association for Computational Linguistics.
[25]	Sinclair, J., & Cardew-Hall, M. (2008). The folksonomy tag cloud: When is it useful? Journal of Information Science, 34(1), 15-29.
[26]	Song Y., Qiu B., & Farooq U. (2011). Hierarchical tag visualization and application for tag recommendations .In Proceedings of the 20th ACM International Conference on Information and Knowledge Management (pp. 1331-1340). New York: ACM.
[27]	Strohmaier M., K?rner C., & Kern R. (2012). Understanding why users tag: A survey of tagging motivation literature and results from an empirical study. Web Semantics: Science, Services and Agents on the World Wide Web, 17, 1-11.
[28]	Strohmaier M., Helic D., Benz D., K?rner C., & Kern R. (2012). Evaluation of folksonomy induction algorithms. ACM Transactions on Intelligent Systems and Technology (TIST), 3(4), Article No. 74.
[29]	Suchanek F.M., Vojnovic M., & Gunawardena D. (2008, October) .Social tags: Meaning and suggestions. In Proceedings of the 17th ACM Conference on Information and Knowledge Management (pp. 223-232). New York: ACM.
[30]	Tsai F., Cheng Y., Li S., & Chen C. (2009). Heuristic-based approach for constructing hierarchical knowledge structures .In Proceedings of Industrial and Engineering Applications of Artificial Intelligence and Expert Systems (pp. 439-448). Berlin: Springer-Verlag.
[31]	Tsui E., Wang W.M., Cheung C.F., & Lau A.S.M. (2010). A concept-relationship acquisition and inference approach for hierarchical taxonomy construction from tags .Information Processing & Management, 46(1), 44-57.
[32]	Verma C., Mahadevan V., Rasiwasia N., Aggarwal G., Kant R., Jaimes A., & Dey S. (2015). Construction and evaluation of ontological tag trees .Expert Systems with Applications, 42(24), 9587-9602.
[33]	Wiesman F., van den Herik H.J., & Hasman A. (2004). Information retrieval by metabrowsing .Journal of the American Society for Information Science and Technology, 55(7), 565-578.
[34]	Zhao S.X., Rousseau R., & Ye F.Y. (2011). h-Degree as a basic measure in weighted networks .Journal of Informetrics, 5(4), 668-677.
[35]	Zhou M., Bao S., Wu X., & Yu Y. (2007). An unsupervised model for exploring hierarchical semantics from social annotations .In K. Aberer et al.(Eds.), The Semantic Web: The 6th International Semantic Web Conference, the 2nd Asian Semantic Web Conference,