Comparing the hierarchy of keywords in on-line news portals
Table 3: Ratios of giant and dwarf branches among all branches, size-weighted.
['dataset', '[ITALIC] Rg', '[ITALIC] Rd']
Another important question is whether branch sizes are balanced or not in the hierarchies. A well-balanced hierarchy is expected to have at least 2 but not more than O(1) comparably sized branches at every nonleaf tag. We define a balancedness measure with a pair of real numbers from [0,1)×[0,1) corresponding to the ratio of “giant branches” and the ratio of “dwarf branches” in order to quantify how a DAG fits to the above criterion. First, we calculate the cumulated size of the branches having a child branch which contains more than 50% of the parent branch’s tags. Second, we calculate the cumulated size of the child branches which are smaller than 10% of their parent branches. The higher threshold is motivated by the fact that a child branch above 50% is larger than all the other child branches combined. The motivation for the lower threshold is that below 10%, for equal-sized child branches, the number of child branches exceeds O(1). Other numerical threshold values might also be applied, however, for demonstrating significant phenomena the precise value of the thresholds should not be important. We normalise the sums by their maximal possible value, thus, our balancedness measure is given by (Rg,Rd)=(∑gSg∑bSb,∑dSd∑bSb) (6) where b goes over all branches containing at least 2 tags , Sb is the size of branch b, g goes over branches containing a sub-branch having more than 50% of g’s tags, and Sg is the corresponding branch size, and d goes over sub-branches which are smaller than 10% of their parent branches with Sd being the corresponding branch size. A perfectly balanced hierarchy would have a (0,0) score and the two extremely unbalanced cases would have (1,0) for a chain and (0, 1) for a star graph.