EECS 598-06: Social Networks:
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.

Topics Covered:

(this list is preliminary)


Participation and Comments 25%
Problem Sets 15%
In Class Presentation(s) 20%
Final Project 40%


(This list of readings is preliminary and will be changed.)
Back Ground LecturesGeneral 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 5Network ModelsFor related reading see page 23-26 of Jackson's Survey or chapters 4 and 5 of the Jackon textbook.
Sept 10Network PropertiesFor 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 TheoryFor 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 NetworksFor related readings see chapter 7 of the Jackon textbook. Also, see chapter 19 of Easley Kleinberg Text
Sept 24 Learning on Social NetworksFor 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 17Myopic 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 22Consensus
  • 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 24Evoluary 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
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

Additional Sources:

This reading is completely optional and is provided for the interested student to explore a topic in more depth.

Addition Background Papers

Additional Generative Models and Affiliation Networks Additional Generative Models with Game Theory Additional Papers on cascades and finding influential nodes Additional Papers on Revenues from Cascades Additional Papers on Stopping Viruses Additional Papers on Myopic Updating Additional Papers on Consensus and Disagreement Additional Papers on Evolutionary Biology Additional Papers on Learning Additional Papers on Laboratory experiments Additional Papers on Games on Networks Additional Papers on Competing Contagions Additional Papers on Finding Communities and Partitioning Networks Additional Papers on Local Community Detection Additional Papers on Overlapping Community Detection Additional Papers on Recovering Networks from Data Additional Papers on Defining Communities Additional Papers on Searching Networks Additional Papers on Searching for Information

Related Books:

Related Classes: