22C:196 Social Networks: Models, Algorithms, and Applications
2:00-3:15 TTh Room 16 EPB
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
- 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.
- Week 15: 5/1 and 5/3
- Week 14: 4/24 and 4/26
- Week 13: 4/17 and 4/19
- Week 12: 4/10 and 4/12
- Week 11: 4/3 and 4/5
- Week 10: 3/27 and 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
- 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.