Analysis of tag within online social networks

ABSTRACT

In recent years, tagging systems have been paid increasing attentions from both research communities and system designers. Most popular online social networking sites harness tag for managing and locating contents, for organizing and connecting users, and for recommending and sharing resources. We believe that tag acts like bridge between people and resources. Research on tag and tagging behavior will provide us insight about resource space and user activities on the Internet. In this paper, we present a two-level analysis of the tagging system of Del.icio.us. The results from both two levels confirm each other. In network level, we connect tags by users collaborative tagging to form a social network of tags. By investigating its network feature, we find phenomena of small world and scale-free network. We also discover that the links within this network have relatively strong semantic relatedness. In individual level, users' tagging behaviors and patterns are observed by visualizing their bookmarking history on Del.icio.us. Besides, we study the linked users by their tags and find that users within a subscription network share more common interests than random pairs of users. During the analysis, we also discuss the implications of the findings for the design of tag-based system.

REFERENCES

• 1: Karen H. L. Tso-Sutter , Leandro Balby Marinho , Lars Schmidt-Thieme, Tag-aware recommender systems by fusion of collaborative filtering algorithms, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil [doi>10.1145/1363686.1364171]
• 2: Arrington, M. Exclusive: Screen shots and feature overview of Delicious 2.0 preview. 2007; Available from: http://www.techcrunch.com/2007/09/06/exclusive-screen-shots-and-feature-overview-of-delicious-20-preview/.
• 3: Barry Wellman, For a social network analysis of computer networks: a sociological perspective on collaborative work and virtual community, Proceedings of the 1996 ACM SIGCPR/SIGMIS conference on Computer personnel research, p.1-11, April 11-13, 1996, Denver, Colorado, United States [doi>10.1145/238857.238860]
• 4: Kathy J. Lee, What goes around comes around: an analysis of del.icio.us as social space, Proceedings of the 2006 20th anniversary conference on Computer supported cooperative work, November 04-08, 2006, Banff, Alberta, Canada [doi>10.1145/1180875.1180905]
• 5: Peter D. Turney, Mining the Web for Synonyms: PMI-IR versus LSA on TOEFL, Proceedings of the 12th European Conference on Machine Learning, p.491-502, September 05-07, 2001
• 6: Cilibrasi, R. and P. Vitanyi, Similarity of Objects and the Meaning of Words, in Theory and Applications of Models of Computation. 2006. p. 21--45.
• 7: Ralf Hölzer , Bradley Malin , Latanya Sweeney, Email alias detection using social network analysis, Proceedings of the 3rd international workshop on Link discovery, p.52-57, August 21-25, 2005, Chicago, Illinois [doi>10.1145/1134271.1134279]
• 8: Mislove, A., K.P. Gummadi, and P. Druschel, Exploiting social networks for Internet search, in Proceedings of the 5th Workshop on Hot Topics in Network (HotNets-V). 2006: Irvine, CA.
• 9: Haifeng Yu , Michael Kaminsky , Phillip B. Gibbons , Abraham Flaxman, SybilGuard: defending against sybil attacks via social networks, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 10: Tad Hogg , Lada Adamic, Enhancing reputation mechanisms via online social networks, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988811]
• 11: Stephen Dill , Nadav Eiron , David Gibson , Daniel Gruhl , R. Guha , Anant Jhingran , Tapas Kanungo , Sridhar Rajagopalan , Andrew Tomkins , John A. Tomlin , Jason Y. Zien, SemTag and seeker: bootstrapping the semantic web via automated semantic annotation, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775178]
• 12: Paul - Alexandru Chirita , Stefania Costache , Wolfgang Nejdl , Siegfried Handschuh, P-TAG: large scale automatic generation of personalized annotation tags for the web, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242686]
• 13: Philipp Cimiano , Siegfried Handschuh , Steffen Staab, Towards the self-annotating web, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988735]
• 14: Xian Wu , Lei Zhang , Yong Yu, Exploring social annotations for the semantic web, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135839]
• 15: Szomszor, M., et al., Folksonomies, the Semantic Web, and Movie Recommendation, in 4th European Semantic Web Conference. 2007: Innsbruck, Austria.
• 16: Mathes, A., Folksonomies - Cooperative Classification and Communication Through Shared Metadata. Computer Mediated Communication, 2004.
• 17: Hammond, T., et al., Social Bookmarking Tools (I): A General Review, in D-Lib Magazine. 2005.
• 18: Nickles, M., T. Froehner, and G. Weiß, Social Annotation of Semantically Heterogeneous Knowledge, in SemAnnot. 2004.
• 19: Golder, et al., The Structure of Collaborative Tagging Systems. 2005.
• 20: Rui Li , Shenghua Bao , Yong Yu , Ben Fei , Zhong Su, Towards effective browsing of large scale social annotations, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242700]
• 21: Scott A. Golder , Bernardo A. Huberman, Usage patterns of collaborative tagging systems, Journal of Information Science, v.32 n.2, p.198-208, April 2006 [doi>10.1177/0165551506062337]
• 22: A.L, B. and R. Albert, Emergence of Scaling in Random Networks. Science, 1999. 286: p. 509--512.
• 23: Albert, R., H. Jeong, and B. A.L, Diameter of the World-Wide Web. Nature, 1991. 401: p. 130--131.
• 24: Jure Leskovec , Jon Kleinberg , Christos Faloutsos, Graphs over time: densification laws, shrinking diameters and possible explanations, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081893]
• 25: Ergin Elmacioglu , Dongwon Lee, On six degrees of separation in DBLP-DB and more, ACM SIGMOD Record, v.34 n.2, June 2005 [doi>10.1145/1083784.1083791]
• 26: Ravi Kumar , Jasmine Novak , Andrew Tomkins, Structure and evolution of online social networks, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150476]
• 27: Edward R. Tufte, Visual explanations: images and quantities, evidence and narrative, Graphics Press, Cheshire, CT, 1997
• 28: Daniel Weiskopf , Marc Borchers , Thomas Ertl , Martin Falk , Oliver Fechtig , Regine Frank , Frank Grave , Andreas King , Ute Kraus , Thomas Muller , Hans-Peter Nollert , Isabel Rica Mendez , Hanns Ruder , Tobias Schafhitzel , Sonja Schar , Corvin Zahn , Michael Zatloukal, Explanatory and Illustrative Visualization of Special and General Relativity, IEEE Transactions on Visualization and Computer Graphics, v.12 n.4, p.522-534, July 2006 [doi>10.1109/TVCG.2006.69]
• 29: Opte. Available from: http://www.opte.org.
• 30: Websites as Graphs. Available from: http://www.aharef.info/static/htmlgraph/.
• 31: Micah Dubinko , Ravi Kumar , Joseph Magnani , Jasmine Novak , Prabhakar Raghavan , Andrew Tomkins, Visualizing tags over time, ACM Transactions on the Web (TWEB), v.1 n.2, p.7-es, August 2007 [doi>10.1145/1255438.1255439]
• 32: Anthony Dekker, Visualisation of social networks using CAVALIER, Proceedings of the 2001 Asia-Pacific symposium on Information visualisation, p.49-55, December 01, 2001, Sydney, Australia
• 33: Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
• 34: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 35: Lee, S.H., P.-J. Kim, and H. Jeong, Statistical properties of sampled networks. Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), 2006. 73(1): p. 016102--7.
• 36: Alan Mislove , Massimiliano Marcon , Krishna P. Gummadi , Peter Druschel , Bobby Bhattacharjee, Measurement and analysis of online social networks, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298311]
• 37: Jane Morris , Graeme Hirst, Lexical cohesion computed by thesaural relations as an indicator of the structure of text, Computational Linguistics, v.17 n.1, p.21-48, March 1991
• 38: Resnik, P., Using Information Content to Evaluate Semantic Similarity in a Taxonomy, in Proceeding of 14th International Joint Conference on Artificial Intelligence. 1995: Montreal. p. 448--453.
• 39: 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]
• 40: Jarmasz, M. and S. Szpakowicz, Roget's Thesaurus and Semantic Similarity, in Proceedings of Conference on Recent Advances in Natural Language Processing (RANLP 2003). 2003: Borovets, Bulgaria. p. 212--219.
• 41: Wattenberg, M., F. Viégas, and K. Hollenbach, Visualizing Activity on Wikipedia with Chromograms, in Human-Computer Interaction - INTERACT 2007. 2008. p. 272--287.
• 42: Terrell Russell, cloudalicious: folksonomy over time, Proceedings of the 6th ACM/IEEE-CS joint conference on Digital libraries, June 11-15, 2006, Chapel Hill, NC, USA [doi>10.1145/1141753.1141859]
• 43: Resnik, P., Semantic similarity in taxonomy: An information-based measure and its application to problems of ambiguity in natural language. Journal of Artificial Intelligence Research, 1999. 11: p. 95--130.
• 44: A. Farahat, P Pirolli, and P Markova, Incremental Methods for Computing Word Pair Similarity. 2004, Tech. Rep. No. TR-04-6-2004.
• 45: Watts, D. and S. Strogatz, Collective Dynamics of Small-world Networks. Nature, 1998. 393: p. 440--442.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.3 Network Operations
          Subjects: Network management

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Human Factors, Measurement

Keywords:
del.icio.us, scale-free, semantic relatedness, small world, social annotation, tag, visualization