Annotation 2
Friday, 3:30–5:00 PM
Chair: Debora Donato
Monitoring Algorithms for Negative Feedback Systems
Mark Sandler, S Muthukrishnan
There are many online systems where millions of users post content such as videos, reviews of items such as products, services and businesses, etc. While there are general rules for good behavior or even formal Terms of Service, there are still users that post content that is not suitable. Increasingly, online systems rely on {\em other} users who view the posted content to provide feedback. We study online systems where users report negative feedback, ie report abuse; these systems are quite distinct from traditional feedback and much-studied reputation systems that focus on eliciting popularity of content by various voting methods. The central problem that we study is to {\em monitor} the quality of negative feedback which may be incorrect, or perhaps even malicious. Systems address this problem by testing flags manually, which is an expensive operation. As a result, there is a tradeoff between the number of tests and the number of errors, ie, the number of incorrect flags the monitoring system misses. In this paper we present a simple model for monitoring negative feedbacks, that is still general enough to be applicable for a variety of systems. 2. We design and analyze randomized monitoring algorithm. Irrespective of user’s strategy, we guarantee the total expected error is bounded by $\varepsilon N$ over $N$ flags for a given $\varepsilon > 0$. Simultaneously, the number of tests performed by the algorithm is within a constant factor of the optimal algorithm for a variety of standard users. Further, our algorithm is very simple to implement. 3. We present experimental study of our algorithm that shows its performance on synthetic and data accumulated from a variety of negative feedback systems at Google to be more effective than out theoretical analysis above shows. Our model and approach here might initiate the study of a rich new class of problems for systematic understanding of negative feedback systems.
Document Recommendation in Social Tagging Services
Ziyu Guan, Can Wang, Kun Yang, Jiajun Bu, Chun Chen, Deng Cai
Social tagging services allow users to annotate various online resources with freely chosen keywords (tags). They not only facilitate the users in finding and organizing online resources, but also provide meaningful collaborative semantic data which can potentially be exploited by recommender systems. Traditional studies on recommender systems focused on user rating data, while recently social tagging data is becoming more and more prevalent. How to perform resource recommendation based on tagging data is an emerging research topic. In this paper we consider the problem of document (e.g. Web pages, research papers) recommendation using purely tagging data. That is, we only have data containing users, tags, documents and the relationships among them. We propose a novel graph-based representation learning algorithm for this purpose. The users, tags and documents are represented in the same semantic space in which two related objects are close to each other. For a given user, we recommend those documents that are sufficiently close to him/her. Experimental results on two data sets crawled from Del.icio.us and CiteULike show that our algorithm can generate promising recommendations and outperform traditional recommendation algorithms.
Measurement and Analysis of an Online Content Voting Network: A Case Study of Digg
Yingwu Zhu
In online content voting networks, aggregate user activities (e.g., submitting and rating content) makes high-quality content thrive through the unprecedented scale, high dynamics and divergent quality of user generated content (UGC). To better understand the nature and impact of online content voting networks, we have analyzed Digg, a popular online social news aggregator and rating website. Based on a large amount of data collected, we provide an in-depth study of Digg. We study structural properties of Digg social network, revealing some strikingly distinct properties such as low link symmetry and the power-law distribution of node outdegree with truncated tails. We explore impact of the social network on user digging activities, and investigate the issues of content promotion, content filtering, vote spam and content censorship, which are inherent to content rating networks. We also provide insight into design of content promotion algorithms and recommendation-assisted content discovery. Overall, we believe that the results presented in this paper are crucial in understanding online content rating networks.
.
