Information Aggregation in Quantized Consensus, Recommender Systems, and Ranking

Abstract

Information aggregation is the science of collecting and aggregating knowledge from data. With the development of large scale datasets, the amount of information is growing rapidly. In recent years, the problem of information aggregation has received considerable attention, and finds applications in multiple disciplines. This dissertation addresses a variety of problems in information aggregation, including quantized consensus, recommender systems, and ranking.

This dissertation starts with investigating a class of distributed quantized consensus algorithms for arbitrary networks. An upper bound on the convergence time of the algorithms is derived for an arbitrary graph of size N. Inspired by this class of gossip consensus algorithms and Google's PageRank, and motivated by the development of group-based social networks, a privacy preserving recommender system based on groups is proposed. The main idea is to use groups as a natural middleware to preserve users' privacy. A novel hybrid collaborative filtering model based on random walks is constructed to provide recommendation and prediction to group members. Lastly, the error probability of ranking algorithms equipped with differential privacy is analyzed, and upper bounds on the error rates for arbitrary positional ranking rules are derived.