We are involved into the development of recommendation systems, broadly defined as the algorithms and methods for making recommendations of items or services to users, depending on the application context, based on a variety source of information including past behavior of similar users.
Our efforts in this area have so far considered the design and analysis of collaborative filtering techniques for fully decentralized networks of small devices with limited communication and computational capabilities, and the design of query- and web-page-recommendation techniques for web users.
In the distributed scenarios that we consider, the tasks of collecting, forwarding and processing user profile information are distributed among the items themselves or the users. In particular, it is possible to design both item-based and user-based collaborative filtering strategies. As an example of the former, we consider a setting in which items are tagged with smart tags (such as passive RFIDs), that collect history information about users that accessed them in the past. This information can be read by smart mobile devices and can be used to match a user's profile against the typical profile of users that were interested in a given item in the past.
Another scenario of great interest is the one in which user profile information is transparently collected by users' smart mobile terminals and used to implement recommendation services based on user past activity and similarity with other users. Whereas collecting profile information can be implemented as a more or less sophisticated application on a typical smart phone, exchanging this information in a privacy-preserving way and using it to implement a fully decentralized recommendation service poses interesting challenges. As a first case study, we consider a fully decentralized approach for recommending new contacts (i.e., social matching) in the social network of mobile phone users.
In the application area of web search, we are using past user browsing information as encoded in the so called query-flow graph to recommend search queries to new users to help them for their search goals. We also define the early-adopter graph, which we use to build a recommendation system for news and blog pages.
L. Becchetti, L. Bergamini, U. M. Colesanti, L. Filipponi, G. Persiano, and A. Vitaletti
A Lightweight Privacy Preserving SMS-Based Recommendation System for Mobile Users
Knowledge and Information Systems, Volume 40, Number 1, 2014
In this paper, we propose a fully decentralized approach for recommending new contacts in the social network of mobile phone users. With respect to existing solutions, our approach is characterized by some distinguishing features. In particular, the application we propose does not assume any centralized coordination: It transparently collects and processes user information that is accessible in any mobile phone, such as the log of calls, the list of contacts or the inbox/outbox of short messages and exchanges it with other users. This information is used to recommend new friendships to other users. Furthermore, the information needed to perform recommendation is collected and exchanged between users in a privacy preserving way. Finally, information necessary to implement the application is exchanged transparently and opportunistically, by using the residual space in standard short messages occasionally exchanged between users. As a consequence, we do not ask users to change their habits in using SMS.
L. Becchetti, U. Colesanti, A. Marchetti-Spaccamela, and A. Vitaletti
Fully Decentralized Recommendations in Pervasive Systems: Models and Experimental Analysis
International Journal of Engineering Intelligent Systems for Electrical Engineering and Communications, Volume 20, Number 3, 2012
In this paper we investigate the use of fully decentralized recommendation techniques for pervasive systems of small devices with limited or no communication and computational. We consider a reference scenario where items are distributed in a shop (e.g. a bookstore or a supermarket) and are tagged with computational devices of limited (or no) communication and computational capabilities (such as RFIDs). We do not assume any cooperation among users and, more importantly, we assume that every node has only partial view of the past history of the system, determined by users' visit patterns; information exchange among nodes is mediated by the collective and unpredictable navigation of users. These limitations are coherent with standard systems and current technology. We propose recommendation algorithms relying on the computation and maintenance of simple statistics about users' visit patterns, without requiring any explicit interaction among users and can be easily and efficiently implemented. We report on extensive simulations that show the effectiveness of our profiling heuristics. Finally, we test our recommendation algorithms on real, publicly available datasets.
I. Mele, F. Bonchi, and A. Gionis
The Early-Adopter Graph and Its Application to Web-Page Recommendation [pdf]
Proc. 21st ACM International Conference on Information and Knowledge Management (CIKM 2012), 2012
In this paper we present a novel graph-based data abstraction for modeling the browsing behavior of web users. The objective is to identify users who discover interesting pages before others. We call these users early adopters. By tracking the browsing activity of early adopters we can identify new interesting pages early, and recommend these pages to similar users. We focus on news and blog pages, which are more dynamic in nature and more appropriate for recommendation.
Our proposed model is called early-adopter graph. In this graph, nodes represent users and a directed arc between users u and v expresses the fact that u and v visit similar pages and, in particular, that user u tends to visit those pages before user v. The weight of the edge is the degree to which the temporal rule "v visits a page before v" holds.
Based on the early-adopter graph, we build a recommendation system for news and blog pages, which outperforms other out-of-the-shelf recommendation systems based on collaborative filtering.
L. Becchetti, U. Colesanti, A. Marchetti-Spaccamela, and A. Vitaletti
Recommending Items in Pervasive Scenarios: Models and Experimental Analysis [pdf]
Knowledge and Information Systems, Volume 28, Number 3, 2011
In this paper, we propose and investigate the effectiveness of fully decentralized, collaborative filtering techniques. These are particularly interesting for use in pervasive systems of small devices with limited communication and computational capabilities. In particular, we assume that items are tagged with smart tags (such as passive RFIDs), storing aggregate information about the visiting patterns of users that interacted with them in the past. Users access and modify information stored in smart tags transparently, by smart reader devices that are already available on commercial mobile phones. Smart readers use private information about previous behavior of the user and aggregate information retrieved from smart tags to recommend new items that are more likely to meet user expectations. Note that we do not assume any transmission capabilities between smart tags: Information exchange among them is mediated by users' collective and unpredictable navigation patterns. Our algorithms do not require any explicit interaction among users and can be easily and efficiently implemented. We analyze their theoretical behavior and assess their performance in practice, by simulation on both synthetic and real, publicly available data sets. We also compare the performance of our fully decentralized solutions with that of state-of-the-art centralized strategies.
A. Anagnostopoulos, L. Becchetti, C. Castillo, and A. Gionis
An Optimization Framework for Query Recommendation [pdf]
Proc. 3rd ACM International Conference on Web Search and Data Mining (WSDM 2010), 2010
Query recommendation is an integral part of modern search engines. The goal of query recommendation is to facilitate users while searching for information. Query recommendation also allows users to explore concepts related to their information needs.
In this paper, we present a formal treatment of the problem of query recommendation. In our framework we model the querying behavior of users by a probabilistic reformulation graph, or query-flow graph [Boldi et al. CIKM 2008]. A sequence of queries submitted by a user can be seen as a path on this graph. Assigning score values to queries allows us to define suitable utility functions and to consider the expected utility achieved by a reformulation path on the query-flow graph. Providing recommendations can be seen as adding shortcuts in the query-flow graph that "nudge" the reformulation paths of users, in such a way that users are more likely to follow paths with larger expected utility.
We discuss in detail the most important questions that arise in the proposed framework. In particular, we provide examples of meaningful utility functions to optimize, we discuss how to estimate the effect of recommendations on the reformulation probabilities, we address the complexity of the optimization problems that we consider, we suggest efficient algorithmic solutions, and we validate our models and algorithms with extensive experimentation. Our techniques can be applied to other scenarios where user behavior can be modeled as a Markov process.
E. Baglioni, L. Becchetti, L. Bergamini, U. Colesanti, L. Filipponi, A. Vitaletti, and G. Persiano
A Lightweight Privacy Preserving SMS-Based Recommendation System for Mobile Users [pdf]
Proc. 4th ACM International Conference on Recommender Systems (RecSys 2010), 2010
In this paper we propose a fully decentralized approach for recommending new contacts in the social network of mobile phone users. With respect to existing solutions, our approach is characterized by some distinguishing features. In particular, the application we propose does not assume any centralized coordination: it transparently collects and processes user information that is accessible in any mobile phone, such as the log of calls, the list of contacts or the inbox/outbox of short messages and exchanges it with other users. This information is used to recommend new friendships to other users. Furthermore, the information needed to perform recommendation is collected and exchanged between users in a privacy preserving way. Finally, information necessary to implement the application is exchanged transparently and opportunistically, by using the residual space in standard short messages occasionally exchanged between users. As a consequence, we do not ask users to change their habits in using SMS.