Algorithmic problems in social and geometric influence
Abstract/Contents
- Abstract
- Online social and information networks promise to yield insights into social relationships and also open possibilities for new market paradigms. Moving forward towards these goals requires addressing several new computational challenges, and in this thesis we explore two themes: algorithmic challenges arising due to the massive scale of online social networks, and questions related to social network monetization. In the first part of the thesis, we study the algorithmic problem of finding nearest neighbors that is computationally challenging due to the large scale and dynamic nature of social networks. In particular, we map the relationship discovery problem to a geometric proximity problem and undertake a theoretical study of algorithms needed for solving these proximity problems in the highly dynamic online setting. Our contributions are new data structures for resolving these proximity queries that can be updated dynamically for a changing point set. In the second part of the thesis, we study two problems relating to social network monetization. First, we propose a new monetization paradigm for social networks that works via a referral scheme to market a product on social networks. In particular, we show that computational limitations limit optimal implementations of such referral schemes, and propose an algorithm that leverages the social network topology to achieve revenue that is guaranteed to be within a constant factor of the optimal revenue. The second monetization problem we study is that of inferring the quality of an advertisement (or of generic content) given the knowledge of user clicks. Our contribution for this problem is to introduce a new online learning algorithm (i.e. an algorithm with no prior knowledge of content quality) that can account for the position bias that is inherent in the presentation of the content to users.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Copyright date | 2011 |
| Publication date | 2010, c2011; 2010 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Sharma, Aneesh |
|---|---|
| Associated with | Stanford University, Institute for Computational and Mathematical Engineering. |
| Primary advisor | Roughgarden, Tim |
| Thesis advisor | Roughgarden, Tim |
| Thesis advisor | Goel, Ashish |
| Thesis advisor | Kleinberg, Jon |
| Advisor | Goel, Ashish |
| Advisor | Kleinberg, Jon |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Aneesh Sharma. |
|---|---|
| Note | Submitted to the Institute for Computational and Mathematical Engineering. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2011. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2011 by Aneesh Sharma
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...