Have a personal or library account? Click to login

Enhancing Navigability: An Algorithm for Constructing Tag Trees

Journal of Data and Information Science
Volume 2 (2017): Issue 2 (May 2017)
By:
Open Access
|Mar 2017

Figures & Tables

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.
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.

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 X = 0.4 and k = 30, the TP, TR, and F1 of the proposed algorithm reached the relative best.
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 X = 0.4 and k = 30, the TP, TR, and F1 of the proposed algorithm reached the relative best.

Figure 3

Fragment of NTT tree.
Fragment of NTT tree.

Figure 4

Fragment of HTT tree.
Fragment of HTT tree.

The semantic evaluation results of different similarity threshold setting values in HTT_

ThresholdDegree centralityh-degree
TPTRF1TPTRF1
00.04480.03680.04040.05090.04050.0451
10.04480.03680.04040.05090.04050.0451
20.04480.03680.04040.05090.04050.0451
30.04480.03680.04040.05100.04050.0451
40.04480.03680.04040.05100.04050.0451
50.04480.03680.04040.05090.04040.0451
60.04480.03680.04040.05090.04040.0451
70.04470.03670.04030.05090.04040.0450
80.04460.03650.04020.05080.04020.0449
90.04450.03650.04010.05070.04020.0448
100.04430.03640.04000.05060.04010.0447
200.04170.03390.03740.04790.03760.0421
300.03820.03090.03420.04460.03460.0389
400.03440.02730.03050.04060.03100.0351
500.03160.02490.02790.03780.02860.0325
600.02980.02320.02610.03600.02670.0307
700.02790.02180.02450.03430.02520.0290
800.02640.02050.02310.03280.02380.0276
900.02520.01980.02220.03190.02300.0268
1000.02410.01870.02110.03080.02210.0257

Get representative nodes from tag set L_

FunctionGetRepresent ( L, k, λ )
1.Initialize A = Φ, m = |L|, T = L, and L is tag set {tl,…,tm};
2.Get generality for each tag t in T by calling function Ge(t), and store them in an array D;
3.k = k>m?m:k;
4.for i = 1:k
5.   select the tag tmax from T which has the maximal value in D;
6.   A = A∪tmax, T = T / tmax;   //Add tmax to A and remove tmax from T
7.   for j = 1: |T|
8.      D[tj] = D[tj] – λ*sim(tmax,tj)*D[tmax];   //As a punishment, lowering down the nodes’
      generality according to their similarity to the selected node tmax.
9.   end for
10.end for
11.return to A;

Construct a tag tree_

FunctionConstructTree (p, L, k, λ )
1.A = GetRepresent( L, k, λ );
2.n = |A|; m = |L|     // n,m is the number of elements in A,L separately.
3.if n = 0 return to p;
4.L1={}, L2={}, …, Ln={};
5.for i=1:m
6.   if (L[i] in A) continue;
7.   j = MaxSimIndex(A, L[i]);    // get the index of the most similar tag in A for L[i].
8.   if (Ge(L[i])>Ge(A[j]) ) continue;    // Ge() is the function of generality.
9.Lj = Lj∪L[i];    //group element L[i] to subset Lj, which associates with A[j].
10.end for
11.for i=1:n
12.   build a node c for tag A[i];
13.   s = ConstructTree(&c, Li, k, λ);
14.   add s as a child of p;
15.end for
16.return to p;
DOI: https://doi.org/10.1515/jdis-2017-0008 | Journal eISSN: 2543-683X | Journal ISSN: 2096-157X
Journal RSS Feed
Language: English
Page range: 56 - 75
Submitted on: Nov 29, 2016
Accepted on: Feb 22, 2017
Published on: Mar 21, 2017
Published by: Chinese Academy of Sciences, National Science Library
In partnership with: Paradigm Publishing Services
Publication frequency: 4 times per year
Keywords:
Semantic coherence,
Structural balance,
Tag tree,
Resources navigation,
Algorithm
Related subjects:
Computer sciences,
Information technology,
Project management,
Databases and data mining

© 2017 Chong Chen, Pengcheng Luo, published by Chinese Academy of Sciences, National Science Library
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Previous articleVolume 2 (2017): Issue 2 (May 2017)Next article