Indiana University Bloomington

School of Informatics and Computing

Technical Report TR676:
Socially Induced Semantic Networks and Applications

Benjamin Markines
(Jun 2009), 177 pages
[This is a PhD thesis]
Social bookmarking systems allow Web users to actively annotate online resources. These annotations incorporate meta-information with Web pages in addition to the actual document contents. From a collection of socially annotated resources, we present various methods for quantifying the relationship between objects, i.e., tags or resources. These relationships can then be represented in a semantic similarity network where the nodes represent objects and the undirected weighted edges represent their relations. These relations are quantified through similarity measures. There are two challenges associated with assembling and maintaining such a similarity network. The first challenge is updating the relations efficiently, i.e., the time and space complexity associated with graph algorithms. The complexity of these algorithms is typically quadratic. We present an incremental process answering both space and time limitations. The second challenge is the quality of the similarity measure. We evaluate various measures through the approximation of reference similarities. We then present a number of applications leveraging socially induced semantic similarity networks. A tag recommendation system, a page recommendation engine, and a Web navigation tool are evaluated through user studies. Finally, we design spam detection algorithms to enhance the functionality of social bookmarking systems.

Available as: