P. S.: Post Scriptum

I think the time have come to write my third, and hopefully last contribution to the topic of tagclouds.

I have been hearing a lot of talk on how users should not use too many tags in linking to url. I also am the maintainer of the mindmap maker, and I often look at some of the maps generated (available to everybody). There is a number of people who tend to use an average of between one and two tags per URL. Their maps are often very ordered. No clustering, no hierarchy. (Forgive me if I don’t put a link to such a map, but since I am going to bash this way of using delicious, I’d rather bash a method than a specific human being. Just go to the list of maps and open a couple, odds are one of them will be of the type I am describing). This way of using delicious uses tags as folders, just with the modification that every now and then you can put an URL in more than one folder at the same time. A bit like big bookstore might carry several copies of the same book, and store them in more than one place (and the Tao Te Ching, ends up in New Age -God knows why- and in Religion).

Of course tags tend not to fit exactly. My Tag Clouds and Cultural Change will be under Tags or Folksonomy or Sociology… Whatever you chose you probably will not put it under Ajax. And yet most of the analysis was done studying the spreading of the term Ajax.

Let’s make a few simple calculations.
I think we can agree that when a search from delicious gives us more than 20 results it’s starting to be unconfortable. We have n tags. Since we use often only one tag to store an URL I assume that search is done by looking for the URL’s in that specific tag. Like you would look inside a folder in your bookmarks. In each tag we can store about 20 links. SO the maximum naumber of url that we can store ends up being 20*n. Add to this that not all tags will be used with the same multiplicity, tags will (probably!) still follow a power law, and even if it is not going to be a precise power law you will have some tags way more used than others, and we can lower this number to 10*n. In any case something that grows linearly with the number of tags.
Let’s suppose instead that we use two tags for each URL. Having n tags all together. The total number of combination will then, hmm, mumble mumble mumble, (n*(n-1))/2.
And n*(n-1) is an even number because either n is even or (n-1) is even.
And that grows as the square of n. Much better.
But why stop there. What if you start using 3 tags.
Then we would have n(n-1)(n-2)/(3*2*1) = n(n-1)(n-2)/6
That grows nearly as the cube of n.
So, is this general? Can we always use more tags per URL to have more space.
Yes, it is part of a general rule, and no the general rule does not just grow (unless the total number of tags that you want to be using is really going to be unbounded).

Let’s rapidly look at the general rule.
If we remember that n! (n factorial) is equal to n*(n-1)*(n-2)*(n-3)*…*3*2*1
And if we use m tags for each URL out of a total of n the total number of possible URL we can store will be:
n! / ((n-m)! * m!)
Every first year student know this, or should. As this is the m’th term of the n’th line of the Tartaglia Triangle (aka Pascal Triangle !java applet)

The number of URL we can store will generally grow until we reach n/2 and then will start to decrese again. If we use n different tags (out of n) to store each URL we are essentially using only one possible combination.

So we know we don’t want to use more than half of the total number of tags to store URL’s. But how are we going then to find out those URL? We are probably going to look for the intersection of those tags. Give me “Folksonomy” intersection “Sociology” in the example above. Only one of the two might give you too many links. On the other hand it’s very hard to remember where did we store an URL when we use only one tag. If we use a whole combination of m tags that will be even harder. But is not that hard to remember a couple of those tags. Or three if two ends up still returning too many results.

So the solution that I am suggesting is:
Use as many tags as fits. Make sure that you use different combination for different URL (if two URL’s have the same combination find the difference between the two and use the difference to burn/carve a new tag). When you search use always couples of keywords. And increase keywords if you got too many results.
And this is good, but we probably can do better. Yet this will give us more storage space than using a single term. So what I am actually suggesting is to use maybe five or ten tags for each URL (all the keywords that would fit!). And then search using 3 of those.

Tag Spam

But how is that different from tag spam. We have seen tag spam. People using a hundred tags for each URL as a way to increase visibility. Yet there are a number of differences.

1. Their posts tend to have all the same tags, i.e. the tags they use don’t follow a power law respect to the times they are used. Each is often used the same amount of times as the others: the number of URL’s thay have stored
2. For the reason above the tags are not useful to distinguish one URL from another.

In this a spammer is really different from someone who uses many tags.

Also spam will have a deleterious effect on using tag metric to explore the long tail. If a spammer tags a common url with many improbable keywords, and then tags another url with the same set of keywords, that might be enough to make the two url very close. The proof is left as a simple excercise to the reader. This is bad (although I am quite convinced that there is a lot of work that can be done to mitigate this effect by carefully working on which metric to use).

The fact that their set of tags don’t follow a power law might seem that we could use this in our fight against SPAM. It is not so. It would be quite easy for the spammer to change the algorithm, to follow exactly a power law. What I am about to suggest is way more fundamental and revolutionary.

Let’s use tags clouds to store links instead of tag sets!
At the moment each person uses a tag set to tag a link. Each tag has the same importance of each other. Order is irrelevant. But we know that left in the cultural wild tags tend to develop a very specific tag cloud where each tag has a very specific weight. Like the ingredients in grandma’ pudding each URL will have that much of this tag and that much of that tag. If this is true, and if tags are not just discrete folders, where something either is inside or is not, but are dimensions in a continuous space (…at its limit you might say that the absence of a tag respect to an url is a privative and as such is impossible. Just many many tags have such a low weight to be irrelevant, but let’s not get philosophical), then it really is limiting to let users just have the possibility to use a tag set to store an URL instead of a tag cloud. We are starting to understand a natural way to store a huge number of things, and it will not pass much time that tools will appear to let people bookmark URL with a tag cloud.

But how can URL be bopokmarked with a tagcloud, instead than a tagset? Isn’t it impractical? Think, it is already a pain in the ass to find all the tags that are relevant, now you also want us to store next to each tag its weight:
“I think this is worth 0.5, this 0.4, this 0.9 and this at 0.1. Oops it doesn’t sum up to 1, I need to start again. Let’s put them all as 0.25. Oops, it does not fit a power law. Delicious new interface thinks it’s spam and have deleted the whole URL. Grr, damn Pietro!”

We can do better than that.
We know that:

• tag clouds approximate a power law;
• the sum of the weight should be renormalised to one;
• the steeper the power law the shorter the list of tags above a certain weight is.
• a power law can be approximated by a list of tags and a steepnes.
• delicious does not consider the order of the tags.

And now, if we put all together… mix, add some salt. We could have an interface that:

• takes the list of tags, ordered (!);
• by looking at the number of tags, decides the best steepnes to use;
• assigns to each tag a weight such that:
  • the tags ordered by weight end up being ordered as the user sent them,
  • the sum of the weights is one,
  • the tags weight follow a power law (as much as it makes sense in such a short list).

And all that is needed from the user point of view is to make sure that the tags are ordered from the most fir for that URL to the least fit to that URL.

What would be the consequences of using tag clouds instead of tag sets?

• First of all we know that the general tag cloud of a URL is obtained by summing up the tag sets of all the users. This is still true, we can sum up the tag cloud of each user and get a general tag cloud. Only, this time, user will all have the same weight. If there are u user who have tagged a URL, each user will be responsible for 1/u of the position of the result in the n-simplex. (While now people who use more than one tag are generally more relevant on the final position).
• Even if someone uses 10000 tags the extra noise he is adding will rapidly approximate zero.
• It will be impossible for users to add irrelevant tags to link together different article (unless this will happen as the joint effort of many users) using the tag metric described before.
  Search in tag space could have the possibility to use the extra information of the order of the tags, thus adding storage space.
  Roughly we go from
  n! / ((n-m)! * m!)
  to
  n! / (n-m)!
• The inbox can be modified, so that instead of looking for one keyword we look for a position in the n-simplex (i.e. space of the normalised tag clouds), and only look for pages that appear withing a distance of d from that position. (This is important and not to be overlooked). So I could look for (”delicious, tool”; d=0.5) to find all the delicious tools ecc.
• General search will also be made in a way similar to the inbox, just without the distance d. You give a position in the simplex (i.e. an ordered list of tags) and you receive a list of URL in order of distance from that point. Notice how the idea of giving an ordered list of tags is not new. In google, for example, the list of words you search on, is ordered. Try to switch the orderings of some of the terms in the list and see how the results change.

There is also another reason why the order of tags should be considered to the point of considering it a powerlaw atg cloud instead than just a set. At the moment there are many people who are noticing (correctly!) a serious difference between user versus author tagging. Well, I claim that this way of using tag clouds instead of tag sets will heal the gap by forcing authors to use a normalised (to sum of weight of 1) tag cloudm with weights following a power law. And in such space it is much harder to spam.

But why is it harder to spam? Because each document have a place in the simplex. The visibility will generally be higher when you can reach that place, because that is where people will look for you. Right now spammers tend to add keywords to be present in multiple places. But if the weight of tags gets rinormalised, then it will be like forcing URL to be present in one and only one place of the general simplex. Trying to look for a better position might increase their visibility but not their visibility toward the people who are actually looking for them.

All this of course require some changes. In particular:

• delicious should be modified to consider as relevant the order of the tags, use it to calculate the relative tag cloud. Add that to the general tag cloud of a certain url, and use that tag cloud in its calculations.
• Technorati might do the same.
• Users need to be alerted that the order of tags is important.

In the meantime we could play with cloudalicious by renormilizing the weight of the tags that each user inserts by dividing it on the number of tags that that user have added.

Ok, hopefully in the next days I will clean up a bit this entry and make it nicer. And then I’ll be off, or so I hope. I am going on vacation. This summer I might go to the European Go conference in Prague, and maybe to the first conference on wikipedia. If you plan to go to either of them let me know, and we might have a something to drink together.

Related posts:

1. COP15 Needs an e-Government System This morning I received a mail from Copenhagen. It was very moving, and describing a situation of chaos, strong commitment, and braveness. It told the story of people fighting with non violence, and shouting that they want change. And I am afraid all this is useless. I feel once again what I felt looking at Iran [...]...