Reasoning about Structure and Processes

Instructor: Grant Schoenebeck

Time: Monday and Wednesday 10:30am-Noon

Location: 1006 DOW

The study of social networks became a familiar field of study by sociologists around the 1920s. Social networks are an abstraction used to study social structure via pair-wise social interactions. The advent of the internet has rekindled interest in this field because of the new ability to gather data and test theories on a large scale. This course will study social networks with a particular focus on how applying traditional tools, insights, and approaches from theoretical computer science (including graph theory, linear algebra, probabilistic analysis, and basic game theory) can better help us to understand this domain.

We will see how these techniques have been used in the past to explore problems such as when social networks are able (or unable) to effectively aggregate information, how network structure relates to the ability of agents to search within the network, and how network structure relates to the spreading of cascades over a network. We will also explore how these ideas might be leveraged in new ways.

The first three weeks will be background lectures. The remaining class periods will be seminar style: the class will read a paper (or set of papers), and a pair of students will briefly present the papers and lead a class discussion. Students are expected to contribute to the in-class discussion, present one or more papers, and to execute a final paper. A brief response paper about the day's reading will be required before each lecture to help facilitate discussion.

A goal of this course is to expose students to a broad range of the literature on this topic, which has developed across different fields. After this course, students should be equipped to further explore the literature on their own and to perform novel research about social networks. As such we will be reading many papers on a wide variety of topics.

No previous knowledge of social networks will be assumed, but familiarity with mathematical reasoning and basic probability theory will be essential to getting the most out of this course. Students should expect to learn additional mathematics on their own as necessary. Parts of this course will rely on basic ideas from economics (like Nash equilibrium and related notions), so experience with these ideas will also be helpful, but not assumed. I encourage students from a variety of diverse disciplines to consider this course, and this course will survey background topics. If you are interested in the course but aren't sure if you have the necessary training, please contact me and ask!

Additionally, you can try to read some of the technical papers listed below to get a sense for what we will be doing. However, note that the first part of the course will survey some background material designed to help you read these papers.

- Social network structure and properties
- Models for social network growth.
- Community Detection
- Viruses and Cascades over Networks
- Learning in Networked environments/diffusion of information
- Navigating Social networks/information location

Participation and Comments | 25% |

Problem Sets | 15% |

In Class Presentation(s) | 20% |

Final Project | 40% |

Back Ground Lectures | General Back Ground Reading- Mark Granovetter. “The Strength of Weak Ties.” American Journal of Sociology. 1973. pdf
- A. Marin and B. Wellman. Social network analysis: An introduction. pdf
- Matthew Jackson. “The Study of Social Networks In Economics.” 2007. pdf
- J. S. Coleman. "Social capital in the creation of human capital." American Journal of Sociology, 1988. pdf
- White, H. C., S. A. Boorman, and R. L. Breiger. "Social Structure From Multiple Networks I. Block models of Roles and Positions" American Journal of Sociology. 1976. pdf
- more background readdings (this reading is optional)
| ||

Sept 5 | Network Models | For related reading see page 23-26 of Jackson's Survey or chapters 4 and 5 of the Jackon textbook. | |

Sept 10 | Network Properties | For related readings see chapters 2 and 3 of the Jackon textbook. Also, see chapter 3, 4, and parts of 18 of Easley Kleinberg Text. | |

Sept 12 | Spectral Graph Theory | For related readings see Luca Trevisan's Notes, particularly Lecture's 2 and 3 and Dan Spielman's notes | |

Sept 17 | Economics, Game Theory, and Social Networks | For related readings see Chapter 6 of Easley Kleinberg Text | |

Sept 19 | Transmission on Social Networks | For related readings see chapter 7 of the Jackon textbook. Also, see chapter 19 of Easley Kleinberg Text | |

Sept 24 | Learning on Social Networks | For related readings see chapters 8 of the Jackon textbook. Also, see chapters 16 and 7 of Easley Kleinberg Text | |

Network Structure | |||

Sept 26 | Block Models and Affiliation Networks | - Ron Breiger. "The duality of persons and groups." Social Forces. 1974. pdf
- Silvio Lattanzi, D. Sivakumar. “Affiliation Networks.” STOC 09 . pdf
- more related work (this reading is optional)
| Aaron S. and Pedro |

Oct 1 | Generative Models with Game Theory | - M. O. Jackson and A. Wolinsky. “A Strategic Model of Social and Economic Networks.” Journal of Economic Theory. 1996. pdf
- Christian Borgs, Jennifer Chayes, Jian Ding, and Brendan Lucier. “The Hitchhiker's Guide to Affiliation Networks: A Game-Theoretic Approach.” ICS 2011. pdf
- more related work (this reading is optional)
| Bryce and Erik |

(Stochastic) Processes on Social Networks | |||

Oct 3 | Finding Influential Nodes | - D. Kempe, J. Kleinberg, E. Tardos. "Maximizing the Spread of Influence in a Social Network." KDD, 2003. pdf
- D. Kempe, J. Kleinberg, E. Tardos. "Influential Nodes in a Diffusion Model for Social Networks." ICALP, 2005. pdf
- more related work (this reading is optional)
| Can and Yuan |

Oct 8 | How to profit from a cascade | - D. Arthur, R. Motwani, A. Sharma, and Y. Xu. Pricing strategies for viral marketing on social networks. WINE, 2009. pdf
- more related work (this reading is optional)
| Dan and Johnathon |

Oct 10 | How to stop a cascade | - P. Chen, M. David, D. Kempe. "Better Vaccination Strategies for Better People." EC 2010. pdf
- more related work (this reading is optional)
| Travis and Erik |

Oct 17 | Myopic Updating | - Ellison, Glenn. “Learning, Local Interaction, and Coordination.” Econometrica 1993.pdf
- A. Montanari, A. Amin Saberi. “Convergence to Equilibrium in Local Interaction Games.” FOCS 2009. pdf
- more related work (this reading is optional)
| Alex and Yue |

Oct 22 | Consensus | - E. Mossel, G. Schoenebeck. "Reaching Consensus on Social Networks." ICS '10. pdf
- E. Perron, D. Vasudevan and M. Vojnovic “Using three states for binary consensus on complete graphs.” Infocom, 2009. pdf
- more related work (this reading is optional)
| Adam and Parinaz |

Oct 24 | Evoluary Biology on Networks | - Hisashi Ohtsuki and Martin A. Nowak. "Evolutionary stability on graphs." PMC 2009. pdf
- Erez Lieberman, Christoph Hauert, and Martin A. Nowak. "Evolutionary dynamics on graphs." Nature, 2004. pdf
- more related work (this reading is optional)
| Bryce and Aaron S. |

Learning in Networks | |||

Oct 29 | Information Aggregation | - A. Jadbabaie, P. Molavi, A. Sandroni, A. Tahbaz-Salehi. "Non-Bayesian Social Learning." Games and Economic Behavior 2010. pdf
- more related work (this reading is optional)
| Parinaz and Pedro |

Games over Networks | |||

Oct 31 | Human Lab Studies | - W. Mason and D. J. Watts. "Collaborative problem solving in networks." PNAS 2012. pdf
- S. Judd, M. Kearns, J. Tan and J. Wortman. "Behavioral Experiments on Biased Voting in Networks." PNAS, 2009. pdf
- more related work (this reading is optional)
| Duc and Kam Chung |

Nov 5 | Fischer Symposium | Note that this will be in BBBB | |

Nov 7 | Combatting Contagions | - S. Goyal, M. Kearns. “Competitive Contagion in Networks.” STOC 2012.pdf
- more related work (this reading is optional)
| Alex and Travis |

Analyzing networks | |||

Nov 12 | Modularity | - M. Girvan and M. E. J. Newman. “Finding and evaluating community structure in networks.” Phy Rev E, 2004. arXiv
- more related work (this reading is optional)
| Can and Yiwei |

Nov 14 | Local Community Detection | - R Andersen, Y Peres. "Finding Sparce Cuts Locally Using Evolving Sets." STOC 2009. pdf
- more related work (this reading is optional)
| Aaron T. and TBA |

Nov 19 | Affiliation Networks Reconstruction | - S. Arora, R. Ge, S. Sachdeva, G. Schoenebeck. “Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach.” EC 2012. pdf
- more related work (this reading is optional)
| Adam and Yuan |

Nov 21 | Recovering Networks from Data | - M. Gomez-Rodriguez, J. Leskovec, A. Krause. "Inferring Networks of Diffusion and Influence." KDD, 2010. pdf
- more related work (this reading is optional)
| Erik and Yue |

Nov 26 | Defining Communities | - T. Y. Berger-Wolf, C. Tantipathananandh, and D. Kempe. "Community Identification in Dynamic Social Networks." Link Mining: Models, Algorithms and Applications, 2010. pdf
- more related work (this reading is optional)
| Aaron T. and Yiwei |

Searching Networks | |||

Nov 28 | Local Routing | - Jon Kleinberg. The small-world phenomenon: An algorithmic perspective. STOC 2000. pdf
- more related work (this reading is optional)
| Dan and Duc |

Processes that change the network | |||

Dec 3 | Agreement or Leave Game | - Petter Holme, M E J Newman. “Nonequilibrium phase transition in the coevolution of networks and opinions.” Physical Review E. 2006. pdf
- R. Durrett, J.. Gleeson, A. L. Lloyd, P. J. Mucha, F. Shi, D. Sivakoff, J. E. S. Socolar, and C. Varghese. “Graph fission in an evolving voter model.” PNAS, 2012. pdf
| Grant |

Dec 5 | Emergence of Cooperation | - N. Immorlica, B. Lucier, and B. Rogers. Emergence of Cooperation in Anonymous Social Networks through Social Capital, EC 2010. pdf
- more related work (this reading is optional)
| Adam and TBD |

Dec 10 | NO CLASS |

- Mark Granovetter. “The Impact of Social Structure on Economic Outcomes.” Journal of Economic Perspectives. 2005. pdf
- A. Barabasi and R. Albert. “Emergence of scaling in random networks.” Science 1999.
- R. S. Burt. Structural Holes: The social structure of competition. Harvard University Press, 1995.
- R. S. Burt. “Structural holes and good ideas.” American Journal of Sociology. 2004.
- Markus Mobius, Do Quoc-Auh, Tanya Rosenblat. “Social Capital in Social Networks." pdf
- D. Centola and M. Macy. “Complex contagions and the weakness of long ties.” American Journal of Sociology. 2007.
- R. Grannis, “Six Degrees of "Who Cares"?” American Journal of Sociology, 2010.
- Duncan Watts, Steven Strogatz. "Collective dynamics of 'small-world' networks." Nature, 1998.
- J. Leskovec, J. Kleinberg, and C. Faloutsos. "Graphs over time: densification laws, shrinking diameters and possible explanations." KDD ’05.
- White, H. C. and S. A. Boorman. "Social Structure From Multiple Networks II. Role Structures" American Journal of Sociology. 1976. pdf

- Frank McSherry. Spectral Partitioning of Random Graphs. STOC ’01. pdf
- Edoardo M Airoldi, David M Blei, Stephen E Fienberg, Eric P Xing. “Combining stochastic block models and mixed membership for statistical network analysis.” ICML'06.
- Scott Feld. “The focused organization of social ties.” The American Journal of Sociology, 1981.
- Scott Feld. Social Structural Determinants of Similarity among Associates. American Sociological Review. 1982.
- Peter D Hoff, Adrian E Raftery, Mark S Handcock. "Latent Space Approaches to Social Network Analysis." Journal of the American Statistical Association. 2002.

- Jackson, Matthew O. “A Survey of Models of Network Formation : Stability and Efficiency.” Group January (2003) : 1-62. pdf
- Venkatesh Bala and Sanjeev Goyal. “A Noncooperative Model of Network Formation.” Econometrica 2000.
- Jon Kleinberg, Siddharth Suri, Eva Tardos, Tom Wexler. “Strategic Network Formation with Structural Holes.” ACM SIGecom Exchanges. 2008.

- M. Granovetter. "Threshold models of collective behavior." American Journal of Sociology, 1978. pdf
- Berger, Noam, Christian Borgs, Jennifer T Chayes, and Amin Saberi.. “On the Spread of Viruses in the Internet.” SODA ‘05.
- Benjamin Golub, Matthew O Jackson. “Using selection bias to explain the observed structure of Internet diffusions.” PNAS 2010.
- P. Domingos and M. Richardson. "Mining the network value of customers." KDD, 2001.
- E. Mossel and S. Roch. "On the Submodularity of Influence in Social Networks." SIAM J. Comput. 2010. pdf
- C. Borgs, M. Brautbar, J. Chayes, and B. Lucier. "Influence Maximization in Social Networks: Approximations in Nearly-Linear and Sublinear Time"

- N. Haghpanah, N. Immorlica, V. S. Mirrokni, and K. Munagala. "Optimal auctions with positive network externalities." EC 2011. pdf
- M. Babaei, B. Mirzasoleiman, M. Safari, and M. Jalili. "Revenue maximization in social networks through discounting."
- J. D. Hartline, V. S. Mirrokni, and M. Sundararajan. "Optimal marketing strategies over social networks." WWW, 2008. pdf
- Hessameddin Akhlaghpour, Mohammad Ghodsi, Nima Haghpanah, Vahab S. Mirrokni, Hamid Mahini, and Afshin Nikzad. "Optimal iterative pricing over social networks." WINE, 2010.
- P. Dayama, A. Karnik, and Y. Narahari. "Optimal incentive timing strategies for product marketing on social networks." AAMAS, 2012. pdf
- Yaron Singer. "How to Win Friends and Influence People, Truthfully: Influence Maximization Mechanisms for Social Networks." WSDM, 2012. pdf

- E. Anshelevich, D. Chakrabarty, A. Hate, and C. Swamy. Approximability of the firefighter problem: Computing cuts over time. Intl. Symp. on Algorithms and Computation, 2009.
- J. Aspnes, K. L. Chang, and A. Yamposlkiy. "Inoculation strategies for victims of viruses and the sum-of-squares partition problem." Journal of Computer and System Sciences, 2006.
- Zolt´an Dezs˝o and Albert-L´aszl´o Barab´asi. Halting viruses in scale-free networks. Physical Review E, 2002.

- Sharad Goel, Winter Mason, Duncan J Watts. “Real and perceived attitude agreement in social networks.” Journal of Personality and Social Psychology. 2010. pdf
- C. Brandt, N. Immorlica, G. Kamath and R.D. Kleinberg. An Analysis of One-Dimensional Schelling Segregation, STOC 2012. pdf
- David Bindel, Jon M. Kleinberg, Sigal Oren. "How Bad is Forming Your Own Opinion?" FOCS 2011. pdf

- R. Axelrod and W. D. Hamilton. "The Evolution of Cooperation." Science Vol. 211. 1981. pdf
- Martin A. Nowak.
*Evolutionary Dynamics: Exploring the Equations of Life*. (book)

- D Acemoglu and M. A. Dahleh. "Bayesian Learning in Social Networks." Review of Economic Studies, 78, 2011. pdf
- G. Ellison and D. Fudenberg. "Word-of-mouth communication and social learning." The Quarterly Journal of Economics 110, 1995.
- V. Bala and S. Goyal. "Conformism and diversity under social learning." Economic Theory 17, 101–120.
- E. Mossel, and O. Tamuz. Efficient Bayesian learning in social networks with Gaussian estimators. Preprint, arXiv:1002.0747. 2010.
- V. Bala and S. Goyal. "Learning from neighbors." The Review of Economic Studies 65, 1998.
- A. Banerjee and D. Fudenberg. "Word-of-mouth learning." Games and Economic Behavior 46, 2004.
- Galeotti, A. and Goyal, S. "Influencing and influencers: a theory of strategic diffusion." Rand Journal of Economics, 40, 3, 2009.
- M. H. DeGroot. "Reaching a consensus." Journal of American Statistical Association 69, 1974.

- W. Mason, A. Jones, and R. Goldstone. "Propagation of Innovations in Networked Groups." J. of Experimental Psychology. 2008. pdf
- Bibb Latan\´{e} and Todd L’Herrou. "Spatial clustering in the conformity game: Dynamic social impact in electronic groups." Journal of Personality and Social Psychology, 1996.
- Daniel P. Enemark, Mathew D. McCubbins, Ramamohan Paturi, Nicholas Weller. "Does more connectivity help groups to solve social problems." EC 2011.
- Michael Kearns, Siddharth Suri, and Nick Montfort. "An experimental study of the coloring problem on human subject networks." Science 2006.
- T. Chakraborty, S. Judd, M. Kearns, J. Tan. "A Behavioral Study of Bargaining in Social Networks." EC 2010. pdf
- S. Judd, M. Kearns, and Y. Vorobeychik. "Behavioral Dynamics and Influence in Networked Coloring and Consensus." PNAS, 2010. pdf
- S. Judd, M. Kearns, and Y. Vorobeychik. "Behavioral Experiments on a Network Formation Game." EC 2012. pdf

- M. O. JacksonGames and Y. Zenou. "Games on Networks." (Survey) pdf
- Andrea Galeotti, Sanjeev Goyal, Matthew O. Jackson, Fernando Vega-Redondo, and Leeat Yariv. "Network Games." Review of Economic Studies, 2010. pdf

- T Antunovic, Y Dekel, E Mossel, Y Peres. Competing first passage percolation on random regular graphs. pdf
- Nathaniel D. Blair-Stahn. "First Passage Percolation and Competition Models." pdf
- S. Bharathi, D. Kempe, and M. Salek. "Competitive influence maximization in social networks." WINE, 2007.
- N. Alon, M. Feldman, A. D. Procaccia, and M. Tennenholtz. "A note on competitive diffusion through social networks." Inf. Process. Lett., 110(6):221–225, 2010.
- K. R. Apt and E. Markakis. "Diffusion in social networks with competing products." In SAGT, pages 212–223, 2011.pdf
- A. Borodin, Y. Filmus, and J. Oren. "Threshold models for competitive influence in social networks." WINE, 2010. pdf
- K. R. Apt and E. Markakis. "Diffusion in Social Networks with Competing Products." arXiv 2011. pdf

- Frank McSherry. Spectral Partitioning of Random Graphs. STOC ’01. pdf
- M. Girvan and M. E. J. Newman. “Community structure in social and biological networks.” PNAS 2002. arXiv
- Adrien Friggeri, Guillaume Chelius, Eric Fleury. “Triangles to Capture Social Cohesion.” 2011.
- Y. Dekel, O. Gurel-Gurevich, and Y. Peres. "Finding Hidden Cliques in Linear Time with High Probability." pdf
- J. Leskovec, K. J. Lang, A. Dasgupta, and M. W. Mahoney. “Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters.” Internet Mathematics, 2008.
- Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavanin. "Detecting High Log-Densities - An O(n¼) Approximation for Densest k-Subgraph." STOC '10.

- R Andersen, Y Peres. "Finding Sparce Cuts Locally Using Evolving Sets." pdf
- R. Andersen, F. R. K. Chung, and K. J. Lang. "Local graph partitioning using pagerank vectors." In FOCS'06.
- Michael W Mahoney, Lorenzo Orecchia, Nisheeth K Vishnoi. “A spectral Algorithm for improving graph partitions.” 2009. pdf
- Michael W Mahoney, Lorenzo Orecchia, Nisheeth K Vishnoi. “A spectral Algorithm for improving graph partitions: with Applications to Improving Graph Partitions and Exploring Data Graphs Locally.” 2009. pdf
- Daniel A. Spielman, Shang-Hua Teng. "A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning". arXiv, 2008. pdf

- Santo and Fortunato. Community detection in graphs. Physics Reports, 2010.
- Jierui Xie, Stephen Kelley, Boleslaw K Szymanski. “Overlapping Community Detection in Networks: the State of the Art and Comparative Study” Search. 2011.
- M.-F. Balcan, C. Borgs, M. Braverman, J. Chayes, and S.-H. Teng. “I like her more than you: Self-determined communities.” 2011.
- D. Eppstein, M. Loffler, and D. Strash. “Listing all maximal cliques in sparse graphs in near optimal time.” Algorithms and Computation, 2010.
- Nina Mishra, Robert Schreiber, Isabelle Stanton, and Robert Tarjan. “Clustering Social Networks.” (2) 2005.
- Ittai Abraham, Shiri Chechik, David Kempe, Aleksandrs Slivkins. Low-distortion Inference of Latent Similarities from a Multiplex Social Network. arXiv 2011. pdf

- M. Gomez-Rodriguez, J. Leskovec, A. Krause. "Inferring Networks of Diffusion and Influence." TKDD, 2012. pdf

- J. Hopcroft, O. Khan, B. Kulis, and B. Selman. “Natural communities in large linked networks.” KDD 03.

- Stanley Milgram. “ The small world problem.” Psychology Today, 1967.
- J. Travers, S. Milgram. "An experimental study of the small world problem." Sociometry, 1969.
- D.J. Watts, P.S., Dodds, M.E.J. Newman. “Identity and search in social networks.” Science, 2002. pdf
- Lee, N.H. The Search for an Abortionist. University of Chicago Press, 1969. (Chapters 1 and 5).
- Easley and Kleinberg. Chapter 20. pdf
- R. Kumar, D. Liben-Nowell, A. Tomkins. "Navigating Low-Dimensional and Hierarchical Population Networks." ESA '06 pdf

- Jon Kleinberg, Prbhakar Raghavan. "Query Incentive Networks." FOCS ‘05 pdf
- Moshe Babaioff, Shahar Dobzinski, Sigal Oren, and Aviv Zohar. "On bitcoin and red balloons." EC 2012.

- Easley, David and Jon Kleinberg. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. (Available Open Access)
- Mathew O. Jackson: Social and Economic Networks.
- David Kempe. Structure and Dynamics of Information in Networks. Class Notes as book.
- J. Scott. Social Network Analysis: And handbook. Sage Publications Lt, 2 edition, 2000.