A Connection-Centric Survey of Recommender Systems Research
---
paper_title: Comparing feature-based and clique-based user models for movie selection

paper_content:

The huge amount of information available in the currently evolving world wide information infrastructure at any one time can easily overwhelm end-users. One way to address the information explosion is to use an “information filtering agent” which can select information according to the interest and/or need of an end-user. However, at present few such information filtering agents exist. In this study, we evaluate the use of feature-based approaches to user modcling with the purpose of creating a filtering agent for the video-on-demand application. We evaluate several feature and clique-based models for 10 voluntary subjects who provided ratings for the movies. Our preliminary results suggest that feature-based selection can be a useful tool to recommend movies according to the taste of the user and can be as effective as a movie rating expert. We compare our feature-based approach with a clique-based approach, which has advantages whcrc information from other users is available.
---
paper_title: Content-based book recommending using learning for text categorization

paper_content:

Recommender systems improve access to relevant products and information by making personalized suggestions based on previous examples of a user's likes and dislikes. Most existing recommender systems use collaborative filtering methods that base recommendations on other users' preferences. By contrast,content-based methods use information about an item itself to make suggestions.This approach has the advantage of being able to recommend previously unrated items to users with unique interests and to provide explanations for its recommendations. We describe a content-based book recommending system that utilizes information extraction and a machine-learning algorithm for text categorization. Initial experimental results demonstrate that this approach can produce accurate recommendations.
---
paper_title: User profiling in personalization applications through rule discovery and validation

paper_content:

Gediminas Adomavicius New York University adomavic@cs.nyu.edu In many applications, ranging from recommender systems to one-to-one marketing to Web browsing, it is important to build personalized profiles of individual users from their transactional histories. These profiles describe individual behavior of users and can be specified with sets of rules learned from user transactional histories using various data mining techniques. Since many discovered rules can be spurious, irrelevant, or trivial, one of the main problems is how to perform post-analysis of the discovered rules, i.e., how to validate customer profiles by separating “good” rules from the “bad.” This paper presents a method for validating such rules with an explicit participation of a human expert
---
paper_title: The Web as a graph: Measurements, models and methods

paper_content:

The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph is a fascinating object of study: it has several hundred million nodes today, over a billion links, and appears to grow exponentially with time. There are many reasons -- mathematical, sociological, and commercial -- for studying the evolution of this graph. In this paper we begin by describing two algorithms that operate on the Web graph, addressing problems from Web search and automatic community discovery. We then report a number of measurements and properties of this graph that manifested themselves as we ran these algorithms on the Web. Finally, we observe that traditional random graph models do not explain these observations, and we propose a new family of random graph models. These models point to a rich new sub-field of the study of random graphs, and raise questions about the analysis of graph algorithms on the Web.
---
paper_title: Advances in Social Network Analysis: Research in the Social and Behavioral Sciences

paper_content:

Introduction - Joseph Galaskiewicz and Stanley Wasserman Advances in the Social and Behavioral Sciences from Social Network Analysis PART ONE: SOCIAL PSYCHOLOGY AND DIFFUSION Network Studies of Social Influence - Peter V Marsden and Noah E Friedkin Epidemiology and Social Networks - Martina Morris Modeling Structured Diffusion Statistical Models for Social Support Networks - Michael E Walker, Stanley Wasserman and Barry Wellman Social Cognition in Context - Philippa Pattison Some Applications of Social Network Analysis PART TWO: ANTHROPOLOGY AND COMMUNICATION Anthropological Contributions to the Study of Social Networks - Jeffrey C Johnson A Review Primate Social Networks - Donald Stone Sade and Malcolm M Dow Network Analysis and Computer-Mediated Communication Systems - Ronald E Rice PART THREE: POLITICS AND ORGANIZATIONS Intraorganizational Networks - David Krackhardt and Daniel J Brass The Micro Side Networks of Interorganizational Relations - Mark S Mizruchi and Joseph Galaskiewicz Marketing and Social Networks - Phipps Arabie and Yoram Wind Networks of Elite Structure and Decision Making - David Knoke
---
paper_title: Mining the Web's Link Structure

paper_content:

The Web is a hypertext body of approximately 300 million pages that continues to grow at roughly a million pages per day. Page variation is more prodigious than the data's raw scale: taken as a whole, the set of Web pages lacks a unifying structure and shows far more authoring style and content variation than that seen in traditional text document collections. This level of complexity makes an "off-the-shelf" database management and information retrieval solution impossible. To date, index based search engines for the Web have been the primary tool by which users search for information. Such engines can build giant indices that let you quickly retrieve the set of all Web pages containing a given word or string. Experienced users can make effective use of such engines for tasks that can be solved by searching for tightly constrained key words and phrases. These search engines are, however, unsuited for a wide range of equally important tasks. In particular, a topic of any breadth will typically contain several thousand or million relevant Web pages. How then, from this sea of pages, should a search engine select the correct ones-those of most value to the user? Clever is a search engine that analyzes hyperlinks to uncover two types of pages: authorities, which provide the best source of information on a given topic; and hubs, which provide collections of links to authorities. We outline the thinking that went into Clever's design, report briefly on a study that compared Clever's performance to that of Yahoo and AltaVista, and examine how our system is being extended and updated.
---
paper_title: Studying Recommendation Algorithms by Graph Analysis

paper_content:

We present a novel framework for studying recommendation algorithms in terms of the ‘jumps’ that they make to connect people to artifacts. This approach emphasizes reachability via an algorithm within the implicit graph structure underlying a recommender dataset and allows us to consider questions relating algorithmic parameters to properties of the datasets. For instance, given a particular algorithm ‘jump,’ what is the average path length from a person to an artifact? Or, what choices of minimum ratings and jumps maintain a connected graph? We illustrate the approach with a common jump called the ‘hammock’ using movie recommender datasets.
---
paper_title: Recommender systems in e-commerce

paper_content:

Recommender systems are changing from novelties used by a few E-commerce sites, to serious business tools that are re-shaping the world of E-commerce. Many of the largest commerce Web sites are already using recommender systems to help their customers find products to purchase. A recommender system learns from a customer and recommends products that she will find most valuable from among the available products. In this paper we present an explanation of how recommender systems help E-commerce sites increase sales, and analyze six sites that use recommender systems including several sites that use more than one recommender system. Based on the examples, we create a taxonomy of recommender systems, including the interfaces they present to customers, the technologies used to create the recommendations, and the inputs they need from customers. We conclude with ideas for new applications of recommender systems to E-commerce.
---
paper_title: State of the Art in Selective Dissemination of Information

paper_content:

This paper condenses the results of a detailed survey of 100 SDI systems throughout the world, conducted this year by the American Society for Information Science. The text develops the concept of SDI as a computerized method to provide for the effective flow of technical information among scientific workers. The current status of SDI in university, industrial, and government environments is analyzed and placed in historical perspective, with possible future trends developed particularly those that might affect the form of tomorrow's technical information media.
---
paper_title: Jumping Connections: A Graph-Theoretic Model for Recommender Systems

paper_content:

Recommender systems have become paramount to customize information access and reduce information overload. They serve multiple uses, ranging from suggesting products and artifacts (to consumers), to bringing people together by the connections induced by (similar) reactions to products and services. This thesis presents a graph-theoretic model that casts recommendation as a process of ‘jumping connections’ in a graph. In addition to emphasizing the social network aspect, this viewpoint provides a novel evaluation criterion for recommender systems. Algorithms for recommender systems are distinguished not in terms of predicted ratings of services/artifacts, but in terms of the combinations of people and artifacts that they bring together. We present an algorithmic framework drawn from random graph theory and outline an analysis for one particular form of jump called a ‘hammock.’ Experimental results on two datasets collected over the Internet demonstrate the validity of this approach.
---
paper_title: Comparing feature-based and clique-based user models for movie selection

paper_content:

The huge amount of information available in the currently evolving world wide information infrastructure at any one time can easily overwhelm end-users. One way to address the information explosion is to use an “information filtering agent” which can select information according to the interest and/or need of an end-user. However, at present few such information filtering agents exist. In this study, we evaluate the use of feature-based approaches to user modcling with the purpose of creating a filtering agent for the video-on-demand application. We evaluate several feature and clique-based models for 10 voluntary subjects who provided ratings for the movies. Our preliminary results suggest that feature-based selection can be a useful tool to recommend movies according to the taste of the user and can be as effective as a movie rating expert. We compare our feature-based approach with a clique-based approach, which has advantages whcrc information from other users is available.
---
paper_title: Social Information Filtering for Music Recommendation

paper_content:

Thesis (M. Eng)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1994.
---
paper_title: Personalizing Interactions with Information Systems

paper_content:

Abstract Personalization constitutes the mechanisms and technologies necessary to customize information access to the end-user. It can be defined as the automatic adjustment of information content, structure, and presentation tailored to the individual. In this chapter, we study personalization from the viewpoint of personalizing interaction . The survey covers mechanisms for information-finding on the web, advanced information retrieval systems, dialog-based applications, and mobile access paradigms. Specific emphasis is placed on studying how users interact with an information system and how the system can encourage and foster interaction. This helps bring out the role of the personalization system as a facilitator which reconciles the user's mental model with the underlying information system's organization. Three tiers of personalization systems are presented, paying careful attention to interaction considerations. These tiers show how progressive levels of sophistication in interaction can be achieved. The chapter also surveys systems support technologies and niche application domains.
---
paper_title: Content-based book recommending using learning for text categorization

paper_content:

Recommender systems improve access to relevant products and information by making personalized suggestions based on previous examples of a user's likes and dislikes. Most existing recommender systems use collaborative filtering methods that base recommendations on other users' preferences. By contrast,content-based methods use information about an item itself to make suggestions.This approach has the advantage of being able to recommend previously unrated items to users with unique interests and to provide explanations for its recommendations. We describe a content-based book recommending system that utilizes information extraction and a machine-learning algorithm for text categorization. Initial experimental results demonstrate that this approach can produce accurate recommendations.
---
paper_title: Eigentaste: A Constant Time Collaborative Filtering Algorithm

paper_content:

Eigentaste is a collaborative filtering algorithm that uses i>universal queries to elicit real-valued user ratings on a common set of items and applies principal component analysis (PCA) to the resulting dense subset of the ratings matrix. PCA facilitates dimensionality reduction for offline clustering of users and rapid computation of recommendations. For a database of i>n users, standard nearest-neighbor techniques require i>O(i>n) processing time to compute recommendations, whereas Eigentaste requires i>O(1) (constant) time. We compare Eigentaste to alternative algorithms using data from i>Jester, an online joke recommending system. ::: ::: Jester has collected approximately 2,500,000 ratings from 57,000 users. We use the Normalized Mean Absolute Error (NMAE) measure to compare performance of different algorithms. In the Appendix we use Uniform and Normal distribution models to derive analytic estimates of NMAE when predictions are random. On the Jester dataset, Eigentaste computes recommendations two orders of magnitude faster with no loss of accuracy. Jester is online at: http://eigentaste.berkeley.edu
---
paper_title: Personalized Information Delivery: An Analysis Of Information Filtering Methods

paper_content:

As we know, today everyone is using On-line Social Networks (OSNs) to communicate and share information. Therefore one important need in today On-line Social Networks (OSNs) is to give users the ability to control the messages posted on their own private space to avoid that unwanted content is displayed. OSNs provide little support to this requirement up to now. To provide this, we propose a system allowing OSN users to have a direct control on the messages posted on their walls. This is accomplished through a flexible rule-based system, which allows users to customize the filtering criteria to be applied to their walls, and a Machine Learning based soft classifier which automatically produce membership labels in support of content-based filtering.
---
paper_title: Social information filtering: algorithms for automating “word of mouth”

paper_content:

This paper describes a technique for making personalized recommendations from any type of database to a user based on similarities between the interest profile of that user and those of other users. In particular, we discuss the implementation of a networked system called Ringo, which makes personalized recommendations for music albums and artists. Ringo's database of users and artists grows dynamically as more people use the system and enter more information. Four different algorithms for making recommendations by using social information filtering were tested and compared. We present quantitative and qualitative results obtained from the use of Ringo by more than 2000 people.
---
paper_title: Fab: Content-based, collaborative recommendation

paper_content:

A passive, integrating electromagnetic radiation power dosimeter. A radiofrequency or microwave antenna is combined with a diode detector/rectifier, a squaring circuit, and a electrochemical storage cell to provide an apparatus for determining the average energy of electromagnetic radiation incident on a surface. After a particular period of irradiation, the dosimeter can be interrogated electrically or visually, depending on the type of electrochemical cell employed, to yield the desired information. The apparatus has a substantially linear response to the electromagnetic power density over a wide range of electromagnetic field, and all of the energy required to record the incident energy is supplied by the electromagnetic field.
---
paper_title: Empirical Analysis of Predictive Algorithms for Collaborative Filtering

paper_content:

Collaborative filtering or recommender systems use a database about user preferences to predict additional topics or products a new user might like. In this paper we describe several algorithms designed for this task, including techniques based on correlation coefficients, vector-based similarity calculations, and statistical Bayesian methods. We compare the predictive accuracy of the various methods in a set of representative problem domains. We use two basic classes of evaluation metrics. The first characterizes accuracy over a set of individual predictions in terms of average absolute deviation. The second estimates the utility of a ranked list of suggested items. This metric uses an estimate of the probability that a user will see a recommendation in an ordered list. ::: ::: Experiments were run for datasets associated with 3 application areas, 4 experimental protocols, and the 2 evaluation metr rics for the various algorithms. Results indicate that for a wide range of conditions, Bayesian networks with decision trees at each node and correlation methods outperform Bayesian-clustering and vector-similarity methods. Between correlation and Bayesian networks, the preferred method depends on the nature of the dataset, nature of the application (ranked versus one-by-one presentation), and the availability of votes with which to make predictions. Other considerations include the size of database, speed of predictions, and learning time.
---
paper_title: Information Filtering and Information Retrieval: Two Sides of the Same Coin

paper_content:

Information filtering systems are designed for unstructured or semistructured data, as opposed to database applications, which use very structured data. The systems also deal primarily with textual information, but they may also entail images, voice, video or other data types that are part of multimedia information systems. Information filtering systems also involve a large amount of data and streams of incoming data, whether broadcast from a remote source or sent directly by other sources. Filtering is based on descriptions of individual or group information preferences, or profiles, that typically represent long-term interests. Filtering also implies removal of data from an incoming stream rather than finding data in the stream; users see only the data that is extracted. Models of information retrieval and filtering, and lessons for filtering from retrieval research are presented.
---
paper_title: A vector space model for automatic indexing

paper_content:

In a document retrieval, or other pattern matching environment where stored entities (documents) are compared with each other or with incoming patterns (search requests), it appears that the best indexing (property) space is one where each entity lies as far away from the others as possible; in these circumstances the value of an indexing system may be expressible as a function of the density of the object space; in particular, retrieval performance may correlate inversely with space density. An approach based on space density computations is used to choose an optimum indexing vocabulary for a collection of documents. Typical evaluation results are shown, demonstating the usefulness of the model.
---
paper_title: Relevance Feedback in Information Retrieval

paper_content:

1332840 Primer compositions DOW CORNINGCORP 6 Oct 1971 [30 Dec 1970] 46462/71 Heading C3T [Also in Divisions B2 and C4] A primer composition comprises 1 pbw of tetra ethoxy or propoxy silane or poly ethyl or propyl silicate or any mixture thereof, 0A75-2A5 pbw of bis(acetylacetonyl) diisopropyl titanate, 0A75- 5 pbw of a compound CF 3 CH 2 CH 2 Si[OSi(CH 3 ) 2 - X] 3 wherein each X is H or -CH 2 CH 2 Si- (OOCCH 3 ) 3 , at least one being the latter, and 1-20 pbw of a ketone, hydrocarbon or halohydrocarbon solvent boiling not above 150‹ C. In the examples 1 pbw each of bis(acetylacetonyl)diisopropyl titanate, polyethyl silicate and are dissolved in 10 pbw of acetone or in 9 pbw of light naphtha and 1 of methylisobutylketone. The solutions are used to prime Ti panels, to which a Pt-catalysed room-temperature vulcanizable poly-trifluoropropylmethyl siloxanebased rubber is then applied.
---
paper_title: State of the Art in Selective Dissemination of Information

paper_content:

This paper condenses the results of a detailed survey of 100 SDI systems throughout the world, conducted this year by the American Society for Information Science. The text develops the concept of SDI as a computerized method to provide for the effective flow of technical information among scientific workers. The current status of SDI in university, industrial, and government environments is analyzed and placed in historical perspective, with possible future trends developed particularly those that might affect the form of tomorrow's technical information media.
---
paper_title: Multidimensional Recommender Systems: A Data Warehousing Approach

paper_content:

In this paper, we present a new data-warehousing-based approach to recommender systems. In particular, we propose to extend traditional two-dimensional user/item recommender systems to support multiple dimensions, as well as comprehensive profiling and hierarchical aggregation (OLAP) capabilities. We also introduce a new recommendation query language RQL that can express complex recommendations taking into account the proposed extensions. We describe how these extensions are integrated into a framework that facilitates more flexible and comprehensive user interactions with recommender systems.
---
paper_title: Using filtering agents to improve prediction quality in the GroupLens research collaborative filtering system

paper_content:

Collaborative filtering systems help address information overload by using the opinions of users in a community to make personal recommendations for documents to each user. Many collaborative filtering systems have few user opinions relative to the large number of documents available. This sparsity problem can reduce the utility of the filtering system by reducing the number of documents for which the system can make recommendations and adversely affecting the quality of recommendations. This paper defines and implements a model for integrating content-based ratings into a collaborative filtering system. The filterbot model allows collaborative filtering systems to address sparsity by tapping the strength of content filtering techniques. We identify and evaluate metrics for assessing the effectiveness of filterbots specifically, and filtering system enhancements in general. Finally, we experimentally validate the filterbot approach by showing that even simple filterbots such as spell checking can increase the utility for users of sparsely populated collaborative filtering systems.
---
paper_title: Inferring user interest

paper_content:

As the World Wide Web continues to grow, people find it impossible to access even a small portion of the information generated in a day from Usenet news, e-mail, and Web postings. Automated filters help us to prioritize and access only the information in which we're interested. Because opinions differ about the importance or relevance of information, people need personalized filters. Implicit indicators captured while users browse the Web can be as predictive of interest levels as explicit ratings.
---
paper_title: Joining Collaborative and Content-Based Filtering

paper_content:

Different authors have proposed combining content-based and collaborative attributes in a single table. In this article, we try out a different approach. We propose not to merge the two tables, but to join them as if they were tables in a relational database. As a result, we get several new application cases and a system architecture that supports the formulation of universal queries.
---
paper_title: Recommender systems for evaluating computer messages

paper_content:

Free-riding leads to too few evaluations. Beyond this, evaluations will be provided by an unrepresentative group—those who most enjoy the evaluation process. Hence, their evaluations may be misleading. Free-riding implies neither sloth nor conscious selfinterested calculation; it can arise innocently. For instance, a newsgroup reader with the flu may not evaluate messages for several days. Upon return, that reader should find a set of the best messages as selected by other readers, and none of the worst. Such an experience would probably diminish the reader’s zeal to evaluate. Figure 1 shows payoffs for Example 1. There are two potential readers for a particular message that is equally likely to be either “good” or “bad.” A single evaluation is assumed to completely identify the value of the message. Table (b) is derived by calculating expected outcomes from section (a). For example, assume B reads. If A also reads immediately, her payoff is 10 if the message is good and -12 if it is bad, implying -1 on average. If A waits, she will read only if the message is good, yielding an expected payoff of 5. In Example 1, it would be optimal for one person to read immediately and the other to wait, giving a total payoff of 4. Unfortunately, reader B gains by waiting no matter what reader A does, and vice versa. Thus, neither player reads immediately, although the social benefits (that is, benefits to the other player) of an evaluation by either person (+5 on average) outweigh its cost (-1 on average). No one will read a message unless it offers a positive expected personal payoff, and many useful messages will never be read. (Moreover, if effort in evaluations can be chosen when a message is read, it will be insufficient.) Analogously, any John Grisham novel sells well, regardless of initial reviews, but excellent novels by Recommender Systems for Evaluating Computer Messages
---
paper_title: Fab: Content-based, collaborative recommendation

paper_content:

A passive, integrating electromagnetic radiation power dosimeter. A radiofrequency or microwave antenna is combined with a diode detector/rectifier, a squaring circuit, and a electrochemical storage cell to provide an apparatus for determining the average energy of electromagnetic radiation incident on a surface. After a particular period of irradiation, the dosimeter can be interrogated electrically or visually, depending on the type of electrochemical cell employed, to yield the desired information. The apparatus has a substantially linear response to the electromagnetic power density over a wide range of electromagnetic field, and all of the energy required to record the incident energy is supplied by the electromagnetic field.
---
paper_title: Empirical Analysis of Predictive Algorithms for Collaborative Filtering

paper_content:

Collaborative filtering or recommender systems use a database about user preferences to predict additional topics or products a new user might like. In this paper we describe several algorithms designed for this task, including techniques based on correlation coefficients, vector-based similarity calculations, and statistical Bayesian methods. We compare the predictive accuracy of the various methods in a set of representative problem domains. We use two basic classes of evaluation metrics. The first characterizes accuracy over a set of individual predictions in terms of average absolute deviation. The second estimates the utility of a ranked list of suggested items. This metric uses an estimate of the probability that a user will see a recommendation in an ordered list. ::: ::: Experiments were run for datasets associated with 3 application areas, 4 experimental protocols, and the 2 evaluation metr rics for the various algorithms. Results indicate that for a wide range of conditions, Bayesian networks with decision trees at each node and correlation methods outperform Bayesian-clustering and vector-similarity methods. Between correlation and Bayesian networks, the preferred method depends on the nature of the dataset, nature of the application (ranked versus one-by-one presentation), and the availability of votes with which to make predictions. Other considerations include the size of database, speed of predictions, and learning time.
---
paper_title: Integrating Knowledge-based and Collaborative-filtering Recommender Systems

paper_content:

Knowledge-based and collaborative-filtering recommender systems facilitate electronic commerce by helping users find appropriate products from large catalogs. This paper discusses the strengths and weaknesses of both techniques and introduces the possibility of a hybrid recommender system that combines the two approaches. An approach is suggested in which knowledge-based techniques are used to bootstrap the collaborative filtering engine while its data pool is small, and the collaborative filter is used as a postfilter for the knowledge-based recommender. Collaborative Filtering Collaborative filtering recommender system are a widelyaccepted technique in electronic commerce. (See [Resnick & Varian, 1997] and other articles in that special issue. A recent survey is found in [Maes, Guttman & Moukas, 1999]. See also [Goldberg et al. 1992] and [Resnick, et al. 1994].) These systems aggregate data about customers’ purchasing habits or preferences and make recommendations to other users based on similarity in overall patterns. For example, in the Ringo music recommender system (Shardanand & Maes, 1995), users who had expressed their musical preferences by rating various artists and albums could get suggestions of other groups and recordings that others with similar preferences also liked. As a collaborative filtering system collects more ratings from more users, the probability increases that someone in the system will be a good match for any given new user. This beneficial property also has its downside, however. A collaborative filtering system must be initialized with a large amount of data, because a system with a small base of ratings is unlikely to be very useful. Further, the accuracy of the system is very sensitive to the number of rated items that can be associated with a given user (Shardanand & Maes, 1995). These factors contribute to a “ramp-up” problem: until there is a large number of users whose habits are known, the system cannot be useful for most users, and until a sufficient number of rated items has been collected, the system cannot be useful for a particular user. Another problem with collaborative filtering systems might be called the “banana” problem. Bananas are a frequently-purchased item in most American grocery stores, and the odds are high that any given market basket will contain bananas. A naive recommender system working from market basket data will always recommend bananas, simply because they are highly correlated with everything. Because the system has no notion of what foods ought to go together, it cannot screen out such suggestions. These drawbacks are not significant for some large ecommerce sites, such as Amazon.com, with a very large customer base, and a large and diverse product line that lends itself to multi-item purchases. A more difficult challenge is presented for a product such as an automobile that is bought much less frequently and one at a time. For an automobile, a home loan or any other infrequentlypurchased item, the system will not be able to use marketbasket or purchase history to make recommendations. A recommender system would never be able to say “people who bought a Geo Metro also bought a Ford Escort,” because that is not how people buy cars. Knowledge-based recommender systems What a recommender system for a car or other similar product must do is get information about users’ preferences: Why are they buying a car? Is comfort or fuel economy more important? Based on such information, the system can pursue a knowledge-based approach to generating a recommendation, by reasoning about what products meet the user’s requirements. The PersonalLogic recommender system offers a dialog that effectively walks the 1 The need to maintain user-identified logs of preferences and purchases also raises privacy concerns for collaborative filtering
---
paper_title: Horting hatches an egg: a new graph-theoretic approach to collaborative filtering

paper_content:

This paper introduces a new and novel approach to ratingbased collaborative filtering. The new technique is most appropriate for e-commerce merchants offering one or more groups of relatively homogeneous items such as compact disks, videos, books, software and the like. In contrast with other known collaborative filtering techniques, the new algorithm is graph-theoretic, based on the twin new concepts of ho&rag and predictability. As is demonstrated in this paper, the technique is fast, scalable, accurate, and requires only a modest learning curve. It makes use of a hierarchical classification scheme in order to introduce context into the rating process, and uses so-called creative links in order to find surprising and atypical items to recommend, perhaps even items which cross the group boundaries. The new technique is one of the key engines of the Intelligent Recommendation Algorithm (IRA) project, now being developed at IBM Research. In addition to several other recommendation engines, IRA contains a situation analyzer to determine the most appropriate mix of engines for a particular e-commerce merchant, as well as an engine for optimizing the placement of advertisements.
---
paper_title: Studying Recommendation Algorithms by Graph Analysis

paper_content:

We present a novel framework for studying recommendation algorithms in terms of the ‘jumps’ that they make to connect people to artifacts. This approach emphasizes reachability via an algorithm within the implicit graph structure underlying a recommender dataset and allows us to consider questions relating algorithmic parameters to properties of the datasets. For instance, given a particular algorithm ‘jump,’ what is the average path length from a person to an artifact? Or, what choices of minimum ratings and jumps maintain a connected graph? We illustrate the approach with a common jump called the ‘hammock’ using movie recommender datasets.
---
paper_title: An Efficient Boosting Algorithm for Combining Preferences

paper_content:

We study the problem of learning to accurately rank a set of objects by combining a given collection of ranking or preference functions. This problem of combining preferences arises in several applications, such as that of combining the results of different search engines, or the "collaborative-filtering" problem of ranking movies for a user based on the movie rankings provided by other users. In this work, we begin by presenting a formal framework for this general problem. We then describe and analyze an efficient algorithm called RankBoost for combining preferences based on the boosting approach to machine learning. We give theoretical results describing the algorithm's behavior both on the training data, and on new test data not seen during training. We also describe an efficient implementation of the algorithm for a particular restricted but common case. We next discuss two experiments we carried out to assess the performance of RankBoost. In the first experiment, we used the algorithm to combine different web search strategies, each of which is a query expansion for a given domain. The second experiment is a collaborative-filtering task for making movie recommendations.
---
paper_title: The SIFT information dissemination system

paper_content:

Information dissemination is a powerful mechanism for finding information in wide-area environments. An information dissemination server accepts long-term user queries, collects new documents from information sources, matches the documents against the queries, and continuously updates the users with relevant information. This paper is a retrospective of the Stanford Information Filtering Service (SIFT), a system that as of April 1996 was processing over 40,000 worldwide subscriptions and over 80,000 daily documents. The paper describes some of the indexing mechanisms that were developed for SIFT, as well as the evaluations that were conducted to select a scheme to implement. It also describes the implementation of SIFT, and experimental results for the actual system. Finally, it also discusses and experimentally evaluates techniques for distributing a service such as SIFT for added performance and availability.
---
paper_title: Eigentaste: A Constant Time Collaborative Filtering Algorithm

paper_content:

Eigentaste is a collaborative filtering algorithm that uses i>universal queries to elicit real-valued user ratings on a common set of items and applies principal component analysis (PCA) to the resulting dense subset of the ratings matrix. PCA facilitates dimensionality reduction for offline clustering of users and rapid computation of recommendations. For a database of i>n users, standard nearest-neighbor techniques require i>O(i>n) processing time to compute recommendations, whereas Eigentaste requires i>O(1) (constant) time. We compare Eigentaste to alternative algorithms using data from i>Jester, an online joke recommending system. ::: ::: Jester has collected approximately 2,500,000 ratings from 57,000 users. We use the Normalized Mean Absolute Error (NMAE) measure to compare performance of different algorithms. In the Appendix we use Uniform and Normal distribution models to derive analytic estimates of NMAE when predictions are random. On the Jester dataset, Eigentaste computes recommendations two orders of magnitude faster with no loss of accuracy. Jester is online at: http://eigentaste.berkeley.edu
---
paper_title: Using filtering agents to improve prediction quality in the GroupLens research collaborative filtering system

paper_content:

Collaborative filtering systems help address information overload by using the opinions of users in a community to make personal recommendations for documents to each user. Many collaborative filtering systems have few user opinions relative to the large number of documents available. This sparsity problem can reduce the utility of the filtering system by reducing the number of documents for which the system can make recommendations and adversely affecting the quality of recommendations. This paper defines and implements a model for integrating content-based ratings into a collaborative filtering system. The filterbot model allows collaborative filtering systems to address sparsity by tapping the strength of content filtering techniques. We identify and evaluate metrics for assessing the effectiveness of filterbots specifically, and filtering system enhancements in general. Finally, we experimentally validate the filterbot approach by showing that even simple filterbots such as spell checking can increase the utility for users of sparsely populated collaborative filtering systems.
---
paper_title: Fab: Content-based, collaborative recommendation

paper_content:

A passive, integrating electromagnetic radiation power dosimeter. A radiofrequency or microwave antenna is combined with a diode detector/rectifier, a squaring circuit, and a electrochemical storage cell to provide an apparatus for determining the average energy of electromagnetic radiation incident on a surface. After a particular period of irradiation, the dosimeter can be interrogated electrically or visually, depending on the type of electrochemical cell employed, to yield the desired information. The apparatus has a substantially linear response to the electromagnetic power density over a wide range of electromagnetic field, and all of the energy required to record the incident energy is supplied by the electromagnetic field.
---
paper_title: GroupLens: an open architecture for collaborative filtering of netnews

paper_content:

Collaborative filters help people make choices based on the opinions of other people. GroupLens is a system for collaborative filtering of netnews, to help people find articles they will like in the huge stream of available articles. News reader clients display predicted scores and make it easy for users to rate articles after they read them. Rating servers, called Better Bit Bureaus, gather and disseminate the ratings. The rating servers predict scores based on the heuristic that people who agreed in the past will probably agree again. Users can protect their privacy by entering ratings under pseudonyms, without reducing the effectiveness of the score prediction. The entire architecture is open: alternative software for news clients and Better Bit Bureaus can be developed independently and can interoperate with the components we have developed.
---
paper_title: Horting hatches an egg: a new graph-theoretic approach to collaborative filtering

paper_content:

This paper introduces a new and novel approach to ratingbased collaborative filtering. The new technique is most appropriate for e-commerce merchants offering one or more groups of relatively homogeneous items such as compact disks, videos, books, software and the like. In contrast with other known collaborative filtering techniques, the new algorithm is graph-theoretic, based on the twin new concepts of ho&rag and predictability. As is demonstrated in this paper, the technique is fast, scalable, accurate, and requires only a modest learning curve. It makes use of a hierarchical classification scheme in order to introduce context into the rating process, and uses so-called creative links in order to find surprising and atypical items to recommend, perhaps even items which cross the group boundaries. The new technique is one of the key engines of the Intelligent Recommendation Algorithm (IRA) project, now being developed at IBM Research. In addition to several other recommendation engines, IRA contains a situation analyzer to determine the most appropriate mix of engines for a particular e-commerce merchant, as well as an engine for optimizing the placement of advertisements.
---
paper_title: Studying Recommendation Algorithms by Graph Analysis

paper_content:

We present a novel framework for studying recommendation algorithms in terms of the ‘jumps’ that they make to connect people to artifacts. This approach emphasizes reachability via an algorithm within the implicit graph structure underlying a recommender dataset and allows us to consider questions relating algorithmic parameters to properties of the datasets. For instance, given a particular algorithm ‘jump,’ what is the average path length from a person to an artifact? Or, what choices of minimum ratings and jumps maintain a connected graph? We illustrate the approach with a common jump called the ‘hammock’ using movie recommender datasets.
---
paper_title: Collective dynamics of ‘small-world’ networks

paper_content:

Networks of coupled dynamical systems have been used to model biological oscillators1,2,3,4, Josephson junction arrays5,6, excitable media7, neural networks8,9,10, spatial games11, genetic control networks12 and many other self-organizing systems. Ordinarily, the connection topology is assumed to be either completely regular or completely random. But many biological, technological and social networks lie somewhere between these two extremes. Here we explore simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder. We find that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. We call them ‘small-world’ networks, by analogy with the small-world phenomenon13,14 (popularly known as six degrees of separation15). The neural network of the worm Caenorhabditis elegans, the power grid of the western United States, and the collaboration graph of film actors are shown to be small-world networks. Models of dynamical systems with small-world coupling display enhanced signal-propagation speed, computational power, and synchronizability. In particular, infectious diseases spread more easily in small-world networks than in regular lattices.
---
paper_title: Authoritative sources in a hyperlinked environment

paper_content:

The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools for extracting information from the link structures of such environments, and report on experiments that demonstrate their effectiveness in a variety of context on the World Wide Web. The central issue we address within our framework is the distillation of broad search topics, through the discovery of “authorative” information sources on such topics. We propose and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure. Our formulation has connections to the eigenvectors of certain matrices associated with the link graph; these connections in turn motivate additional heuristrics for link-based analysis.
---
paper_title: Footprints: history-rich tools for information foraging

paper_content:

Inspired by Hill and Hollans original work [7], we have beendeveloping a theory of interaction history and building tools toapply this theory to navigation in a complex information space. Wehave built a series of tools - map, paths, annota- tions andsignposts - based on a physical-world navigation metaphor. Thesetools have been in use for over a year. Our user study involved acontrolled browse task and showed that users were able to get thesame amount of work done with significantly less effort.
---
paper_title: Web usage mining for Web site evaluation

paper_content:

An electrical connector having means providing a signal when the connector members are fully interengaged. The signal means includes a pair of contacts in the two connector members which are axially spaced apart a distance greater than that of the power contacts in the two members so that the power contacts will become electrically coupled prior to the signal contacts when the connector members are mated. The signal contacts are preferably fixedly mounted in the connector insulators and conductors are releasably coupled to the rear portions of such contacts.
---
paper_title: Machine Learning for User Modeling

paper_content:

At first blush, user modeling appears to be a prime candidate for straightforward application of standard machine learning techniques. Observations of the user's behavior can provide training examples that a machine learning system can use to form a model designed to predict future actions. However, user modeling poses a number of challenges for machine learning that have hindered its application in user modeling, including: the need for large data sets; the need for labeled data; concept drift; and computational complexity. This paper examines each of these issues and reviews approaches to resolving them.
---
paper_title: Web usage mining: discovery and applications of usage patterns from Web data

paper_content:

Web usage mining is the application of data mining techniques to discover usage patterns from Web data, in order to understand and better serve the needs of Web-based applications. Web usage mining consists of three phases, namely preprocessing, pattern discovery, and pattern analysis. This paper describes each of these phases in detail. Given its application potential, Web usage mining has seen a rapid increase in interest, from both the research and practice communities. This paper provides a detailed taxonomy of the work in this area, including research efforts as well as commercial offerings. An up-to-date survey of the existing work is also provided. Finally, a brief overview of the WebSIFT system as an example of a prototypical Web usage mining system is given.
---
paper_title: Learning and Revising User Profiles: The Identification of Interesting Web Sites

paper_content:

We discuss algorithms for learning and revising user profiles that can determine which World Wide Web sites on a given topic would be interesting to a user. We describe the use of a naive Bayesian classifier for this task, and demonstrate that it can incrementally learn profiles from user feedback on the interestingness of Web sites. Furthermore, the Bayesian classifier may easily be extended to revise user provided profiles. In an experimental evaluation we compare the Bayesian classifier to computationally more intensive alternatives, and show that it performs at least as well as these approaches throughout a range of different domains. In addition, we empirically analyze the effects of providing the classifier with background knowledge in form of user defined profiles and examine the use of lexical knowledge for feature selection. We find that both approaches can substantially increase the prediction accuracy.
---
paper_title: Horting hatches an egg: a new graph-theoretic approach to collaborative filtering

paper_content:

This paper introduces a new and novel approach to ratingbased collaborative filtering. The new technique is most appropriate for e-commerce merchants offering one or more groups of relatively homogeneous items such as compact disks, videos, books, software and the like. In contrast with other known collaborative filtering techniques, the new algorithm is graph-theoretic, based on the twin new concepts of ho&rag and predictability. As is demonstrated in this paper, the technique is fast, scalable, accurate, and requires only a modest learning curve. It makes use of a hierarchical classification scheme in order to introduce context into the rating process, and uses so-called creative links in order to find surprising and atypical items to recommend, perhaps even items which cross the group boundaries. The new technique is one of the key engines of the Intelligent Recommendation Algorithm (IRA) project, now being developed at IBM Research. In addition to several other recommendation engines, IRA contains a situation analyzer to determine the most appropriate mix of engines for a particular e-commerce merchant, as well as an engine for optimizing the placement of advertisements.
---
paper_title: Machine Learning in User Modeling

paper_content:

It is generally recognized that information systems are becoming more complex and, therefore, intelligent user interfaces are needed to improve user interaction with these systems. Furthermore, the exponential growth of the Internet makes it difficult for the users to cope with the huge amount of available on-line information. The challenge that information providers and system engineers face is the creation of adaptive (Webbased) applications, as well as the development of “personalized” retrieval and filtering mechanisms. Responses to this challenge come from various disciplines including machine learning and data mining, intelligent agents and multi-agent systems, intelligent tutoring, information retrieval, etc.
---
paper_title: Using frequency-of-mention in public conversations for social filtering

paper_content:

We report on an investigation of using Usenet newsgroups for social filtering of Web resources. Our main empirical results are: (1) for the period of May ’96 to Jul ’96, about 23% of Usenet news messages mention Web resources, (2) 19% of resource mentions are recommendations (as opposed, e.g., to home pages), (3) we can’automatically recognize recommendations with at least 90% accuracy, and (4) in some newsgroups, certain resources are mentioned significantly more frequently than others and thus appear to play a central role for that community. We have created a Web site that summarizes the most frequently and recently mentioned Web resources for 1400 newsgroups.
---
paper_title: Explaining collaborative filtering recommendations

paper_content:

Automated collaborative filtering (ACF) systems predict a person's affinity for items or information by connecting that person's recorded interests with the recorded interests of a community of people and sharing ratings between like-minded persons. However, current recommender systems are black boxes, providing no transparency into the working of the recommendation. Explanations provide that transparency, exposing the reasoning and data behind a recommendation. In this paper, we address explanation interfaces for ACF systems - how they should be implemented and why they should be implemented. To explore how, we present a model for explanations based on the user's conceptual model of the recommendation process. We then present experimental results demonstrating what components of an explanation are the most compelling. To address why, we present experimental evidence that shows that providing explanations can improve the acceptance of ACF systems. We also describe some initial explorations into measuring how explanations can improve the filtering performance of users.
---
paper_title: Learning users' interests by unobtrusively observing their normal behavior

paper_content:

For intelligent interfaces attempting to learn a user's interests, the cost of obtaining labeled training instances is prohibitive because the user must directly label each training instance, and few users are willing to do so. We present an approach that circumvents the need for human-labeled pages. Instead, we learn “surrogate” tasks where the desired output is easily measured, such as the number of hyperlinks clicked on a page or the amount of scrolling performed. Our assumption is that these outputs will highly correlate with the user's interests. In other words, by unobtrusively “observing” the user's behavior we are able to learn functions of value. For example, an intelligent browser could silently observe the user's browsing behavior during the day, then use these training examples to learn such functions and gather, during the middle of the night, pages that are likely to be of interest to the user. Previous work has focused on learning a user profile by passively observing the hyperlinks clicked on and those passed over. We extend this approach by measuring user mouse and scrolling activity in addition to user browsing activity. We present empirical results that demonstrate our agent can accurately predict some easily measured aspects of one's use of his or her browser.
---
paper_title: Mining association rules between sets of items in large databases

paper_content:

We are given a large database of customer transactions. Each transaction consists of items purchased by a customer in a visit. We present an efficient algorithm that generates all significant association rules between items in the database. The algorithm incorporates buffer management and novel estimation and pruning techniques. We also present results of applying this algorithm to sales data obtained from a large retailing company, which shows the effectiveness of the algorithm.
---
paper_title: Authoritative sources in a hyperlinked environment

paper_content:

The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools for extracting information from the link structures of such environments, and report on experiments that demonstrate their effectiveness in a variety of context on the World Wide Web. The central issue we address within our framework is the distillation of broad search topics, through the discovery of “authorative” information sources on such topics. We propose and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure. Our formulation has connections to the eigenvectors of certain matrices associated with the link graph; these connections in turn motivate additional heuristrics for link-based analysis.
---
paper_title: Fab: Content-based, collaborative recommendation

paper_content:

A passive, integrating electromagnetic radiation power dosimeter. A radiofrequency or microwave antenna is combined with a diode detector/rectifier, a squaring circuit, and a electrochemical storage cell to provide an apparatus for determining the average energy of electromagnetic radiation incident on a surface. After a particular period of irradiation, the dosimeter can be interrogated electrically or visually, depending on the type of electrochemical cell employed, to yield the desired information. The apparatus has a substantially linear response to the electromagnetic power density over a wide range of electromagnetic field, and all of the energy required to record the incident energy is supplied by the electromagnetic field.
---
paper_title: Self-organization and identification of Web communities

paper_content:

The vast improvement in information access is not the only advantage resulting from the increasing percentage of hyperlinked human knowledge available on the Web. Additionally, much potential exists for analyzing interests and relationships within science and society. However, the Web's decentralized and unorganized nature hampers content analysis. Millions of individuals operating independently and having a variety of backgrounds, knowledge, goals and cultures author the information on the Web. Despite the Web's decentralized, unorganized, and heterogeneous nature, our work shows that the Web self-organizes and its link structure allows efficient identification of communities. This self-organization is significant because no central authority or process governs the formation and structure of hyperlinks.
---
paper_title: The Hidden Web

paper_content:

The difficulty of finding information on the World Wide Web by browsing hypertext documents has led to the development and deployment of various search engines and indexing techniques. However, many information-gathering tasks are better handled by finding a referral to a human expert rather than by simply interacting with online information sources. A personal referral allows a user to judge the quality of the information he or she is receiving as well as to potentially obtain information that is deliberately not made public. The process of finding an expert who is both reliable and likely to respond to the user can be viewed as a search through the net-work of social relationships between individuals as opposed to a search through the network of hypertext documents. The goal of the REFERRAL WEB Project is to create models of social networks by data mining the web and develop tools that use the models to assist in locating experts and related information search and evaluation tasks.
---
paper_title: Studying Recommendation Algorithms by Graph Analysis

paper_content:

We present a novel framework for studying recommendation algorithms in terms of the ‘jumps’ that they make to connect people to artifacts. This approach emphasizes reachability via an algorithm within the implicit graph structure underlying a recommender dataset and allows us to consider questions relating algorithmic parameters to properties of the datasets. For instance, given a particular algorithm ‘jump,’ what is the average path length from a person to an artifact? Or, what choices of minimum ratings and jumps maintain a connected graph? We illustrate the approach with a common jump called the ‘hammock’ using movie recommender datasets.
---
paper_title: As we may think

paper_content:

As Director of the Office of Scientific Research and Development, Dr. Vannevar Bush has coordinated the activities of some six thousand leading American scientists in the application of science to warfare. In this significant article he holds up an incentive for scientists when the fighting has ceased. He urges that men of science should then turn to the massive task of making more accessible our bewildering store of knowledge. For years inventions have extended man's physical powers rather than the powers of his mind. Trip hammers that multiply the fists, microscopes that sharpen the eye, and engines of destruction and detection are new results, but not the end results, of modern science. Now, says Dr. Bush, instruments are at hand which, if properly developed, will give man access to and command over the inherited knowledge of the ages. The perfection of these pacific instruments should be the first objective of our scientists as they emerge from their war work. Like Emerson's famous address of 1837 on "The American Scholar," this paper by Dr. Bush calls for a new relationship between thinking man and the sum of our knowledge.
---
paper_title: The Web as a graph: Measurements, models and methods

paper_content:

The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph is a fascinating object of study: it has several hundred million nodes today, over a billion links, and appears to grow exponentially with time. There are many reasons -- mathematical, sociological, and commercial -- for studying the evolution of this graph. In this paper we begin by describing two algorithms that operate on the Web graph, addressing problems from Web search and automatic community discovery. We then report a number of measurements and properties of this graph that manifested themselves as we ran these algorithms on the Web. Finally, we observe that traditional random graph models do not explain these observations, and we propose a new family of random graph models. These models point to a rich new sub-field of the study of random graphs, and raise questions about the analysis of graph algorithms on the Web.
---
paper_title: The Hidden Web

paper_content:

The difficulty of finding information on the World Wide Web by browsing hypertext documents has led to the development and deployment of various search engines and indexing techniques. However, many information-gathering tasks are better handled by finding a referral to a human expert rather than by simply interacting with online information sources. A personal referral allows a user to judge the quality of the information he or she is receiving as well as to potentially obtain information that is deliberately not made public. The process of finding an expert who is both reliable and likely to respond to the user can be viewed as a search through the net-work of social relationships between individuals as opposed to a search through the network of hypertext documents. The goal of the REFERRAL WEB Project is to create models of social networks by data mining the web and develop tools that use the models to assist in locating experts and related information search and evaluation tasks.
---
paper_title: Graph structure in the Web

paper_content:

The study of the web as a graph is not only fascinating in its own right, but also yields valuable insight into web algorithms for crawling, searching and community discovery, and the sociological phenomena which characterize its evolution. We report on experiments on local and global properties of the web graph using two Altavista crawls each with over 200 million pages and 1.5 billion links. Our study indicates that the macroscopic structure of the web is considerably more intricate than suggested by earlier experiments on a smaller scale.
---
paper_title: Mining the Web's Link Structure

paper_content:

The Web is a hypertext body of approximately 300 million pages that continues to grow at roughly a million pages per day. Page variation is more prodigious than the data's raw scale: taken as a whole, the set of Web pages lacks a unifying structure and shows far more authoring style and content variation than that seen in traditional text document collections. This level of complexity makes an "off-the-shelf" database management and information retrieval solution impossible. To date, index based search engines for the Web have been the primary tool by which users search for information. Such engines can build giant indices that let you quickly retrieve the set of all Web pages containing a given word or string. Experienced users can make effective use of such engines for tasks that can be solved by searching for tightly constrained key words and phrases. These search engines are, however, unsuited for a wide range of equally important tasks. In particular, a topic of any breadth will typically contain several thousand or million relevant Web pages. How then, from this sea of pages, should a search engine select the correct ones-those of most value to the user? Clever is a search engine that analyzes hyperlinks to uncover two types of pages: authorities, which provide the best source of information on a given topic; and hubs, which provide collections of links to authorities. We outline the thinking that went into Clever's design, report briefly on a study that compared Clever's performance to that of Yahoo and AltaVista, and examine how our system is being extended and updated.
---
paper_title: Studying Recommendation Algorithms by Graph Analysis

paper_content:

We present a novel framework for studying recommendation algorithms in terms of the ‘jumps’ that they make to connect people to artifacts. This approach emphasizes reachability via an algorithm within the implicit graph structure underlying a recommender dataset and allows us to consider questions relating algorithmic parameters to properties of the datasets. For instance, given a particular algorithm ‘jump,’ what is the average path length from a person to an artifact? Or, what choices of minimum ratings and jumps maintain a connected graph? We illustrate the approach with a common jump called the ‘hammock’ using movie recommender datasets.
---
paper_title: The Anatomy of a Large-Scale Hypertextual Web Search Engine

paper_content:

In this paper, we present Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext. Google is designed to crawl and index the Web efficiently and produce much more satisfying search results than existing systems. The prototype with a full text and hyperlink database of at least 24million pages is available at http://google.stanford.edu/ To engineer a search engine is a challenging task. Search engines index tens to hundreds of millions of web pages involving a comparable number of distinct terms. They answer tens of millions of queries every day. Despite the importance of large-scale search engines on the web, very little academic research has been done on them. Furthermore, due to rapid advance in technology and web proliferation, creating a web search engine today is very different from 3years ago. This paper provides an in-depth description of our large-scale web search engine - the first such detailed public description we know of to date. Apart from the problems of scaling traditional search techniques to data of this magnitude, there are new technical challenges involved with using the additional information present in hypertext to produce better search results. This paper addresses this question of how to build a practical large-scale system which can exploit the additional information present in hypertext. Also we look at the problem of how to effectively deal with uncontrolled hypertext collections, where anyone can publish anything they want.
---
paper_title: Does “authority” mean quality? predicting expert quality ratings of Web documents

paper_content:

For many topics, the World Wide Web contains hundreds or thousands of relevant documents of widely varying quality. Users face a daunting challenge in identifying a small subset of documents worthy of their attention. Link analysis algorithms have received much interest recently, in large part for their potential to identify high quality items. We report here on an experimental evaluation of this potential. We evaluated a number of link and content-based algorithms using a dataset of web documents rated for quality by human topic experts. Link-based metrics did a good job of picking out high-quality items. Precision at 5 is about 0.75, and precision at 10 is about 0.55; this is in a dataset where 0.32 of all documents were of high quality. Surprisingly, a simple content-based metric performed nearly as well; ranking documents by the total number of pages on their containing site.
---
paper_title: Authoritative sources in a hyperlinked environment

paper_content:

The network structure of a hyperlinked environment can be a rich source of information about the content of the environment, provided we have effective means for understanding it. We develop a set of algorithmic tools for extracting information from the link structures of such environments, and report on experiments that demonstrate their effectiveness in a variety of context on the World Wide Web. The central issue we address within our framework is the distillation of broad search topics, through the discovery of “authorative” information sources on such topics. We propose and test an algorithmic formulation of the notion of authority, based on the relationship between a set of relevant authoritative pages and the set of “hub pages” that join them together in the link structure. Our formulation has connections to the eigenvectors of certain matrices associated with the link graph; these connections in turn motivate additional heuristrics for link-based analysis.
---
paper_title: Highly optimized tolerance: A mechanism for power laws in designed systems

paper_content:

We introduce a mechanism for generating power law distributions, referred to as highly optimized tolerance (HOT), which is motivated by biological organisms and advanced engineering technologies. Our focus is on systems which are optimized, either through natural selection or engineering design, to provide robust performance despite uncertain environments. We suggest that power laws in these systems are due to tradeoffs between yield, cost of resources, and tolerance to risks. These tradeoffs lead to highly optimized designs that allow for occasional large events. We investigate the mechanism in the context of percolation and sand pile models in order to emphasize the sharp contrasts between HOT and self-organized criticality (SOC), which has been widely suggested as the origin for power laws in complex systems. Like SOC, HOT produces power laws. However, compared to SOC, HOT states exist for densities which are higher than the critical density, and the power laws are not restricted to special values of the density. The characteristic features of HOT systems include: (1) high efficiency, performance, and robustness to designed-for uncertainties; (2) hypersensitivity to design flaws and unanticipated perturbations; (3) nongeneric, specialized, structured configurations; and (4) power laws. The first three of these are in contrast to the traditional hallmarks of criticality, and are obtained by simply adding the element of design to percolation and sand pile models, which completely changes their characteristics.
---
paper_title: Emergence of scaling in random networks

paper_content:

Systems as diverse as genetic networks or the World Wide Web are best described as networks with complex topology. A common property of many large networks is that the vertex connectivities follow a scale-free power-law distribution. This feature was found to be a consequence of two generic mechanisms: (i) networks expand continuously by the addition of new vertices, and (ii) new vertices attach preferentially to sites that are already well connected. A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.
---
paper_title: Navigation in a small world

paper_content:

It is easier to find short chains between points in some networks than others. The small-world phenomenon — the principle that most of us are linked by short chains of acquaintances — was first investigated as a question in sociology1,2 and is a feature of a range of networks arising in nature and technology3,4,5. Experimental study of the phenomenon1 revealed that it has two fundamental components: first, such short chains are ubiquitous, and second, individuals operating with purely local information are very adept at finding these chains. The first issue has been analysed2,3,4, and here I investigate the second by modelling how individuals can find short chains in a large social network.
---
paper_title: The Small World Web

paper_content:

I show that the World Wide Web is a small world, in the sense that sites are highly clustered yet the path length between them is small. I also demonstrate the advantages of a search engine which makes use of the fact that pages corresponding to a particular search query can form small world networks. In a further application, the search engine uses the small-worldness of its search results to measure the connectedness between communities on the Web.
---
paper_title: The small-world phenomenon: an algorithmic perspective

paper_content:

Long a matter of folklore, the ``small-world phenomenon'''' --the principle that we are all linked by short chains of acquaintances --was inaugurated as an area of experimental study in the social sciences through the pioneering work of Stanley Milgram in the 1960''s. This work was among the first to make the phenomenon quantitative, allowing people to speak of the ``six degrees of separation'''' between any two people in the United States. Since then, a number of network models have been proposed as frameworks in which to study the problem analytically. One of the most refined of these models was formulated in recent work of Watts and Strogatz; their framework provided compelling evidence that the small-world phenomenon is pervasive in a range of networks arising in nature and technology, and a fundamental ingredient in the evolution of the World Wide Web. But existing models are insufficient to explain the striking algorithmic component of Milgram''s original findings: that individuals using local information are collectively very effective at actually constructing short paths between two points in a social network. Although recently proposed network models are rich in short paths, we prove that no decentralized algorithm, operating with local information only, can construct short paths in these networks with non-negligible probability. We then define an infinite family of network models that naturally generalizes the Watts-Strogatz model, and show that for one of these models, there is a decentralized algorithm capable of finding short paths with high probability. More generally, we provide a strong characterization of this family of network models, showing that there is in fact a unique model within the family for which decentralized algorithms are effective.
---
paper_title: Collective dynamics of ‘small-world’ networks

paper_content:

Networks of coupled dynamical systems have been used to model biological oscillators1,2,3,4, Josephson junction arrays5,6, excitable media7, neural networks8,9,10, spatial games11, genetic control networks12 and many other self-organizing systems. Ordinarily, the connection topology is assumed to be either completely regular or completely random. But many biological, technological and social networks lie somewhere between these two extremes. Here we explore simple models of networks that can be tuned through this middle ground: regular networks ‘rewired’ to introduce increasing amounts of disorder. We find that these systems can be highly clustered, like regular lattices, yet have small characteristic path lengths, like random graphs. We call them ‘small-world’ networks, by analogy with the small-world phenomenon13,14 (popularly known as six degrees of separation15). The neural network of the worm Caenorhabditis elegans, the power grid of the western United States, and the collaboration graph of film actors are shown to be small-world networks. Models of dynamical systems with small-world coupling display enhanced signal-propagation speed, computational power, and synchronizability. In particular, infectious diseases spread more easily in small-world networks than in regular lattices.
---
paper_title: The Diameter of the World Web Web

paper_content:

Acoustic well-logging methods and apparatus are provided for investigating earth formations traversed by a borehole. Acoustic waves are transmitted from different points in the borehole and received at other points in the borehole, and a reception signal is generated representative of the received acoustic waves. The time interval between the instant the measurement waves are transmitted and the instant the instantaneous amplitude of the reception signal exceeds a given detection threshold for the first time is measured as a function of depth and the value of the detection threshold is adjusted during each measurement sequence in accordance with the amplitude of the noise received during the next preceding listening interval.
---
paper_title: Eigentaste: A Constant Time Collaborative Filtering Algorithm

paper_content:

Eigentaste is a collaborative filtering algorithm that uses i>universal queries to elicit real-valued user ratings on a common set of items and applies principal component analysis (PCA) to the resulting dense subset of the ratings matrix. PCA facilitates dimensionality reduction for offline clustering of users and rapid computation of recommendations. For a database of i>n users, standard nearest-neighbor techniques require i>O(i>n) processing time to compute recommendations, whereas Eigentaste requires i>O(1) (constant) time. We compare Eigentaste to alternative algorithms using data from i>Jester, an online joke recommending system. ::: ::: Jester has collected approximately 2,500,000 ratings from 57,000 users. We use the Normalized Mean Absolute Error (NMAE) measure to compare performance of different algorithms. In the Appendix we use Uniform and Normal distribution models to derive analytic estimates of NMAE when predictions are random. On the Jester dataset, Eigentaste computes recommendations two orders of magnitude faster with no loss of accuracy. Jester is online at: http://eigentaste.berkeley.edu
---
paper_title: Empirical Analysis of Predictive Algorithms for Collaborative Filtering

paper_content:

Collaborative filtering or recommender systems use a database about user preferences to predict additional topics or products a new user might like. In this paper we describe several algorithms designed for this task, including techniques based on correlation coefficients, vector-based similarity calculations, and statistical Bayesian methods. We compare the predictive accuracy of the various methods in a set of representative problem domains. We use two basic classes of evaluation metrics. The first characterizes accuracy over a set of individual predictions in terms of average absolute deviation. The second estimates the utility of a ranked list of suggested items. This metric uses an estimate of the probability that a user will see a recommendation in an ordered list. ::: ::: Experiments were run for datasets associated with 3 application areas, 4 experimental protocols, and the 2 evaluation metr rics for the various algorithms. Results indicate that for a wide range of conditions, Bayesian networks with decision trees at each node and correlation methods outperform Bayesian-clustering and vector-similarity methods. Between correlation and Bayesian networks, the preferred method depends on the nature of the dataset, nature of the application (ranked versus one-by-one presentation), and the availability of votes with which to make predictions. Other considerations include the size of database, speed of predictions, and learning time.
---
paper_title: Eigentaste: A Constant Time Collaborative Filtering Algorithm

paper_content:

Eigentaste is a collaborative filtering algorithm that uses i>universal queries to elicit real-valued user ratings on a common set of items and applies principal component analysis (PCA) to the resulting dense subset of the ratings matrix. PCA facilitates dimensionality reduction for offline clustering of users and rapid computation of recommendations. For a database of i>n users, standard nearest-neighbor techniques require i>O(i>n) processing time to compute recommendations, whereas Eigentaste requires i>O(1) (constant) time. We compare Eigentaste to alternative algorithms using data from i>Jester, an online joke recommending system. ::: ::: Jester has collected approximately 2,500,000 ratings from 57,000 users. We use the Normalized Mean Absolute Error (NMAE) measure to compare performance of different algorithms. In the Appendix we use Uniform and Normal distribution models to derive analytic estimates of NMAE when predictions are random. On the Jester dataset, Eigentaste computes recommendations two orders of magnitude faster with no loss of accuracy. Jester is online at: http://eigentaste.berkeley.edu
---
paper_title: Empirical Analysis of Predictive Algorithms for Collaborative Filtering

paper_content:

Collaborative filtering or recommender systems use a database about user preferences to predict additional topics or products a new user might like. In this paper we describe several algorithms designed for this task, including techniques based on correlation coefficients, vector-based similarity calculations, and statistical Bayesian methods. We compare the predictive accuracy of the various methods in a set of representative problem domains. We use two basic classes of evaluation metrics. The first characterizes accuracy over a set of individual predictions in terms of average absolute deviation. The second estimates the utility of a ranked list of suggested items. This metric uses an estimate of the probability that a user will see a recommendation in an ordered list. ::: ::: Experiments were run for datasets associated with 3 application areas, 4 experimental protocols, and the 2 evaluation metr rics for the various algorithms. Results indicate that for a wide range of conditions, Bayesian networks with decision trees at each node and correlation methods outperform Bayesian-clustering and vector-similarity methods. Between correlation and Bayesian networks, the preferred method depends on the nature of the dataset, nature of the application (ranked versus one-by-one presentation), and the availability of votes with which to make predictions. Other considerations include the size of database, speed of predictions, and learning time.
---
paper_title: Explaining collaborative filtering recommendations

paper_content:

Automated collaborative filtering (ACF) systems predict a person's affinity for items or information by connecting that person's recorded interests with the recorded interests of a community of people and sharing ratings between like-minded persons. However, current recommender systems are black boxes, providing no transparency into the working of the recommendation. Explanations provide that transparency, exposing the reasoning and data behind a recommendation. In this paper, we address explanation interfaces for ACF systems - how they should be implemented and why they should be implemented. To explore how, we present a model for explanations based on the user's conceptual model of the recommendation process. We then present experimental results demonstrating what components of an explanation are the most compelling. To address why, we present experimental evidence that shows that providing explanations can improve the acceptance of ACF systems. We also describe some initial explorations into measuring how explanations can improve the filtering performance of users.
---
paper_title: Mining association rules between sets of items in large databases

paper_content:

We are given a large database of customer transactions. Each transaction consists of items purchased by a customer in a visit. We present an efficient algorithm that generates all significant association rules between items in the database. The algorithm incorporates buffer management and novel estimation and pruning techniques. We also present results of applying this algorithm to sales data obtained from a large retailing company, which shows the effectiveness of the algorithm.
---
paper_title: Comparing Recommendations Made by Online Systems and Friends

paper_content:

The quality of recommendations and usability of six online recommender systems (RS) was examined. Three book RS (Amazon.com, RatingZone & Sleeper) and three movie RS (Amazon.com, MovieCritic, Reel.com) were evaluated. Quality of recommendations was explored by comparing recommendations made by RS to recommendations made by the user’s friends. Results showed that the user’s friends consistently provided better recommendations than RS. However, users did find items recommended by online RS useful: recommended items were often “new” and “unexpected”, while the items recommended by friends mostly served as reminders of previously identified interests. Usability evaluation of the RS showed that users did not mind providing more input to the system in order to get better recommendations. Also users trusted a system more if it recommended items that they had previously liked. A common way for people to decide what books to read is to ask friends and acquaintances for recommendations. The logic behind this time-tested method is that one shares tastes in books, movies, music etc., with one’s friends. As such, items that appeal to them (friends) might appeal to me. Online Recommender Systems (RS) attempt to create a technological proxy for this social filtering process. The assumption behind many RS is that a good way to personalize recommendations for a user is to identify people with similar interests and recommend items that have interested these like-minded people (Resnick & Varian (1997), Goldberg, Nichols, Oki & Terry (1992)). This premise forms the statistical basis of most collaborative filtering algorithms. Since the goal of most RS is to replace (or at least augment) what is essentially a social process, we decided to directly compare the two ways of receiving recommendations (friends & online RS). Do users like receiving recommendations from an online system? How do the recommendations provided by online systems differ from those provided by the users’ friends? Our hypothesis was that friends would make superior recommendations since they know the user well, and have intimate knowledge of his / her tastes in a number of domains. In contrast, RS only have limited, domain-specific knowledge about the users. Also, information retrieval systems do not yet match the sophistication of human judgment processes.
---
paper_title: The role of transparency in recommender systems

paper_content:

Recommender Systems act as a personalized decision guides, aiding users in decisions on matters related to personal taste. Most previous research on Recommender Systems has focused on the statistical accuracy of the algorithms driving the systems, with little emphasis on interface issues and the user's perspective. The goal of this research was to examine the role of transprency (user understanding of why a particular recommendation was made) in Recommender Systems. To explore this issue, we conducted a user study of five music Recommender Systems. Preliminary results indicate that users like and feel more confident about recommendations that they perceive as transparent.
---
paper_title: Privacy Risks in Recommender Systems

paper_content:

Recommender system users who rate items across disjoint domains face a privacy risk analogous to the one that occurs with statistical database queries.
---
paper_title: Exposing profiles to build trust in a recommender

paper_content:

This paper describes a method for increasing trust in a TV show recommender. We look for people in common between programs users watch and new programs that are highly rated by our TV show recommender. We then present these to users in a conversational sentence, helping them decide if they want to try the new show. This method has been implemeted in our current TV show recommender interface and will be tested in the near future.
---
paper_title: The role of transparency in recommender systems

paper_content:

Recommender Systems act as a personalized decision guides, aiding users in decisions on matters related to personal taste. Most previous research on Recommender Systems has focused on the statistical accuracy of the algorithms driving the systems, with little emphasis on interface issues and the user's perspective. The goal of this research was to examine the role of transprency (user understanding of why a particular recommendation was made) in Recommender Systems. To explore this issue, we conducted a user study of five music Recommender Systems. Preliminary results indicate that users like and feel more confident about recommendations that they perceive as transparent.
---
paper_title: Personalization and privacy

paper_content:

Personalization has been a hot topic or nearly a decade now, and many new products and advanced algorithms have emerged in that time. Several companies now sell tools such as recommender systems, which take input about users and products and generate recommendations about which products the users will like best. At their best, recommenders can be wonderful tools for users, helping them sort through myriad items they could read, buy, or watch to select those few that are most valuable to them. The algorithms that power these systems have evolved dramatically, and the best can produce rapid recommendations over data sets of millions of users and hundreds of thousands of products. The other edge of the sword is that recommender systems provide perfect tools for marketers and others to invade users' privacy. After all, recommenders; seek to learn everything about our preferences, including what we like to read, what we like to buy, how much money we spend, and what influences us to spend it. How a recommender deals with privacy decides whether its-users view it,as a boon or a bane. If the recommender only uses this information to help us find items to purchase on a Web site, we will probably value the feature - it might even bring us back to shop there again. On the other hand, if the Web site sells our information to other companies, so they can more effectively bother us. with phone calls at dinner time, we'll probably feel our privacy has been invaded. Privacy is a critical issue for recommender systems. In the end, personalization is an important factor in developing effective Web sites because it creates a user experience that is both compelling and sticky. The experience is compelling because it helps users find exactly the information, products, and services they need. It is sticky because a personalized Web site trains itself over time to serve its users better, which makes those users less likely to go to a new site that they would have to train all over again.
---
paper_title: Is speech recognition becoming mainstream

paper_content:

The Web's connectivity, wireless technology and handheld devices - combined with effective grammar-based speech recognition in a VoiceXML infrastructure may finally bring speech recognition to mass-market prominence.
---
paper_title: Studying Recommendation Algorithms by Graph Analysis

paper_content:

We present a novel framework for studying recommendation algorithms in terms of the ‘jumps’ that they make to connect people to artifacts. This approach emphasizes reachability via an algorithm within the implicit graph structure underlying a recommender dataset and allows us to consider questions relating algorithmic parameters to properties of the datasets. For instance, given a particular algorithm ‘jump,’ what is the average path length from a person to an artifact? Or, what choices of minimum ratings and jumps maintain a connected graph? We illustrate the approach with a common jump called the ‘hammock’ using movie recommender datasets.
---

Title: A Connection-Centric Survey of Recommender Systems Research
Section 1: Introduction
Description 1: Introduce the concept of recommender systems and the motivation for reducing information overload.

Section 2: A Chequered History
Description 2: Present an historical perspective of recommender systems and outline their evolution from Information Retrieval (IR).

Section 3: Creating Connections: Explicit User Modeling
Description 3: Showcase techniques to explicitly model users for social network formation.

Section 4: Discovering Extant Social Networks
Description 4: Describe approaches to identifying existing communities to explore for recommendation.

Section 5: Broadening Issues
Description 5: Address broader issues related to recommender systems, such as evaluation, targeting, privacy, and trust.

Section 6: Future Work and Conclusion
Description 6: Identify various opportunities for future research in recommender systems and provide concluding thoughts.