22C:196 Social Networks: Models, Algorithms, and Applications

Instructors: Sriram V. Pemmaraju and Alberto M. Segre
SVP Coordinates: 101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
AMS Coordinates: 14D MLH, alberto-segre@uiowa.edu, 319-335-1713
Office Hours: SVP: TBA and AMS: By appointment
Course webpage: www.cs.uiowa.edu/~sriram/196/spring12

In this course we will study a common set of tools and techniques that have emerged over the last decade for the modeling and analysis of social, technological, and biological networks and the processes that interact with these networks. The main themes of the course include (i) random graph models for real-world networks, (ii) the spread of information, disease, influence, etc., on networks, (iii) models and algorithms for web search and sponsored search, and (iv) game-theoretic approach to interaction on networks. The course aims to bring together advances from different disciplines: computer science, mathematics, statistics, physics, economics, and sociology and present them in a manner that students with basic CS backgroud and some mathematical maturity can relate to. A detailed list of topics appears in the syllabus.

Syllabus document, Announcements, Weekly Topics and Lecture Notes, Links to Papers and Other Resources

Announcements

• 4/11 Colloquium by Sara Del Valle on the computational modeling of the spread of epidemics.
• 3/14 Chris Bauch will be the colloquium speaker on 3/23. Among other things, he is an expert in infectious disease modeling, applications of game theory to vaccination policies, etc.
• 3/9 In class on 3/8 (Thursday) we proposed this time line for your research papers.
• 2/7 Research paper "prospectus" due on Tuesday, 2/14. It should contain: (i) the topic of your paper, (ii) conferences/journals you intend to target, (iii) data sets you will use, (iv) questions your paper seeks to answer, and (v) a few citations that will serve as starting points for your paper.
• 1/29 Topics for research papers.
• 1/29 Quick review of basic probability theory.
• 1/18 Here is a directory with latex template for lecture notes. I have tried to illustrate some math, figure inclusion, use of bibliography file, etc. in this template.
• 1/17 Jarad Niemi from Statistics at Iowa State will kick off the colloquium series for spring 2012 at 4 pm on Friday, 1/20.

Weekly Topics and Lecture Notes

• Week 15: 5/1 and 5/3
  • Lecture on 5/1, Lecture on 5/3.

• Week 14: 4/24 and 4/26
  • Lecture on 4/24, Lecture on 4/26.

• Week 13: 4/17 and 4/19
  • Lecture on 4/17, Lecture on 4/19.

• Week 12: 4/10 and 4/12
  • Lecture on 4/10, Lecture on 4/12.

• Week 11: 4/3 and 4/5
  • Contact network epidemiology in the hospital setting: discussion of papers Controlling nosocomial infection based on structure of hospital social networks, Prioritizing Healthcare Worker Vaccinations on the Basis of Social Network Analysis.
  • Introduction to game theory: games with and without dominant strategies, Nash Equilibrium as a solution concept for games.
  • Lecture on 4/3, Lecture on 4/5.

• Week 10: 3/27 and 3/29
  • Spread of disease on network models.
  • Discussion of two papers: Building epidemiological models from R0: an implicit treatment of transmission in networks and When individual behavior matters: homogeneous and network models in epidemiology.
  • Discussion of research that used large-scale network-based simulations to predict disease spread: Strategies for containing an emerging influenza pandemic in Southeast Asia, Modeling targeted layered containment of an influenza pandemic in the United States.
  • Lecture on 3/27, Lecture on 3/29.

• Week 9: 3/20 and 3/22
  • Basic disease spread models based on the "mass action" principle: SI, SIR, SIS, SIRS, etc.
  • Viral marketing: the problem of influence maximization on a network.
  • Approximation algorithms, max-coverage, submodular functions and the result of Kempe, Kleinberg, and Tardos.
  • Lecture on 3/20, Lecture on 3/22.

• Week 8: 3/6 and 3/8
  • Diffusion of innovation: The Ryan and Gross study on hybrid corn and the Tetracycline study.
  • The Bass model and predicting the "S-curve" observed during diffusion of innovation.
  • Network-based models of diffusion.
  • Lecture on 3/6. Lecture 16 was devoted to a discussion of expectations for the research papers.

• Week 7: 2/28and 3/1
  • Description of the Framingham Heart Study data set.
  • Methods and results from the "obesity" paper of Christakis and Fowler.
  • Extensions of these results to smoking, happiness, etc.
  • Methodological critique of this series of papers.
  • Links to the papers discussed this week.
  • Lecture on 2/28, Lecture on 3/1.

• Week 6: 2/21 and 2/23
  • An example calculation in the configuration model: clustering coefficient.
  • The preferential attachment model.
  • How the preferential attachment model leads to power law degree distribution, with power law exponent 3.
  • A variant of the preferential attachment model that leads to a range of power law exponents.
  • Lecture on 2/21, Lecture on 2/23.

• Week 5: 2/14 and 2/16
  • Heuristic argument for why the Kleinberg model permits efficient decentralized search for specific parameter values.
  • A further generalization of the Kleinberg model to take varying geographic density into account. This is from a paper by Liben-Nowell et al. that appeared in PNAS 2005. This paper uses data from "live journal" to validate its results.
  • Degree-distribution based models: The configuration model and the Chung-Lu variant.
  • Lecture on 2/14, Lecture on 2/16.

• Week 4: 2/7 and 2/9
  • Example of "Network Analysis" applied to self-help group meetings data set.
  • The Watts-Strogatz Model.
  • The Kleinberg Model that extends the Watts-Strogatz model to permit efficient decentralized search.
  • Lecture on 2/7, Lecture on 2/9.

• Week 3: 1/31 and 2/2
  • Completion of the heuristic proof of the "small world" property of ER graphs
  • Phase transitions in ER graphs
  • The Watts-Strogatz random graph with high clustering coefficient and small average path length.
  • Lecture on 1/31, Lecture on 2/2.

• Week 2: 1/24 and 1/26
  • More definitions of basic graph-theoretic notions: clustering coefficient, giant component.
  • Examples of social, technological, biological, and information networks.
  • Overview of network datasets and programming tools for analyzing network data.
  • Definition of random graphs, Erdos-Renyi (ER) graphs.
  • The degree distribution of ER graphs, clustering coefficient of ER graphs, a heuristic proof of the "small world" property of ER graphs.
  • Lecture on 1/24, Lecture on 1/26.

• Week 1: 1/17 and 1/19
  • A small sample of phenomena we will study during the semester including (i) an algorithmic view of the "small world" phenomenon, (ii) a game-theoretic view of traffic modeling, and (iii) viral marketing and approximation algorithms.
  • Definitions of basic graph-theoretic notions: degree distribution, the power-law distribution.
  • Lecture on 1/17, Lecture on 1/19.

Links to Papers and Other Resources

• The Python Networkx software package and a tutorial from Stanford demonstrating the use of this package.
• Stanford Large Network Collection Dataset.
• Mark Newman's network datasets.