Discovering Roles In The Evolution Of Collaboration Networks

Abstract

Searching the Web involves more than sifting through a huge graph of pages and hyperlinks. Specific collaboration networks have emerged that serve domain-specific queries better by exploiting the principles and patterns that apply there. We continue this trend by suggesting heuristics and algorithms to mine the evolution of collaboration networks, to discover interesting roles played by entities. The first section of the dissertation introduces the concept of nurturers using the computer science research community as a case study, while the second section formulates three roles - scouts, promoters and connectors, played by ratings in collaborative filtering systems. Nurturers: Nurturing, a pervasive mammalian trait, naturally extends to most association networks that involve humans. The increased availability of digital and online data about associations lets researchers experiment with algorithms to gain insight into such phenomena. Consider some examples of nurturing: • Slashdot endorsement. Slashdot was not the first site to link to Firefox, but the publicity Firefox received from this association surely helped it become popular quickly. The phenomenon of many small websites crashing due to publicity received through Slashdot has become well known as the Slashdot Effect. • A VC (Venture Capitalist) seed-funding a new startup. This event has a high nurturing value if the startup’s valuation increases rapidly after the funding. • A blogger writing about a topic. Kim Cameron has nurtured the “Laws of Identity” topic if it later becomes the buzz in blog circles. A nurturer need not always be the innovator or originator. The evangelist who adopts a prodigal idea and launches it on its way to success can also be a nurturer. • A professor guiding his student through the art of scientific research and bootstrapping him into a vibrant research community. New nodes not only emerge around these nurturers, but also become important in the network. Knowing nurturers is useful especially in vertical search, where algorithms exploit the structure of specialized collaboration networks to make search more relevant: knowing early adopters of good web pages can make web-search fresher; a list of VCs ranked by their nurturing value is useful to people with new startup ideas; the list of top nurturers in computer science is a valuable resource for a student seeking to do research. This dissertation presents a framework for discovering nurturers by mining the evolution of an association network, and discusses heuristics and customizations that can be applied through a case study: finding the Best Nurturers in Computer Science Research. Roles of Ratings in Collaborative Filtering: Recommender systems aggregate individual user ratings into predictions of products or services that might interest visitors. The quality of this aggregation process crucially affects user experience and hence the effectiveness of recommenders in e-commerce. The dissertation presents a novel study that disaggregates global recommender performance metrics into contributions made by each individual rating, allowing us to characterize the many roles played by ratings in nearest neighbor collaborative filtering. In particular, we formulate three roles - scouts, promoters, and connectors that capture how users receive recommendations, how items get recommended, and how ratings of these two types are themselves connected (respectively). These roles find direct uses in improving recommendations for users, in better targeting of items, and most impor -tantly, in helping monitor the health of the system as a whole. For instance, they can be used to track the evolution of neighborhoods, to identify rating subspaces that do not contribute (or contribute negatively) to system performance, to enumerate users who are in danger of leaving, and to assess the susceptibility of the System to attacks such as shilling. The three rating roles presented here provide broad primitives to manage a recommender system and its community.