Efficient assembly of social semantic networks

ABSTRACT

Social bookmarks allow Web users to actively annotate individual Web resources. Researchers are exploring the use of these annotations to create implicit links between online resources. We define an implicit link as a relationship between two online resources established by the Web community. An individual may create or reinforce a relationship between two resources by applying a common tag or organizing them in a common folder. This has led to the exploration of techniques for building networks of resources, categories, and people using the social annotations. In order for these techniques to move from the lab to the real world, efficient building and maintenance of these potentially large networks remains a major obstacle. Methods for assembling and indexing these large networks will allow researchers to run more rigorous assessments of their proposed techniques. Toward this goal we explore an approach from the sparse matrix literature and apply it to our system, GiveALink.org. We also investigate distributing the assembly, allowing us to grow the network with the body of resources, annotations, and users. Dividing the network is effective for assembling a global network where the implicit links are dependent on global properties. Additionally, we explore alternative implicit link measures that remove global dependencies and thus allow for the global network to be assembled incrementally, as each participant makes independent contributions. Finally we evaluate three scalable similarity measures, two of which require a revision of the data model underlying our social annotations.

REFERENCES

• 1: G. Begelman, P. Keller, and F. Smadja. Automated tag clustering: Improving search and exploration in the tag space. In Collaborative Web Tagging Workshop at WWW2006, Edinburgh, Scotland, 2006.
• 2: Robert M. Bell , Yehuda Koren, Lessons from the Netflix prize challenge, ACM SIGKDD Explorations Newsletter, v.9 n.2, December 2007 [doi>10.1145/1345448.1345465]
• 3: P. Boldi, M. Santini, and S. Vigna. Do your worst to make the best: Paradoxical effects in pagerank incremental computations. In S. Leonardi, editor, WAW, volume 3243 of Lecture Notes in Computer Science, pages 168--180. Springer, 2004.
• 4: C. Cattuto, A. Baldassarri, V. D. P. Servedio, and V. Loreto. Emergent community structure in social tagging systems. In Proceedings of the European Confeence on Complex Systems ECCS2007, Dresden, Germany, October 2007.
• 5: J. Diederich and T. Iofciu. Finding communities of practice from user profiles based on folksonomies. Proceedings of the 1st International Workshop on Building Technology Enhanced Learning solutions for Communities of Practice, 2006.
• 6: I. S. Duff , A. M. Erisman , J. K. Reid, Direct methods for sparse matrices, Clarendon Press, New York, NY, 1987
• 7: George W. Furnas , Caterina Fake , Luis von Ahn , Joshua Schachter , Scott Golder , Kevin Fox , Marc Davis , Cameron Marlow , Mor Naaman, Why do tagging systems work?, CHI '06 extended abstracts on Human factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1125451.1125462]
• 8: T. Hammond, T. Hannay, B. Lund, and J. Scott. Social Bookmarking Tools (I): A General Review. D-Lib Magazine, 11(4), 2005.
• 9: Y. Hassan-Montero and V. Herrero-Solana. Improving tag-clouds as visual information retrieval interfaces. In International Conference on Multidisciplinary Information Sciences and Technologies, 2006.
• 10: A. Hotho, R. Jäschke, C. Schmitz, and G. Stumme. Information retrieval in folksonomies: Search and ranking. In Y. Sure and J. Domingue, editors, The Semantic Web: Research and Applications, volume 4011, pages 411--426, 2006.
• 11: Dekang Lin, An Information-Theoretic Definition of Similarity, Proceedings of the Fifteenth International Conference on Machine Learning, p.296-304, July 24-27, 1998
• 12: B. Lund, T. Hammond, M. Flack, and T. Hannay. Social Bookmarking Tools (II): A Case Study - Connotea. D-Lib Magazine, 11(4), 2005.
• 13: Ana G. Maguitman , Filippo Menczer , Heather Roinestad , Alessandro Vespignani, Algorithmic detection of semantic similarity, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060765]
• 14: B. Markines, L. Stoilova, and F. Menczer. Social bookmarks for collaborative search and recommendation. In Proc. AAAI 2006, 2006.
• 15: A. Mathes. Folksonomies - cooperative classification and communication through shared metadata.
• 16: Filippo Menczer, Mapping the Semantics of Web Text and Links, IEEE Internet Computing, v.9 n.3, p.27-36, May 2005 [doi>10.1109/MIC.2005.59]
• 17: P. Mika. Ontologies are us: A unified model of social networks and semantics. In Y. Gil, E. Motta, V. R. Benjamins, and M. A. Musen, editors, The Semantic Web - ISWC 2005, Proceedings of the 4th International Semantic Web Conference, ISWC 2005, Galway, Ireland, November 6-10, volume 3729 of Lecture Notes in Computer Science, pages 522--536, Heidelberg, 2005. Springer.
• 18: Paul Resnick , Neophytos Iacovou , Mitesh Suchak , Peter Bergstrom , John Riedl, GroupLens: an open architecture for collaborative filtering of netnews, Proceedings of the 1994 ACM conference on Computer supported cooperative work, p.175-186, October 22-26, 1994, Chapel Hill, North Carolina, United States [doi>10.1145/192844.192905]
• 19: Badrul Sarwar , George Karypis , Joseph Konstan , John Riedl, Analysis of recommendation algorithms for e-commerce, Proceedings of the 2nd ACM conference on Electronic commerce, p.158-167, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352887]
• 20: Upendra Shardanand , Pattie Maes, Social information filtering: algorithms for automating “word of mouth”, Proceedings of the SIGCHI conference on Human factors in computing systems, p.210-217, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223931]
• 21: Greg Linden , Brent Smith , Jeremy York, Amazon.com Recommendations: Item-to-Item Collaborative Filtering, IEEE Internet Computing, v.7 n.1, p.76-80, January 2003 [doi>10.1109/MIC.2003.1167344]
• 22: Harris Wu , Mohammad Zubair , Kurt Maly, Harvesting social knowledge from folksonomies, Proceedings of the seventeenth conference on Hypertext and hypermedia, August 22-25, 2006, Odense, Denmark [doi>10.1145/1149941.1149962]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human information processing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.3 Group and Organization Interfaces
          Subjects: Web-based interaction; Computer-supported cooperative work; Evaluation/methodology

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
aggregation, annotation, collaborative filtering, folksonomy, resource, similarity, tag, web 2.0