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.
| Participation and Comments | 25% |
| Problem Sets | 15% |
| In Class Presentation(s) | 20% |
| Final Project | 40% |
| Back Ground Lectures | General Back Ground Reading
| ||
| 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 |
| Aaron S. and Pedro |
| Oct 1 | Generative Models with Game Theory |
| Bryce and Erik |
| (Stochastic) Processes on Social Networks | |||
| Oct 3 | Finding Influential Nodes |
| Can and Yuan |
| Oct 8 | How to profit from a cascade |
| Dan and Johnathon |
| Oct 10 | How to stop a cascade |
| Travis and Erik |
| Oct 17 | Myopic Updating |
| Alex and Yue |
| Oct 22 | Consensus |
| Adam and Parinaz |
| Oct 24 | Evoluary Biology on Networks |
| Bryce and Aaron S. |
| Learning in Networks | |||
| Oct 29 | Information Aggregation |
| Parinaz and Pedro |
| Games over Networks | |||
| Oct 31 | Human Lab Studies |
| Duc and Kam Chung |
| Nov 5 | Fischer Symposium | Note that this will be in BBBB | |
| Nov 7 | Combatting Contagions |
| Alex and Travis |
| Analyzing networks | |||
| Nov 12 | Modularity |
| Can and Yiwei |
| Nov 14 | Local Community Detection |
| Aaron T. and TBA |
| Nov 19 | Affiliation Networks Reconstruction |
| Adam and Yuan |
| Nov 21 | Recovering Networks from Data |
| Erik and Yue |
| Nov 26 | Defining Communities |
| Aaron T. and Yiwei |
| Searching Networks | |||
| Nov 28 | Local Routing |
| Dan and Duc |
| Processes that change the network | |||
| Dec 3 | Agreement or Leave Game |
| Grant |
| Dec 5 | Emergence of Cooperation |
| Adam and TBD |
| Dec 10 | NO CLASS |