A Comparison of Graph Centrality Algorithms For Semantic Distance

Abstract

Semantic networks are kind of datasets used for natural language processing (NLP). Distance measurement for semantic networks, which are generally based on a graph structure, is a vital requirement for semantic analysis on concepts. Centrality measures can be used for calculating the semantic distance between concepts in a semantic network. In this paper, we evaluated graph centrality algorithms including PageRank, Hyperlink-induced Topic Search (HITS), and Betweenness Centrality on a semantic network, which was created from a Turkish dictionary dataset. Centrality measures special to these algorithms are used to calculate the semantic distance between synonym pairs in the semantic network. Also, we have used a simple centrality method beside the other three popular centrality algorithms to find out the most accurate and cost-effective method on our semantic network. Working on a bipartite model of the network which increases the complexity of implementation for centrality algorithms and performing calculations on a semantic network, that can be expanded with new nodes and edges, are two major challenges to overcome. Considering all these conditions, results from each algorithm are compared to pick out an optimal method for the semantic network.

Anlamsal ağlar, doğal dil işleme (DDİ) için kullanılan graf tabanlı veri kümeleridir. Anlamsal ağlarda mesafe ölçümü ise, kavramların ağ içinde ilişkiler ile birbirine bağlılığının anlamsal analizi için çok önemli bir yere sahiptir. Bağlantılılık ölçümleriyle elde edilen değerler, anlamsal ağlardaki kavramlar arasındaki mesafe hesaplamaları için kullanılabilinir. Bu çalışmada, PageRank, Hyperlink-induced Topic Search (HITS) ve Arasındalık Merkeziliği graf bağlantılılık algoritmaları, Türkçe sözlükteki kavramlardan oluşturulan anlamsal ağ üzerinde uygulanmış ve elde edilen değerler ile anlamsal ağdaki eş anlamlı sözcükler arasındaki mesafe hesaplanmıştır. Bu üç önemli graf bağlantılılık algoritmaları, bu çalışmada kullanılan anlamsal ağ için tasarlanmış olan temel bir bağlantılılık yöntemiyle karşılaştırılmıştır. İki parçalı graf tasarımı ile oluşturulmuş olan Türkçe Sözlük anlamsal ağı üzerinde geleneksel graf bağlantılılık algoritmalarının uygulanması daha karmaşık hale gelmektedir. Uygulama esnasında gereken işleme zamanını arttırması, ayrıca ağa eklenecek olan yeni kavramlar ve bağlantılar sonrası ağın tekrar anlamsal mesafe için hesaplamalara ihtiyaç duyması, bağlantılılık algoritmalarının karşılaştığı iki önemli sorundur. Bu zorluklar ve anlamsal ağın iki parçalı graf yapısı göz önüne alındığında, her bir algoritma ile elde edilen sonuçlar karşılaştırılmış ve tasarlanan anlamsal ağ için en verimli yöntem bulunmaya çalışılmıştır.