http://www.hpl.hp.com/personal/Thomas_Sandholm/sandholm2009a.pdf How to run parallel jobs more efficiently in a multi-user cluster We present a system for allocating resources in shared data and compute clusters that improves MapReduce job scheduling in three ways. First, the system uses regulated and user-assigned priorities to offer different service levels to jobs and users over time. Second, the system dynamically adjusts resource allocations to fit the requirements of different job stages. Finally, the system automatically detects and eliminates bottlenecks within a job. We show experimentally using real applications that users can optimize not only job execution time but also the cost-benefit ratio or prioritization efficiency of a job using these three strategies. Our approach relies on a proportional share mechanism that continuously allocates virtual machine resources. Our experimental results show a 11-31% improvement in completion time and 4-187% improvement in prioritization efficiency for different classes of MapReduce jobs. We further show that delay intolerant users gain even more from our system. Thomas Sandholm and Kevin Lai 2009-06-23 09:26:00 tycoon mapreduce http://www.hpl.hp.com/research/scl/papers/feedbacks/feedbacks.pdf Why does the distribution of user contributions obey a power law? A significant percentage of online content is now published and consumed via the mechanism of crowdsourcing. While any user can contribute to these forums, a disproportionately large percentage of the content is submitted by very active and devoted users, whose continuing participation is key to the sites’ success. As we show, people’s propensity to keep participating increases the more they contribute, suggesting motivating factors which increase over time. This paper demonstrates that submitters who stop receiving attention tend to stop contributing, while prolific contributors attract an ever increasing number of followers and their attention in a feedback loop. We demonstrate that this mechanism leads to the observed power law in the number of contributions per user and support our assertions by an analysis of hundreds of millions of contributions to top content sharing websites Digg.com and Youtube.com. Fang Wu, Dennis M. Wilkinson and Bernardo Huberman 2009-05-04 23:13:00 attention social media crowdsourcing http://www.hpl.hp.com/research/scl/papers/friendlee/friendlee.pdf Generating the networks that matter We have designed and implemented Friendlee, a mobile social networking application for close relationships. Friendlee analyzes the user’s call and messaging activity to form an intimate network of the user’s closest social contacts while providing ambient awareness of the user’ social network in a compelling, yet non-intrusive manner. To appear in Proceedings of the MobileHCI Conference 2009 Anupriya Ankolekar, Gabor Szabo, Yarun Luon, Bernardo A. Huberman, Dennis Wilkinson and Fang Wu 2009-04-30 17:50:00 social computing intimate networks mobility ambient awareness MobileHCI http://www.hpl.hp.com/research/scl/papers/bundles/bundles.pdf Clusters in social networks can help design customized bundles of products for consumers. Identifying consumer preferences is a key challenge in customizing electronic commerce sites to individual users. The increasing availability of online social networks provides one approach to this problem: people linked in these networks often share preferences, allowing inference of interest in products based on knowledge of a consumer's network neighbors and their interests. This paper evaluates the benefits of inference from online social networks in two contexts: a random graph model and a web site allowing people to both express preferences and form distinct social and preference links. We determine conditions on network topology and preference correlations leading to extended clusters of people with similar interests. Knowledge of when such clusters occur improves the usefulness of social network-based inference for identifying products likely to interest consumers based on information from a few people in the network. Such estimates could help sellers design customized bundles of products and improve combinatorial auctions for complementary products. To appear in Electronic Commerce Research and Applications special issue on Social Networks. Tad Hogg 2009-04-27 21:09:00 social networks electronic commerce essembly EC http://arxiv.org/abs/0709.4502 Reading part of a database without revealing what you're looking at. We describe a method for private database queries using exchange of quantum states with bits encoded in mutually incompatible bases. For technology with limited coherence time, the database vendor can announce the encoding after a suitable delay to allow the user to privately learn one of two items in the database without the ability to also definitely infer the second item. This quantum approach also allows the user to choose to learn other functions of the items, such as the exclusive-or of their bits, but not to gain more information than equivalent to learning one item, on average. This method is especially useful for items consisting of a few bits by avoiding the substantial overhead of conventional cryptographic approaches. Tad Hogg and Li Zhang 2009-04-08 19:45:00 quantum information privacy digital property rights http://arxiv.org/abs/0904.0016 Fans, the law of web surfing and users' interests combine to promote and rate stories on Digg. We describe a general stochastic processes-based approach to modeling user-contributory web sites, where users create, rate and share content. These models describe aggregate measures of activity and how they arise from simple models of individual users. This approach provides a tractable method to understand user activity on the web site and how this activity depends on web site design choices, especially the choice of what information about other users' behaviors is shown to each user. We illustrate this modeling approach in the context of user-created content on the news rating site Digg. (In Proc. of the 3rd Int'l AAAI Conference on Weblogs and Social Media) Tad Hogg and Kristina Lerman 2009-04-02 00:39:00 ICWSM digg social media social networks online content popularity http://www.hpl.hp.com/research/scl/papers/persistence/persistence.pdf How persistence does not lead to success A hallmark of the attention economy is the competition for the attention of others in information rich environments. Thus people persistently upload content to social media sites, hoping for the highly unlikely outcome of topping the charts and reaching a wide audience. And yet, an analysis of the production histories and success dynamics of 10 million videos from Youtube revealed that the more frequently an individual uploads content the less likely it is that it will reach a success threshold. This paradoxical result is further compounded by the fact that the average quality of submissions does increase with the number of uploads, and also that the likelihood success is less than that of playing a lottery. Fang Wu and Bernardo Huberman 2009-03-21 00:33:00 attention persistence success social computing lotteries youtube http://www.hpl.hp.com/research/scl/papers/feedback Attention matters in motivating contributions to enterprise social media. But some types of attention matter more. Increasingly, large organizations are experimenting with internal social media (e.g., blogs, forums) as a platform for widespread distributed collaboration. Contributions to their counterparts outside the organization's firewall are driven by attention from strangers, in addition to sharing among friends. However, employees in a workplace under time pressures may be reluctant to participate and the audience for their contributions is comparatively smaller. Participation rates also vary widely from group to group. So what influences people to contribute in this environment? In this paper, we present the results of a year-long empirical study of internal social media participation at a large technology company, and analyze the impact attention, feedback, and managers and coworkers participation have on employees behavior. We find feedback in the form of posted comments is highly correlated with a users subsequent participation. Recent manager and coworker activity relate to users initiating or resuming participation in social media. These findings extend, to an aggregate level, the results from prior interviews about blogging at the company and offer design and policy implications for organizations seeking to encourage social media adoption. To appear at GROUP 2009. Michael J. Brzozowski, Thomas Sandholm, and Tad Hogg 2009-03-18 00:00:00 blogs social media hp attention participation GROUP http://www.hpl.hp.com/research/scl/papers/watercooler/group2009 Cross-referencing enterprise social media with an enterprise directory can increase inter-group communication. As organizations scale up, their collective knowledge increases, and the potential for serendipitous collaboration between members grows dramatically. However, finding people with the right expertise or interests becomes much more difficult. Semi-structured social media, such as blogs, forums, and bookmarking, present a viable platform for collaboration--if enough people participate, and if shared content is easily findable. Within the trusted confines of an organization, users can trade anonymity for a rich identity that carries information about their role, location, and position in its hierarchy. This paper describes WaterCooler, a tool that aggregates shared internal social media and cross-references it with an organization's directory. We deployed WaterCooler in a large global enterprise and present the results of a preliminary user study. Despite the lack of complete social networking affordances, we find that WaterCooler changed users' perceptions of their workplace, made them feel more connected to each other and the company, and redistributed users' attention outside their own business groups. To appear at GROUP 2009. Michael J. Brzozowski 2009-03-17 00:00:00 blogs social media hp watercooler attention GROUP http://www.hpl.hp.com/research/scl/papers/blogging/chi2009 How do you get people to blog at work? blogs attention social media participation CHI The attention economy motivates participation in peer-produced sites on the Web like YouTube and Wikipedia. However, this economy appears to break down at work. We studied a large internal corporate blogging community using log files and interviews and found that employees expected to receive attention when they contributed to blogs, but these expectations often went unmet. Like in the external blogosphere, a few people received most of the attention, and many people received little or none. Employees expressed frustration if they invested time and received little or no perceived return on investment. While many corporations are looking to adopt Web-based communication tools like blogs, wikis, and forums, these efforts will fail unless employees are motivated to participate and contribute content. We identify where the attention economy breaks down in a corporate blog community and suggest mechanisms for improvement. To appear at CHI 2009. Sarita Yardi, Scott A. Golder, and Michael J. Brzozowski 2009-01-20 16:33:00 http://www.hpl.hp.com/research/scl/papers/twitter the social network that matters is not the one you declare. attention twitter social networks social media First Monday Scholars, advertisers and political activists see massive online social networks as a representation of social interactions that can be used to study the propagation of ideas, social bond dynamics and viral marketing, among others. But the linked structures of social networks do not reveal actual interactions among people. Scarcity of attention and the daily rhythms of life and work makes people default to interacting with those few that matter and that reciprocate their attention. A study of social interactions within Twitter reveals that the driver of usage is a sparse and hidden network of connections underlying the declared set of friends and followers. Bernardo A. Huberman, Daniel M. Romero and Fang Wu 2008-12-05 15:27:00 http://www.hpl.hp.com/research/scl/papers/predictions popularity, youtube, digg, attention, predicting future downloads. attention youtube popularity social media prediction online content We present a method for accurately predicting the long time popularity of online content from early measurements of user access. Using two content sharing portals, Youtube and Digg, we show that by modeling the accrual of views and votes on content offered by these services we can predict the long-term dynamics of individual submissions from initial data. In the case of Digg, measuring access to given stories during the first two hours allows us to forecast their popularity 30 days ahead with remarkable accuracy, while downloads of Youtube videos need to be followed for 10 days to attain the same performance. The differing time scales of the predictions are shown to be due to differences in how content is consumed on the two portals: Digg stories quickly become outdated, while Youtube videos are still found long after they are initially submitted to the portal. We show that predictions are more accurate for submissions for which attention decays quickly, whereas predictions for evergreen content will be prone to larger errors. Gabor Szabo and Bernardo A. Huberman 2008-11-03 15:27:00 http://www.hpl.hp.com/research/scl/papers/watercooler Visibility, attention, and recognition drive participation in internal corporate social media. watercooler blogs attention social media hp CSCW Blogs, wikis, and forums can break down geographic distances, workgroup boundaries, and organizational hierarchy in an organization. While these tools significantly lower the barriers to producing content, employees may perceive there to be little incentive to invest their own time in providing this content for public consumption. We found that increasing visibility often motivated employees to participate and contribute content. Employees were motivated by the opportunity for attention, and the ways in which social media tools enabled or hindered this opportunity influenced the way it was used. In this paper, we describe the design and use of the internal social media platforms at Hewlett-Packard and examine the ways that employees used these tools. Specifically, we explore ways in which designing for increased visibility and providing opportunities for recognition improve the ways that social media platforms can be used in organizations. To appear at CSCW 2008 Workshop on Enterprise 3.0. Michael J. Brzozowski and Sarita Yardi 2008-10-13 15:27:00 http://www.hpl.hp.com/research/scl/papers/blogging/ Participation in internal corporate blogs is both work-related and social, indicating a desire to connect with coworkers on multiple levels. blogs community temporal patterns hp CSCW Blogging at work has gained considerable interest in the knowledge management community. It is not clear, however, how much of work blogging is work-related versus social, or when work blogging takes place. In this poster, we present results from our examination of the temporal aspects of blogging within a large internal corporate blogging community. We compared our findings to similar analyses of employee email use and to college student Facebook use. We found that blog posting is temporally similar to email, while blog reading is more similar to Facebook messaging. Our results suggest that participation is both work-related and social, indicating a desire to connect to coworkers at multiple levels. To appear at CSCW 2008. Sarita Yardi, Scott Golder, and Michael J. Brzozowski 2008-10-13 15:15:00 http://www.hpl.hp.com/research/scl/papers/sncf/ User-generated social networking links can be as predictive as algorithmically identified "neighbors" in recommender systems. collaborative filtering social networks prediction recommender systems essembly This paper demonstrates that "social network collaborative filtering" (SNCF), wherein user-selected like-minded alters are used to make predictions, can rival traditional user-to-user collaborative filtering (CF) in predictive accuracy. Using a unique data set from an online community where users rated items and also created social networking links specifically intended to represent like-minded allies, we use SNCF and traditional CF to predict ratings by networked users. We find that SNCF using generic "friend" alters is moderately worse than the better CF techniques, but outperforms benchmarks such as by-item or by-user average rating; generic friends often are not like-minded. However, SNCF using "ally" alters is competitive with CF. These results are significant because SNCF is tremendously more computationally efficient than traditional user-user CF and may be implemented in large-scale web commerce and social networking communities. It is notoriously difficult to distinguish the contributions of social influence (where allies influence users) and social selection (where users are simply effective at selecting like-minded people as their allies). Nonetheless, comparing similarity over time, we do show no evidence of strong social influence among allies or friends. Rong Zheng, Dennis M. Wilkinson and Foster Provost 2008-10-06 12:00:00 http://www.hpl.hp.com/research/scl/papers/crowd/crowd.pdf How to solve the digital commons dilemma. attention social networks reputation crowdsourcing The tragedy of the digital commons does not seem to prevent the copious voluntary production of content that one witnesses in the web. We show through an analysis of a massive data set from Youtube that the productivity exhibited in crowdsourcing exhibits a strong positive dependence on attention, measured by the number of downloads. Conversely, a lack of attention leads to a decrease in the number of videos uploaded and the consequent drop in productivity, which in many cases asymptotes to no uploads whatsoever. Moreover, we observed that uploaders compare themselves to others when having low productivity and to themselves when exceeding a personal threshold. Bernardo A. Huberman, Daniel M. Romero and Fang Wu 2008-09-11 12:00:00 http://www.hpl.hp.com/research/scl/papers/howopinions/wine.pdf How web discourse evolves. To appear in the Proceedings of the Workshop on Internet and Network Economics-2008 opinion formation social networks polarization crowdsourcing WINE No aspect of the massive participation in content creation that the web enables is more evident than in the countless number of opinions, news and product reviews that are constantly posted on the Internet. Given their importance we have analyzed their temporal evo- lution in a number of scenarios. We have found that while ignorance of previous views leads to a uniform sampling of the range of opinions among a community, exposure of previous opinions to potential review- ers induces a trend following process which leads to the expression of increasingly extreme views. Moreover, when the expression of an opinion is costly and previous views are known, a selection bias softens the ex- treme views, as people exhibit a tendency to speak out differently from previous opinions. These findings are not only robust but also suggest simple procedures to extract given types of opinions from the population at large. Fang Wu and Bernardo A. Huberman 2008-09-11 12:00:00 http://www.hpl.hp.com/research/scl/papers/reputationExpt/reputation-expts-and-Prosper.pdf How people use reputation information. reputation incentive design experimental economics We evaluated how people use reputation in a laboratory market and in Prosper, an online microfinance business. We found people use information on past behavior to ostracize previous poor performance in both cases. The laboratory market did not show significant price discrimination, but people used their ability to not fulfill contracts to punish poor performers. Price discrimination was significantly correlated with reputation in Prosper. Thus we find people apply multiple strategies to deal with reputation. Kay-Yut Chen, Scott Golder, Tad Hogg and Cecilia Zenteno 2008-08-19 12:00:00 http://arxiv.org/abs/0707.4195 How people perform in an auction using simulated quantum information processing. quantum information incentive design experimental economics We describe human-subject laboratory experiments on probabilistic auctions based on previously proposed auction protocols involving the simulated manipulation and communication of quantum states. These auctions are probabilistic in determining which bidder wins, or having no winner, rather than always having the highest bidder win. Comparing two quantum protocols in the context of first-price sealed bid auctions, we find the one predicted to be superior by game theory also performs better experimentally. We also compare with a conventional first price auction, which gives higher performance. Thus to provide benefits, the quantum protocol requires more complex economic scenarios such as maintaining privacy of bids over a series of related auctions or involving allocative externalities. Kay-Yut Chen and Tad Hogg 2008-08-19 12:00:00 http://arxiv.org/abs/0704.0800 A privacy-preserving auction using quantum information processing. quantum information incentive design game theory economics We present a quantum auction protocol using superpositions to represent bids and distributed search to identify the winner(s). Measuring the final quantum state gives the auction outcome while simultaneously destroying the superposition. Thus non-winning bids are never revealed. Participants can use entanglement to arrange for correlations among their bids, with the assurance that this entanglement is not observable by others. The protocol is useful for information hiding applications, such as partnership bidding with allocative externality or concerns about revealing bidding preferences. The protocol applies to a variety of auction types, e.g., first or second price, and to auctions involving either a single item or arbitrary bundles of items (i.e., combinatorial auctions). We analyze the game-theoretical behavior of the quantum protocol for the simple case of a sealed-bid quantum, and show how a suitably designed adiabatic sear h reduces the possibilities for bidders to game the auction. This design illustrates how incentive rather that computational constraints affect quantum algorithm choices. Tad Hogg, Pavithra Harsha and Kay-Yut Chen 2008-08-19 12:00:00 http://www.hpl.hp.com/personal/Thomas_Sandholm/sandholm2008a.pdf Tradeoffs between using spot and reservation markets. tycoon incentive design resource allocation markets We propose, implement and evaluate three admission models for computational Grids. The models take the expected demand into account and offer a specific performance guarantee. The main issue addressed is how users and providers should make the tradeoff between a best effort (low guarantee) spot market and an admission controlled (high guarantee) reservation market. Using a realistically modeled high performance computing workload and utility models of user preferences, we run experiments highlighting the conditions under which different markets and admission models are efficient. The experimental results show that providers can make large efficiency gains if the admission model is chosen dynamically based on the current load, likewise we show that users have an opportunity to optimize their job performance by carefully picking the right market based on the state of t e system, and the characteristics of the application to be run. Finally, we provide simple functional expressions that can guide both users and providers when making decisions about guarantee levels to request or offer. Thomas Sandholm, Kevin Lai, and Scott Clearwater 2008-06-06 12:00:00 http://www.hpl.hp.com/research/idl/papers/opinion_expression/ How opinions evolve online. We performed a massive study of the dynamics of group delibera- tion among several websites containing millions of opinions on topics ranging from books to media. Contrary to the common phenomenon of group polarization observed offline, we measured a strong tendency towards moderate views in the course of time. This phenomenon possi- bly operates through a self-selection bias whereby previous comments and ratings elicit contrarian views that soften the previous opinions. Fang Wu and Bernardo A. Huberman 2008-05-15 17:00:00 ratings opinion formation polarization reviews Dennis M. Wilkinson 2008-04-10 00:00:00 social networks attention opinion formation Online peer production systems have enabled people to coactively create, share, classify, and rate content on an unprecedented scale. This paper describes strong macroscopic regularities in how people contribute to peer production systems, and shows how these regularities arise from simple dynamical rules. First, it is demonstrated that the probability a person stops contributing varies inversely with the number of contributions he has made. This rule leads to a power law distribution for the number of contributions per person in which a small number of very active users make most of the contributions. The rule also implies that the power law exponent is proportional to the effort required to contribute, as justified by the data. Second, the level of activity per topic is shown to follow a lognormal distribution generated by a stochastic reinfo cement mechanism. A small number of very popular topics thus accumulate the vast majority of contributions. These trends are demonstrated to hold across hundreds of millions of contributions to four disparate peer production systems of differing scope, interface style, and purpose. Simple behavioral rules hold across hundreds of millions of contributions to disparate online peer production efforts. http://www.hpl.hp.com/research/scl/papers/regularities/ Scott A. Golder 2008-04-09 00:00:00 The ease and lack of cost associated with taking digital photographs have allowed people to amass large personal photograph collections. These collections contain valuable information about their owners' social relationships. This paper is a preliminary investigation into how digital photo collections can provide useful data for the study of social networks. Results from an analysis of 23 subjects photo collections demonstrate the feasibility of this approach. The relationship between perceived closeness and network position, as well as future questions, are also discussed. Digital photo archives contain valuable information about individuals' social networks. social networks photos HT http://www.hpl.hp.com/research/scl/papers/sna-photos/ Tad Hogg and Gabor Szabo 2008-03-25 0:00:00 Web sites where users create and rate content as well as form networks with other users display long-tailed distributions in many aspects of behavior. Using behavior on one such community site, Essembly, we propose and evaluate plausible mechanisms to explain these behaviors. Unlike purely descriptive models, these mechanisms rely on user behaviors based on information available locally to each user. For Essembly, we find the long-tails arise from large differences among user activity rates and qualities of the rated content, as well as the extensive variability in the time users devote to the site. We show that the models not only explain overall behavior but also allow estimating the quality of content from their early behaviors. http://www.hpl.hp.com/research/idl/papers/diversity/ Diversity among users and the content they create in the Essembly web site. social networks essembly Fang Wu and Bernardo A. Huberman 2008-01-24 0:00:00 We analyze the role that popularity and novelty play in attracting the attention of users to dynamic websites. We do so by determining the performance of three different strategies that can be utilized to maximize attention. The first one prioritizes novelty while the second emphasizes popularity. A third strategy looks myopically into the future and prioritizes stories that are expected to generate the most clicks within the next few minutes. We show that the first two strategies should be selected on the basis of the rate of novelty decay, while the third strategy performs sub-optimally in most cases. We also demonstrate that the relative performance of the first two strategies as a function of the rate of novelty decay changes abruptly around a critical value, resembling a phase transition in the physical world. http://www.hpl.hp.com/research/idl/papers/popularity/popularity.pdf Whether to use popularity or novelty to elicit attention attention Tad Hogg, Gabor Szabo, Dennis M. Wilkinson, and Michael J. Brzozowski 2008-01-12 0:00:00 Traditionally, online social network sites like Facebook and MySpace allow people to form links to "friends" but do little to qualify the semantic meaning of the friendship. As a result, many users "collect" friends on these sites, conflating "acquaintances" with "friends". Essembly, a "fiercely non-partisan social network", on the other hand, lets its users enrich the meaning of their relations to others by explicitly labeling them "friends", "allies", or "nemeses". Essembly then allows its members to post resolves reflecting controversial opinions on political issues. As a defining activity on the site, members can vote on these resolves on a four-point scale ranging from complete agreement to full opposition. We examined how the uncommon link semantics affects users in casting their votes. In particular, Essembly prominently highlights the activities of users' acquaintances, and the question arises if this makes them more likely to participate, and if so, how this information affects votes. It is widely assumed that social networks enhance, if not drive, the popularity of online services; what does an additional layer of link classification add to them? Papers appeared at CHI 2008 and AAAI Spring Symposium on Social Information Processing 2008. http://www.hpl.hp.com/research/idl/papers/essembly Examines the usefulness of distinguishing between friends and similar/dissimilar users in propagating new content in an online social network, and suggests resulting design implications for social content aggregation services and recommender systems. social networks voting essembly influence CHI http://www.hpl.hp.com/personal/Thomas_Sandholm/sandholm2007a.pdf Applying Occam's razor to statistics to enable risk preference multiplexing. We study stochastic models to mitigate the risk of poor Quality-of-Service (QoS) in computational markets. Consumers who purchase services expect both price and performance guarantees. They need to predict future demand to budget for sustained performance despite price fluctuations. Conversely, providers need to estimate demand to price future usage. The skewed and bursty nature of demand in large-scale computer networks challenges the common statistical assumptions of symmetry, independence, and stationarity. This discrepancy leads to underestimation of investment risk. We confirm this non-normal distribution behavior in our study of demand in computational markets. Thomas Sandholm and Kevin Lai 2007-07-12 14:08:00 tycoon risk qos http://www.hpl.hp.com/research/idl/papers/agency/ Solving moral hazard and information asymmetry in the enterprise. We study the agency problem experimentally focusing on two issues that are central to its effectiveness. The first tests whether an incentive compatible direct revelation mechanism performs well when human agents are asked to report probabilistic information. The second addresses the principal's lack of knowledge as to how effort levels relate to the final outcome. Our results reveal several behavioral effects that reduce the efficiency of the principal-agent mechanism. We find out that human agents underestimate low probabilities and overestimate high probabilities, introducing errors into what should be a truth-telling me hanism. Furthermore, principals were observed to underpay their agents by substantial amounts. These behavioral issues may explain why contracts designed through standard principal-agent models are seldom used in practice. Kay-Yut Chen, Bernardo A. Huberman and Basak Kalkanci 2007-07-05 10:30:00 http://www.hpl.hp.com/research/idl/papers/novelty/index.html How does novelty affect the attention of large groups The subject of collective attention is central to an information age where millions of people are inundated with daily messages. It is thus of interest to understand how attention to novel items propagates and eventually fades among large populations. We have analyzed the dynamics of collective attention among one million users of an interactive website -digg.com- devoted to thousands of novel news stories. The observations can be described by a dynamical model characterized by a single novelty factor. Our measurements indicate that novelty within groups decays with a stretched-exponential law, suggesting the existence of a natural time scale over which attention fades within large groups. Fang Wu and Bernardo A. Huberman 2007-03-26 10:00:00 attention http://www.hpl.hp.com/personal/ i_Zhang/papers/p2m-c.pdf Simple dynamics may lead to sophisticated equilibrium markets One of the main reasons of the recent success of peer to peer (P2P) file sharing systems such as BitTorrent is its built-in tit-for-tat mechanism. In this paper, we model the bandwidth allocation in a P2P system as an exchange economy and study a tit-for-tat dynamics, namely the proportional response dynamics, in this economy. In a proportional response dynamics each player distributes its good to its neighbors proportional to the utility it received from them in the last period. We show that this dynamics not only converges but converges to a market equilibrium, a standard economic characterization of efficient exchanges in a competitive market. In addition, for some classes of utility functions we consider, it converges much faster than the classical tatonnement process and any existing algorithms for computing market equilibria. Fang Wu and Li Zhang 2007-03-02 http://www.hpl.hp.com/research/idl/papers/wikipedia/index.html How good is wikipedia? Since its inception six years ago, the online encyclopedia Wikipedia has accumulated 6.40 million articles and 250 million edits contributed in a predominantly undirected and haphazard fashion by 5.77 million unvetted contributors. Since it is not obvious that this kind of large-scale, voluntary effort can produce good results, we measured the correlation between the 50 million edits in the English-language Wikipedia and the quality of its 1.5 million articles. We found that article quality is indeed correlated with both number of edits and number of distinct editors. An analysis of editing patterns shows a heavy-tailed distribution of articles, in which relatively few articles having disproportionally high numbers of edits and editors end up at the forefront in terms of quality and visibility. Dennis M. Wilkinson and Bernardo A. Huberman wikipedia cooperation WikiSym 2007-02-15 10:00:00 http://www.hpl.hp.com/research/idl/papers/keywordAuction/index.html How to bid in a continuous-time auction? markets This paper models continuous-time mass bidding markets, such as keyword auctions and market-based resource allocation systems, as a stochastic dynamic system that fluctuates around an average value under the influence of its users. The user's objective to maximize his long-term average utility is formulated as a stochastic control problem. The optimal bidding strategy is calculated both analytically and numerically. It is shown that market fluctuations tend to decrease expected system revenue, thus search engines like Google and Yahoo has an incentive to create a secondary stable market such as a futures market or a reservation market. Fang Wu 2007-02-15 10:00:00 http://www.hpl.hp.com/research/idl/papers/facebook/index.html There are strong temporal patterns of communication among the millions of people interacting through Facebook. We have analyzed the fully anonymized headers of 362 million messages exchanged by 4.2 million users of Facebook, an online social network of college students, during a 26 month interval. The data reveal a number of strong daily and weekly regularities which provide insights into the time use of college studen s and their social lives, including seasonal variations. We also examined how factors such as school affiliation and informal online "friend" lists affect the observed behavior and temporal patterns. Finally, we show that Facebook users appear to be clustered by school with respect to their temporal messaging patterns. Full citation: Scott A. Golder, Dennis Wilkinson and Bernardo A. Huberman. "Rhythms of Social Interaction: Messaging within a Massive Online Network" 3rd International Conference on Communities and Technologies (CT2007). East Lansing, MI. June 28-30, 2007. Scott Golder, Dennis Wilkinson and Bernardo A. Huberman CT facebook social networks temporal patterns 2007-01-26 01:50:00 http://www.hpl.hp.com/research/idl/papers/advantage/index.html Comparative advantage in the attention economy can be used to maximize the revenues a company gets from advertising. We analyze the problem that enterprises face when having to decide on the most effective way to advertise several items belonging to their inventories within the company's webpages. We show that the ability to arbitrarily partition a website among items leads to a comparative advantage among webpages which can be exploited so as to maximize the total utility of the enterprise. This result, which also applies to the case of several competitive providers, is then extended to dynamical scenarios where both the advertising allocation and the exposure levels vary with time. Bernardo A. Huberman and Fang Wu 2007-01-26 01:49:00 http://www.hpl.hp.com/research/idl/papers/microSensorsPassive/index.html Detecting microscopic chemical sources with molecular electronic devices. Molecular electronics and nanoscale chemical sensors could enable constructing microscopic sensors capable of detecting patterns of chemicals in a fluid. Information from a large number of such devices flowing passively in the bloodstream allows estimating properties of tiny chemical sources in a macroscopic ti sue volume. We use estimates of plausible device capabilities to evaluate their performance for typical chemicals released into the blood by tissues in response to localized injury or infection. We find the devices can readily discriminate a single cell-sized chemical source from the background chemical concentration, providing high-resolution sensing in both time and space. By contrast, such a chemical source would be difficult to distinguish from background when diluted throughout the blood volume as obtained with a blood sample. (appeared in Nanomedicine: Nanotechnology, Biology, and Medicine) Tad Hogg and Philip J. Kuekes 2007-01-26 01:48:00 http://www.hpl.hp.com/research/idl/papers/attention/index.html Deciding what to display. We introduce an automatic configuration mechanism that generates the most relevant information to be presented to limited attention users of information-rich media. It also guarantees to maximize their total expected utility from the information they receive. A computationally efficient algorithm is used to assign an index value to each information item, which then determines whether or not a given item appears in the top list presented to users at a given time. Bernardo A. Huberman and Fang Wu 2007-01-26 01:47:00 attention http://www.hpl.hp.com/research/idl/papers/p2p/index.html How to provide any content over the web while avoiding free riding. We describe an efficient incentive mechanism for P2P systems that generates a wide diversity of content offerings while responding adaptively to customer demand. Files are served and paid for through a parimutuel market similar to that commonly used for betting in horse races. An analysis of the performance of such a system shows that there exists an equilibrium with a long tail in the distribution of content offerings, which guarantees the real time provision of any content regardless of its popularity. full citation: "Bootstrapping the Long Tail in Peer to Peer Systems", B. A. Huberman and F. Wu. First Workshop on the Economics of Networked Systems (NetEcon06), ACM Conference on Electronic Commerce, 56-61 (2006) Bernardo A. Huberman and Fang Wu 2007-01-26 01:46:00 http://www.hpl.hp.com/research/idl/papers/trust/index.html Making providers and users reveal their true intentions. reservations We describe a pricing structure for the provision of IT services that ensures trust without requiring repeated interactions between service providers and users. It does so by offering a pricing structure that elicits truthful reporting of quality of service (QoS) by providers while making them profitable. This mechanism also induces truth-telling on the part of users reserving the service. Bernardo A. Huberman, Fang Wu and Li Zhang 2007-01-26 01:45:00 http://www.hpl.hp.com/research/idl/papers/viral/viral.pdf How effective is viral marketing? We present an analysis of a person-to-person recommendation network, consisting of 4 million people who made 16 million recommendations on half a million products. We observe the propagation of recommendations and the cascade sizes, which we explain by a simple stochastic model. We analyze how use behavior varies within user communities defined by a recommendation network. Product purchases follow a 'long tail' where a significant share of purchases belongs to rarely sold items. We establish how the recommendation network grows over time and how effective it is from the viewpoint of the sender and receiver of the recommendations. While on average recommendations are not very effective at inducing purchases and do not spread very far, we present a model that successfully identifies communities, product and pricing categories for which viral marketing seems to be very effective. Jure Leskovec, Lada A. Adamic and Bernardo A. Huberman 2007-01-26 01:44:00 http://www.hpl.hp.com/research/idl/papers/tags/index.html There are patterns to collaboration. Collaborative tagging describes the process by which many users add metadata in the form of keywords to shared content. Recently, collaborative tagging has grown in popularity on the web, on sites that allow users to tag bookmarks, photographs and other content. In this paper we analyze the structure of collaborative tagging systems as well as their dynamical aspects. Specifically, we discovered regularities in user activity, tag frequencies, kinds of tags used, bursts of popularity in bookmarking and a remarkable stability in the relative proportions of tags within a given url. We also present a dynamical model of collaborative tagging that predicts these stable patterns and relates them to imitation and shared knowledge. Full citation: Scott Golder and Bernardo A. Huberman. (2006). "Usage Patterns of Collaborative Tagging Systems." Journal of Information Science, 32(2). 198-208. Scott Golder and Bernardo A. Huberman 2007-01-26 01:43:00 http://www.hpl.hp.com/research/idl/papers/reservations/reservation.pdf Expressing the true likelihood of using a reserved resource. reservations We present a mechanism for reservations of bursty resources that is both truthful and robust. It consists of option contracts whose pricing structure induces users to reveal the true likelihoods that they will purchase a given resource. Users are also allowed to adjust their options as their likelihood changes. This scheme helps users save cost and the providers to plan ahead so as to reduce the risk of under-utilization and overbooking. The mechanism extracts revenue similar to that of a monopoly provider practicing temporal pricing discrimination with a user population whose preference distribution is known in advance. Fang Wu, Li Zhang, and Bernardo A. Huberman 2007-01-26 01:42:00 http://www.hpl.hp.com/research/idl/papers/insurance/index.html How to transform risk averse managers into risk neutral ones risk We present a new mechanism for encouraging risk taking within organizations that relies on the provision of decision insurance to managers. Since insurance increases the likelihood of free riding, we also introduce a technique that mitigates this moral hazard by automatically identifying the social network around the manager and using it as a monitoring group. We show that three possible regimes exist. In the first one, managers contribute to production but avoid risky projects. In the second, managers take on risky projects without free riding. In the third, they free ride. We establish the conditions for the appearance of each of these regimes and show how to adjust the mech nism parameters so as to get the highest expected payoff for the firm in spite of its risk-adverse managers. Tad Hogg and Bernardo A. Huberman 2007-01-26 01:41:00 http://www.hpl.hp.com/research/idl/papers/microSensors/index.html Distributed control of molecular electronic computers and chemical sensors. (click link to view abstract) Tad Hogg 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/qpdilemma/index.html People can effectively use quantum entanglement to reduce free riding. quantum information game theory experimental economics (click link to view abstract) Kay-Yut Chen and Tad Hogg 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/nerveRepair/index.html Distributed control of small robots can improve microsurgery. (click link to view abstract) Tad Hogg and David W. Sretavan 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/fads/fads.pdf What makes fads come and go? (click link to view abstract) Jonathan Bendor, Bernardo A. Huberman and Fang Wu 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/tycoon/tycoon-ec.pdf How efficient and fair is Tycoon? game theory (click link to view abstract) Michal Feldman, Kevin Lai, and Li Zhang 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/tycoon/tycoon-icalp.pdf Can we prove something about Tycoon? game theory (click link to view abstract) Li Zhang 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/swings (click link to view abstract) Scott Clearwater and Bernardo A. Huberman reservations 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/tycoon/index.html (click link to view abstract) Kevin Lai, Lars Rasmusson, Eytan Adar, Stephen Sorkin, Li Zhang and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/wireless/glider-c.pdf How to do geometric routing without geometry (click link to view abstract) Qing Fang, Jie Gao Leonidas Guibas, Vin de Silva, and Li Zhang 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/opinions/index.html How do opinions form? (click link to view abstract) Fang Wu and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/sunk/index.html Do sunk costs affect decisions? (click link to view abstract) Daniel Friedman, Kai Pommerenke, Rajan Lukose, Garret Milam and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/queues/index.html To wait or not to wait; that is the question (click link to view abstract) Li Zhang, Fang Wu and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/experiment/index.html How people deal with Internet delays (click link to view abstract) Dan Friedman and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/reputationExpt/index.html Revealing past behavior improves market efficiency reputation experimental economics (click link to view abstract) Kay-Yut Chen, Tad Hogg and Nathan Wozny 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/molecularAdder/index.html Building an adder with molecular electronics in spite of defects (click link to view abstract) Tad Hogg and Greg Snider 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/molecularMultiplexer/index.html Providing input and output to molecular circuits (click link to view abstract) Tad Hogg, Yong Chen and Phil Kuekes 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/project/index.html How human nature affects complex design projects (click link to view abstract) Bernardo A. Huberman and Dennis M. Wilkinson 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/deviance/index.html The price of secrets (click link to view abstract) Bernardo A. Huberman, Eytan Adar and Leslie R. Fine 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/blogs/index.html (click link to view abstract) Eytan Adar, Li Zhang, Lada A. Adamic, and Rajan M. L kose 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/linear/index.html (click link to view abstract) Fang Wu and Bernardo Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/infodynamics/index.html (click link to view abstract) Bernardo A. Huberman, Lada A. Adamic 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/publicgoods/index.html Quantum information can help address public goods problems. quantum information game theory economics (click link to view abstract) Kay-Yut Chen, Tad Hogg and Raymond Beausoleil 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/coordination/index.html Entangled particles provide a coordination mechanism. quantum information game theory (click link to view abstract) Bernardo A. Huberman and Tad Hogg 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/flow/ (click link to view abstract) Fang Wu, Bernardo A. Huberman, Lada A. Adamic, Joshua R. Tyler 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/shock/ Discovering hidden knowledge within organizations by using profiles and peer-to-peer question routing. (click link to view abstract) Rajan M. Lukose, Eytan Adar, Joshua R. Tyler, and Caesar Sengupta 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/adiabatic/index.html An NMR quantum computer for combinatorial search. quantum information (click link to view abstract) M. Steffen, W. van Dam, T. Hogg, G. Breyta and I. Chuang 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/email/index.html How to reveal the hidden organization and its leaders. (click link to view abstract) Joshua R. Tyler, Dennis M. Wilkinson and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/reputations/index.html How reputations get established, grow and decay. (click link to view abstract) Bernardo A. Huberman and Fang Wu 2007-01-01 00:00:00 http://www.hpl.hp.com/rese rch/idl/papers/communities/index.html Finding functionally related genes from the literature. (click link to view abstract) Dennis M. Wilkinson and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/moral/index.html How to avoid killing the messenger while making him work hard. game theory (click link to view abstract) Tad Hogg and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/public/index.html Public information can seriously distort group predictions. (click link to view abstract) Kay-Yut Chen, Leslie R. Fine and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/genelit Another example of information aggregation. (click link to view abstract) Lada A. Adamic, Dennis M. Wilkinson, Bernardo A. Huberman, a d Eytan Adar 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/review A chapter review of search in scale free networks. (click link to view abstract) Lada A. Adamic, Rajan M. Lukose and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/autonomous/index.html An overview of the dynamics and control of large distributed systems. (click link to view abstract) Tad Hogg and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/privacy/index.html An alternative to trusted third parties. incentive design (click link to view abstract) Bernardo A. Huberman and Tad Hogg 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/future/index.html It is hard to predict anything, especially the future. (click link to view abstract) Kay-Yut Chen, Leslie R. Fine and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/status/index.html Why do we seek status? (click link to view abstract) Bernardo A. Huberman, Christoph Loch and Ayse Onculer 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/quantum/index.html Classical economics can help quantum computation. quantum information (click link to view abstract) Sebastian M. Maurer, Tad Hogg and Bernardo A. Huberma 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/mfs/index.html Economic incentives and privacy for user data. (click link to view abstract) Eytan Adar and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/plsearch/index.html How to navigate in peer-to-peer networks. (click link to view abstract) Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani, Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/auctions/index.html There is more to auctions than meets the eye. (click link to view abstract) Bernardo A. Huberman, Tad Hogg and Arun Swami 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/rings/index.html What to do when web rings become too large. (click link to view abstract) Sebastian M. Maurer, Bernardo A. Huberman and Eytan Adar 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/papers/gnutella/index.html Why copyright violation is the least of Gnutella's problems. (click link to view abstract) Eytan Adar and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/abstracts/ECommerce/winner.html Competitive dynamics on the web unfold in surprising ways, leading to a sudden transition to winner-take-all markets. (click link to view abstract) Sebastian M. Maurer and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/abstracts/ECommerce/econsurf.html Information providers can exploit the differences in surfing behavior exhibited by web users. (click link to view abstract) Eytan Adar and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/abstracts/ECommerce/multi.html What happens to congestion when many users use a clever restart strategy? (click link to view abstract) Sebastian M. Maurer and Bernardo A. Huberman 2007-01-01 00:00:00 http://www.hpl.hp.com/research/idl/abstracts/ECommerce/privacy.html How do you keep privacy while using reputations to select recommendations? incentive design (click link to view abstract) Bernardo A. Huberman, Matt Franklin and Tad Hogg 2007-01-01 00:00:00