Combining Social Networking and Traditional Web Search

We are already waiting quite a while for Google (or Yahoo) to incorporate social networking technology into their web search services. Personalization of search results (as already being offered -- of course in some limited way) as a very first step towards the right direction has become part of traditional web search. The next step should include not only search results from personal resources but also from resources being available within your personal social network. Seems to be straight forward...?!

First thing, include all resources that I have tagged (you can also distinguish between resources that are yours and resources owned by others that you have tagged). In addition to the traditional hyperlink graph of the web (as it is used by the PageRank algorithm), new (weighted and labelled) arcs have to be inserted connecting your homepage (site/blog or whatever) with all the resources (own and foreign) that have been tagged by you.
Ok, now let's consider that everybody's tag-links are inserted into the hyperlink webgraph. Next thing is to insert (weighted and labelled) arcs from your homepage to the homepages of all your friends (according to your personal social network).
You will end up with a graph that includes (a) traditional hyperlinks, (b) personal tagged + weigthed links to resources, and (c) personal tagged + weigthed links to other users. This composite social webgraph should be sufficient for extending the traditional PageRank algorithm to include social networking information.
Of course (and I'm pretty sure of that and I don't go into details now) a lot of adjustments concerning the weights and the use of tags/labels for indexing have to be considered. But, I think it should be possible...

To some extend, a similar approach has been implemented by lijit. lijit is a personalized search engine that makes use of all your available social networking information. At registration, besides your homepage (or blog ... unfortunately you can not manage several different blogs) you pass over your username for several bookmarking/social networking services as well as the URLs of (a) content provided by you and (b) websites (blogs) of your friends. lijit creates a searchable webgraph covering all the resources and networking information that you have provided. Therefore, searching with lijit comes close to a rather personal variant of searching your very own web-universe.

Social Graph Based Search is also the topic of a video podcast from Scobleizer. Although I can't follow his argument that the social networking companies will kick Google's butt in four years (he states that Google's PageRank algorithm cannot be adapted to include social networking information...at least not in a way scalable for Google's purposes and also not with the current business modell of today's SEOs [=Search Engine Optimizers]), I agree to the way how to include social networking information into traditional web search.

Tag search vs. keyword search......substitution or complement

As you know, collaborative tagging systems (CTS) have become rather popular Web 2.0 applications (although I don't like the term 'Web 2.0'...please use 'Social Web' instead). A CTS allows each registered user to maintain her own tags that add semantic annotation to corresponding web links. Today, 'tags' are simple unformatted text data. Tags are transporting meaning, i.e. semantics. Because the user is free to choose any text string (symbol) for a certain semantics (concept) related to a given resource (web page or object). To communicate this semantics, two or more users have to agree upon using the same symbols denoting an object (remember the semiotic triangle [1]).

First difficulty is syntax: there are several posibilities to write a word (of course not all of them are necessarely correct or not all of them belong to the same language). The problem becomes even worse, if one tries to combine several words in a single string (how to separate words?...use CamelCase, underscores, blanks, ...).
Next comes language dependent problems such as polysemy (homonyms or synonyms). For homonyms we have the same symbol but different meanings, and for synonyms vice versa.

Syntax and language dependent problems alone cause tag based search to be more difficult to handle than traditional keyword based approaches (by keyword based approach we refer to full text search or keywords assigned to the resource by the resource author or by some designated expert). For full text search, a query string given by the user (or at least its word stem) has to match some string being part of the searched resource. Keywords given to a resource by some designated expert should meet some level of objectivity and thus, a user might be able to 'guess' the keyword while thinking of a well suited query string. Keywords provided by the author refer to her specific point of view (same with tagging). These 'subjective' keywords are much harder to guess for the arbitrary user, because she does not necessarely share the same context with the (tag) author.
In CTS we distinguish several distinct categories of tags [2]. Among others, there are two fundamental different tag categories: descriptive tags and functional tags. Descriptive tags refer to more objective tags, tags that are used to describe a resource in some general maner. Functional tags on the other hand do include an intended functional use esp. for the tag author and thus, are more subjective. While descriptive tags serve better for general web search, functional tags are useful most for their authors, but not for other users.
To analyse the benefit of tagging for web search, we have to take into account that many users are providing tags for a specific resource. Depending on the distribution of the tags attached to a specific resource, one can observe a power law (see also [2]). Few tags are used very often, while most of all the tags attached to a resource do occur only scarcely. Those few tags rather often can be identified with descriptive tags, while the so called 'long tail' of the other tags often belong to the category of functional tags.
So, how can we make use f that fact?
In [3] the authors propose to use tags for search query refinement. For that reason, they distinguish between two defferent categores of tags (that do not necessarely correspondent with descriptive and functional tags). They distinguish search keywords as being the most popular tags assigned to a resource, which can help to increase the hit rate if being used for query refinement, and exploration keywords, which cannot. Because exploration keywords reflect the personalized search context and information need of an individual user they are supposed to be helpful for the exploration process.

• [1] C.K. Ogden and I. A. Richards: The Meaning of Meaning: A Study of the Influence of Language Upon Thought and of the Science of Symbolism 8th ed. 1923. Reprint New York: Harcourt Brace Jovanovich (1923). (BibTeX)


• [2] S.A.Golder and B.A.Hubermann: Usage Patterns of Collaborative Tagging Systems, Journal of Information Science, 32(2):198-208, 2006 (BibTeX)


• [3] P.Han and Z.Wang and Z.Li and B.Kramer and F.Yang: Substitution or Complement: An Empirical Analysis on the Impact of Collaborative Tagging on Web Search, in Web Intelligence 757-760 (2006). (BibTeX)