## 5 Analysis for Crawl Guidance and Enrichment
### Social Web Analysis
#### 5.3.4 Context-Aware Search  
We consider the problem of top-\(k\) retrieval in social tagging (or bookmarking) systems, with a focus on efficiency, targeting techniques that have the potential to scale to current applications on the Web in an online context where the network, the tagging data and even the seekers' search ingredients can change at any moment. In this context, a key sub-problem for top-\(k\) retrieval that we need to address is computing scores of top-\(k\) candidates by iterating not only through the most relevant items with respect to the query, but also (or mostly) by looking at the closest users and their tagged items. We associate with the notion of social network a rather general interpretation, as a user graph whose edges are labeled by social scores, which give a measure of the proximity or similarity between two users. These are then exploitable in searches, as they say how much weight one's tagging actions should have in the result build-up. For example, even for applications where an explicit social network does not exist or is not exploitable, one may use the tagging history to build a network based on similarity in tagging and items of interest. While we focus mainly on social bookmarking applications, we believe that these represent a good abstraction for other types of social applications, to which our techniques could apply. As an example, let us consider the collaborative tagging configuration of Figure 8 (left). Users have associated lists of tagged documents, and they are interconnected by social links. Each link is labeled by its (social) score, assumed to be in the \((0,1]\) interval. Let us consider user [PERSON] in the role of the seeker. The user graph is not a complete one, as the figure shows, and only two users have an explicit social score with respect to [PERSON]. For the remaining ones, [PERSON],..., [PERSON], only an implicit social score could be computed from the existing links if a precise measure of their relevance with respect to [PERSON]'s queries is necessary in the top-\(k\) retrieval. Figure 8: Collaborative tagging scenario and its social network (**left**); some paths from a seeker towards a relevant item (**right**). Let us assume that [PERSON] looks for the top two documents that are tagged with \(news\) and \(site\). Looking at [PERSON]'s immediate neighbors and their respective documents, intuitively, \(D3\) should have a higher score than \(D4\), since the former is tagged by a more relevant user (\([PERSON]\), having the maximal social score relative to [PERSON]). If we expand the search to the entire graph, e.g., via a shortest paths-like interpretation, the score of \(D4\) may however benefit from the fact that other users, such as \([PERSON]\) or even \([PERSON]\), also tagged it with \(news\) or \(site\). Furthermore, documents, such as \(D2\) and \(D1\), may also be relevant for the top two result, even though they were tagged only by users who are indirectly linked to [PERSON]. Figure 8 (right) gives a different perspective on our scenario, illustrating how [PERSON] can reach one of the relevant documents, \(D1\), by following three paths in the social network. Intuitively, an aggregation of such paths from a seeker towards data items will be used in the scoring model. Under certain model assumptions that are omitted here, pertaining to social and textual relevance, the top two documents for [PERSON]'s query will be, in descending score order, \(D4\) and \(D2\). We provide the underlying model and algorithms for building this type of answer. In [36], we presented our TOPKS algorithm for top-\(k\) answering in collaborative tagging, which has the potential to scale to current online applications, where network changes and tagging are frequent. The contribution of our approach is three-fold:  
* we allow full scoring personalization, where potentially each user of the system can define their own way to rank items.