Applying community detection methods to cluster tags in multimedia search results

Abstract

Multimedia searches often return items that can becategorized into several “topics”, allowing users to disambiguateand explore answers more efficiently. In this paper we investigatemethods for clustering tags associated with multimedia searchresults, where each resulting cluster represents a topic computedonline for that particular search. We specifically investigate theapplicability ofcommunity detection algorithmsto the tag graphinduced from the search results. This type of approach allows usto exploit tag similarity and create ad-hoc topics for each search,without specify the number and sizes of clusters a priori.In this work we experiment with well-known algorithms in thisfield and propose two new methods based onadaptive island cuts.Using theSocial20dataset (a collection gathered from Flickr) weevaluate several community detection methods, with quantitativeanalysis of each algorithm in terms of the relative number ofcommunities (which we interpret as topics) that they produce andtheir sizes, as well as qualitative analysis of topics per humanjudgement. Our evaluation shows that it is possible to extractad-hoc topics for search results using community detection,but that different community detection methods produce verydifferent results. In particular, our proposed methods producemore compact and less noisy clusters as well as less relative recallwhen compared to methods that produce much larger clusters.