1 Introduction
2 Related Work
2.1 Usability of Hierarchies from a User-oriented Perspective
2.2 Methods for Constructing Tag Trees
2.3 Issues with Semantic Drift and Structural Skew
3 Rationale for the Proposed Approach
3.1 Desired Features of a Hierarchy for the Purpose of Navigation
Figure 1. An example of a tag tree. Users track along the paths that most likely lead them to find their desired information by the meaning of nodes. Thus semantic coherence along a path is important for a navigation hierarchy. |
3.2 Measurement of Nodes and Edges in a Tag Network
4 Algorithm for Constructing Tag Trees
4.1 Selecting Representative Tags from T
4.2 Constructing Tag Trees
5 Evaluation
5.1 Dataset and Benchmark
Table 1 The semantic evaluation results of different similarity threshold setting values in HTT. |
Threshold | Degree centrality | h-degree | ||||
---|---|---|---|---|---|---|
TP | TR | F1 | TP | TR | F1 | |
0 | 0.0448 | 0.0368 | 0.0404 | 0.0509 | 0.0405 | 0.0451 |
1 | 0.0448 | 0.0368 | 0.0404 | 0.0509 | 0.0405 | 0.0451 |
2 | 0.0448 | 0.0368 | 0.0404 | 0.0509 | 0.0405 | 0.0451 |
3 | 0.0448 | 0.0368 | 0.0404 | 0.0510 | 0.0405 | 0.0451 |
4 | 0.0448 | 0.0368 | 0.0404 | 0.0510 | 0.0405 | 0.0451 |
5 | 0.0448 | 0.0368 | 0.0404 | 0.0509 | 0.0404 | 0.0451 |
6 | 0.0448 | 0.0368 | 0.0404 | 0.0509 | 0.0404 | 0.0451 |
7 | 0.0447 | 0.0367 | 0.0403 | 0.0509 | 0.0404 | 0.0450 |
8 | 0.0446 | 0.0365 | 0.0402 | 0.0508 | 0.0402 | 0.0449 |
9 | 0.0445 | 0.0365 | 0.0401 | 0.0507 | 0.0402 | 0.0448 |
10 | 0.0443 | 0.0364 | 0.0400 | 0.0506 | 0.0401 | 0.0447 |
20 | 0.0417 | 0.0339 | 0.0374 | 0.0479 | 0.0376 | 0.0421 |
30 | 0.0382 | 0.0309 | 0.0342 | 0.0446 | 0.0346 | 0.0389 |
40 | 0.0344 | 0.0273 | 0.0305 | 0.0406 | 0.0310 | 0.0351 |
50 | 0.0316 | 0.0249 | 0.0279 | 0.0378 | 0.0286 | 0.0325 |
60 | 0.0298 | 0.0232 | 0.0261 | 0.0360 | 0.0267 | 0.0307 |
70 | 0.0279 | 0.0218 | 0.0245 | 0.0343 | 0.0252 | 0.0290 |
80 | 0.0264 | 0.0205 | 0.0231 | 0.0328 | 0.0238 | 0.0276 |
90 | 0.0252 | 0.0198 | 0.0222 | 0.0319 | 0.0230 | 0.0268 |
100 | 0.0241 | 0.0187 | 0.0211 | 0.0308 | 0.0221 | 0.0257 |
5.2 Evaluation of Established Metrics
5.2.1 HTT vs. NTT Algorithms
5.2.2 Degree and h-degree Generality Metrics
Figure 2. Reference-based evaluation results using NTT algorithm with degree and h-degree. The left part is the results using degree centrality for generality, and the right part is those using h-degree. The x-axis denotes punishment parameter λ and the vertical axis represents the value of TP, TR, and F1, respectively. The bar in position 0 on the x-axis of each diagram represents the value of HTT algorithm, and the other following groups on the x-axis demonstrate the values of NTT algorithm with different punishment parameter λ (λ = 0.1 to 1.0) values. In each group, the bars from the left to the right show the TP/TR /F1 value of structural controlling parameter k (k = 10, 20, 30, 40, and 50). When the conditions of NTT were set to h-degree with parameters λ = 0.4 and k = 30, the TP, TR, and F1 of the proposed algorithm reached the relative best. |
5.3 Application Illustration
Figure 3. Fragment of NTT tree. |
Figure 4. Fragment of HTT tree. |