Minimum Steiner Tree Approximation for Extracting Unknown Information via Avoiding High-Centrality Nodes
Rintaro Nishiyama, Andrew Shin, Naoki Matsumoto, Kunitake Kaneko · 2024
Minimum Steiner tree is frequently used as a means for information retrieval, particularly for search with keyword. While it tends to include high-centrality nodes, the information obtained from such tree may already be accessible to the user, which is not very useful. In this paper, we propose a Steiner tree that avoids high-centrality nodes, in order to increase the likelihood of information being unknown to the user, and thus more useful, while maintaining a high degree of relevance to the keywords. We examine various schemes to select high-centrality nodes to avoid, and compare them in terms of the degree of relevance with the keyword, probability of being unknown to the user, and the pre-computation time. We employ degree centrality and betweenness centrality as our metric for centrality. We find that, our best-performing scheme, despite its simplicity, is able to reduce more than 5% in terms of the number of betweenness centrality nodes compared to the minimum Steiner tree, along with its pre-computation time being about 20% times faster, regardless of our choice of centrality metric.