parameters, we set up a small experiment by first selecting 5 different seed terms2**; then running the approach with**
different values. Optimal parameter values would enable the approach to reasonably combine/separate saplings with similar/different senses. We manually inspected the induced folksonomies to check how the saplings were merged/separated.

The parameter K **allows the approach to consider only**
top frequency tags, which tend to be more stable and less noisy [5]. Nevertheless, the top tags will not contain enough information if the number is set too low, e.g., K **= 10. At**
the fixed values of the common tag threshold, J **= 4, and**
the structural-local weight combination, αRR = 0.**1 (in this**
2ski, bird, victoria, africa and **insect**

| Parameters   | Description                                                                                     |
|--------------|-------------------------------------------------------------------------------------------------|
| K            | The number of top frequent tags                                                                 |
| J            | The number of common tags for tag similarity                                                    |
| αRR          | The weight combination of local and structural similarity for computing root-to-root similarity |
| αLR          | The weight combination of local and structural similarity for computing leaf-to-root similarity |
| β            | The weight combination of name and tag similarity (not required in our experiment)                                                                                                 |
| τ            | The similarity threshold                                                                        |

case, we simply evaluated on merging root-root nodes; hence

![0_image_0.png](0_image_0.png)

there is no need for αLR), we found that the approach performs reasonably well when the value of K **is around 30–60,**
while the performance starts to degrade for K > **60. Smaller**
values of J **leads to a weak tag similarity measure, which, in**
turn, mistakenly causes the approach to merge saplings with different senses. Large J **will be relatively stringent, and as**
a result, saplings of the same sense will not be merged. We found that, at K = 40, the value of J **between 4 to 6 allows** reasonable results.

For αRR and αLR**, the weight combination between local**
and structural similarity for root-root and leaf-root nodes in Eq. 1, the larger the values the more the similarity measure emphasizes on the structural similarity. From our experiments, we found that the structure information is very informative. When αRR is set to a very large value or the maximum, 1.**0, the approach clusters "structure-rich" saplings,**
i.e., saplings containing many children, reasonably well. For leaf-to-root merging or in situations where structural information is uncommon, local similarity becomes more important. We discovered that at αRR = 0.1 and αLR = 0.**8, the**
approach produces reasonable folksonomies. Due to space limitations, we do not include the complete set of results.

Here, we report the parameter values that resulted in good performance: we set K = 40; J **= 4. In addition, since all**
similarity measures are normalized to range within 0.**0 and**
1.0, we set τ = 0.5.

We compare sap **against the folksonomy learning method,**
sig**, described in [12]. Briefly,** sig **first breaks a given sapling**
into (collection-set) individual parent-child relations. With the assumption that the nodes with the same (stemmed)
name refer to the same concept, the approach employs hypothesis testing to identify the informative relations, i.e., checking if the relation is not generated at random. Informative relations are then linked into a deeper folksonomy.

We used a significance test threshold of 0.01.

5.1 Methodology We quantitatively evaluate the induced folksonomies by
(1) automatically comparing them to a reference hierarchy;
(2) structural evaluation; (3) manual evaluation.

Evaluation against the reference hierarchy: **We use**
the reference hierarchy from the Open Directory Project
(ODP).3 **We selected ODP because, in contrast to WordNet, ODP is generated, reviewed and revised by many registered users. These users seem to use more colloquial terms**
than appear in WordNet. In addition, like Flickr users, they specify less formal relations, mainly broader/narrower relations. WordNet, on the other hand, specifies a number of formal relations among concepts, including hypernymy and meronymy.

We use methodology described in [12] to automatically evaluate the quality of the learned folksonomies. Although ODP and saplings are generated from different sources, there is substantial vocabulary overlap that makes them comparable. Since the ODP hierarchy is relatively large and composed of many topics, we had to carve out the "relevant" portion for comparison. First, we specified a seed, S**, which**
is the root of the learned folksonomy F **and the reference**
hierarchy to which it is compared.

Next, the folksonomy is expanded two levels along the relations in F**. The nodes in the second level are added as**
3http://rdf.dmoz.org/, as of September 2008