Topics, References and Assignment

Topics

First Session: 22.6.

1. Evolution of social network models (I/II) – From random graphs to small worlds
   
   • Start with random graphs by Erdös and Renyi
   • Question by means of „six degress of separation“ and “Strength of weak ties”
   • Move to small-world theory by Watts and Strogatz
   • Literature:
     
     • Erdős, P. Rényi, A. (1959). "On Random Graphs I" in Publ. Math. Debrecen 6, p. 290–297
     • Mark S. Granovetter (1973). The strength of weak ties. The American Journal of Sociology
     • Watts, D.J., Strogatz, S.H. (1998). "Collective dynamics of 'small-world' networks" in Nature 393 (6684), p. 409–410
     • The Structure and Dynamics of Networks; Newman, Barabasi, and Watts; Princeton University Press, 2006
2. Evolution of social network models (II/II) – From small worlds to power-law distributions
   
   • What the model of Watts-Strogatz is still missing … power-law node distributions!
   • The evolutionary model of Barabasi-Albert: preferential attachment and “rich get richer”
   • Include analytical proof for power-law distribution as made by Barabasi
   • How to bring low diameter, power-law and high clustering coefficient into one model the Holme-Kim model
   • Literature:
     
     • Watts, D.J., Strogatz, S.H. (1998). "Collective dynamics of 'small-world' networks" in Nature 393 (6684), p. 409–410
     • Albert-László Barabási & Réka Albert (October 1999). "Emergence of scaling in random networks". Science 286 (5439): 509–512
     • The Structure and Dynamics of Networks; Newman, Barabasi, and Watts; Princeton University Press, 2006
     • Holme, P. and Kim, B.-J. (2002). “Growing scale-free networks with tunable clustering” in Physical Review E, Vol. 6
3. Applications of social network modelling: Disease spreading and modelling
   
   • Examples of SIR models and their application to HIV; what are the advantages of modelling diseases by considering network structure?
   • Going one step further with SIRS models
   • Analysis of the impact of clustering coefficients on the spread of diseases
   • Literature:
   • Networks, Crowds, and Markets: Reasoning about a Highly Connected World; David Easley and Jon Kleinberg; Cambridge University Press, 2010; http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch21.pdf
   • The Structure and Dynamics of Networks; Newman, Barabasi, and Watts; Princeton University Press, 2006
4. Using social network analysis to find out about the value of customers in marketing
   
   • Early efforts based on dominant eigenvector-based approaches such as Google’s Pagerank
   • The Domingos-Richardson model based on Markov random fields
   • Analysis of the impact of clustering coefficients on the spread of diseases
   • Literature:
     
     • Pedro Domingos and Matt Richardson. 2001. Mining the network value of customers. In Proceedings of KDD '01. ACM, New York, NY, USA, 57-66
     • Matthew Richardson and Pedro Domingos. 2002. Mining knowledge-sharing sites for viral marketing. In Proceedings of KDD '02. ACM, New York, NY, USA, 61-70
     • Hinrichs Harms. Customer Value Estimation Considering Social Network
       Relationships. Studienarbeit Universität Madgeburg, 2009.
5. Game Theory
   
   • Foundations of Games
   • Equilibria, Strategies
   • Literature:
     
     • Networks, Crowds, and Markets: Reasoning about a Highly Connected World; David Easley and Jon Kleinberg; Cambridge University Press, 2010; http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch06.pdf
     • Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani: "Algorithmic Game Theory", Cambridge University Press 2007: Chapter 1 http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf,
6. Auctions: Overview
   
   • Auctions are a major application of game theory with many real-world use cases
   • Provide an overview of various auction types
   • Literature:
   • Networks, Crowds, and Markets: Reasoning about a Highly Connected World; David Easley and Jon Kleinberg; Cambridge University Press, 2010; http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch09.pdf
7. So is it really ‘Six Degrees of Separation’? – Critique of Milgram’s experiment
   
   • Brief presentation of Milgram’s experiment to set the stage
   • Summarizing the points of critique of Kleinfeld, e.g., incomplete chains and questionable assumptions towards attrition
   • Completion rate and probability of “true” chain lengths by White (going into the mathematical details)
   • Goel's model for estimating "true" path lengths
   • Literature:
     
     • Milgram, S. (1967) "The Small World Problem" in Psychology Today, 1(1), p. 60 – 67
     • Kleinfeld, J. (2002). "Could it be a big world after all?" in Society 39, p. 61–66
       White, H. C. (1970). "Search parameters for the small-world problem" in Social Forces 49, p. 259–264
     • Goel, S., Muhamad, R., & Watts, D. J. (2009). "Social search in 'small-world' experiments." in Proceedings of the 18th International World Wide Web Conference, 701-710
     • The Structure and Dynamics of Networks; Newman, Barabasi, and Watts; Princeton University Press, 2006

Second Session: 29.6.

1.  Matching Markets
   
   • Combination of network structure and game theory
   • Find matches between sets of groups, people, etc.
   • Start with overview and from general model
   • Consider a classical application (labor markets) as well as an application in online advertising
   • Literature:
     
     • Networks, Crowds, and Markets: Reasoning about a Highly Connected World; David Easley and Jon Kleinberg; Cambridge University Press, 2010; http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch10.pdf
     • Matching Markets in Online Advertising Networks:The Tao of Taobao and the Sense of AdSense http://faculty.chicagobooth.edu/workshops/marketing/archive/pdf/Wu2011.pdf
     • Roth, A. E. "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory." Journal of Political Economy 92, no. 6 (December 1984): 991-1016. http://kuznets.fas.harvard.edu/~aroth/papers/evolut.pdf
2. Sponsored Search:
   
   • A significant part of online advertising is sold next to search results, aka “sponsored search”
   • Focus on the “auction” part as the underlying mechanism
   • Special focus on GSP: most popular auction model used in online advertising
   • Literature:
     
     • Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani: "Algorithmic Game Theory", Cambridge University Press 2007: Chapter 28 http://www.cambridge.org/journals/nisan/downloads/Nisan_Non-printable.pdf
     • B. Edelman, M. Ostrovsky, M. Schwarz: "Internet Advertising and the Generalized Second Price Auction: Selling Billions of Dollars Worth of Keywords".
3. Sponsored Search: Keyword Selection
   
   • An interesting challenge in sponsored search is the choice of suitable keywords: selective, relatively focused, not too expensive
   • Various approaches to suggest/improve keywords exist
   • Literature:
     
     • Generating Query Substitutions: Jones et al, in Proc of WWW 2006
     • Using the Wisdom of the Crowds for Keyword Generation: Fuxman et al., In proc of WWW 2004
     • Simrank++: Query Rewriting through Link Analysis of the Click Graph: Atoanellis et al., In proc of VLDB 2008
     • Learning Query Substitutions for Online Advertising: Broder et al. in Proc of ACM SIGIR 2008
4. Context-Based Ads
   
   • Another popular type of ads are determined by the contents of pages they are displayed in: aka “context-based ads”
   • Different techniques exist on establishing this context and to decide when to show which ad
   • Literature:
     
     • Finding Advertising Keywords on Web Pages. Wen-tau Yih et al. In Proc. of WWW 2006
     • Impedance coupling in content-targeted advertising. Ribero-Neto et al. In Proc of SIGIR 2005
     • A Semantic Approach to Contextual Advertising..Broder et al, In Proc. of SIGIR 2007
     • Contextual Advertising by Combining Relevance with Click Feedback. D. Chakrabarti et al. In Proc of WWW 2008
     • To Swing or not to Swing: Predicting when (not) to Advertise. Broder et al, CIKM 2008
5. Display Ads
   
   • Graphical Banner ads with different sales approaches
   • Guaranteed Delivery: Fixed target audience vs On-the-spot bidding
   • Optimization: Interesting allocation problems and strategies
   • Statistics: density estimations over large, heavily tailed datasets
   • Literature:
     
     • Ghosh, P. McAfee, K. Papineni, and S. Vassilvitskii, Bidding for
       Representative Allocations for Display Advertising. WINE 2009, 208-219
       (full paper in http://arxiv.org/PS_cache/arxiv/pdf/0910/0910.0880v1.pdf )
     • Agarwal, Kota, Agrawal, Khanna: Estimating Rates of Rare Events with
       Multiple Hierarchies through Scalable Log-linear Models, KDD 2010
6. Targeting
   
   • Selecting the right audience for ads
   • Identifying which audience actually exist
   • Segmenting the pool of possible audiences with different approaches
   • Literature:
     
     • Large-Scale Behavioral Targeting with a Social Twist, Kun Liu, CIKM 2011
     • Y. Chen, D. Pavlov and J. Canny: Large-Scale Behavioral Targeting, KDD 2009
     • Mohamed Aly, Andrew Hatch, Vanja Josifovski, Vijay K. Narayanan: Web-Scale User Modeling for Targeting, WWW 2012