# Network Analysis & Modeling

# CSCI 5352 - Network Analysis & Modeling

**Fall 2020**

- Time: Monday, Wednesday, Friday, 1:50pm - 2:40pm
- Place:
**email for Zoom link or see Canvas**; ECCS 1B28 - Lecturer: Dan Larremore
- Office: –Online–
- Office hours: –TBD–
- Email: daniel.larremore
- Teaching Assistant: None
- Syllabus: PDF

## Description

Network science is a thriving and increasingly important cross-disciplinary domain that focuses on the representation, analysis, and modeling of complex social, biological and technological systems as networks or graphs. Modern data sets often include some kind of network. Nodes can have locations, directions, memory, demographic characteristics, content, and preferences. Edges can have lengths, directions, capacities, costs, durations, and types. And, these variables and the network structure itself can vary, with edges and nodes appearing, disappearing and changing their characteristics over time. Capturing, modeling and understanding networks and rich data requires understanding both the mathematics of networks and the computational tools for identifying and explaining the patterns they contain.

This graduate-level course will examine modern techniques for analyzing and modeling the structure and dynamics of complex networks. The focus will be on statistical algorithms and methods, and both lectures and assignments will emphasize model interpretability and understanding the processes that generate real data. Applications will be drawn from computational biology and computational social science. No biological or social science training is required. (Note: this is not a scientific computing course, but there will be plenty of computing for science.)

For all grading and other information, please see the Syllabus PDF.

## Schedule

- Week 1 - Introduction and overview [Lecture 0] [Lecture 1] [Notes]
- Week 2 - Measures of structural importance [Lecture 2] [Notes]
- Week 3 - Random graphs I [Lecture 3] [webweb] [G(n,p) + webweb notebook] [Notes]
- Week 4 - Random graphs II [Lecture 4] [Notes]
- Week 5 - Large-scale structure I [Lecture 5] [Notes]
- Week 6 - Large-scale structure II [Lecture 6] [Notes] [SBM + webweb notebook]
- Week 7 - Spreading processes on networks [Lecture 7] [Notes] [Kleinberg Ch 24]
- Week 8 - Ranking in directed networks and pairwise comparisons [Lecture 8] [Notes]
- Week 9 - Wrangling network data I (sampling) [Lecture 9] [Notes]
- Week 10 - Wrangling network data II (data, statistics, and tests) [Lecture 10] [Notes] [Notes] [Notes] [Notes] [Notes]
- Week 11 - Spatial networks [Lecture 11]
- Week 12 - Growing networks [Lecture 12]
- Week 13 - Dynamic Networks [Lecture 13]
- Weeks 14-15 - Project Presentations & Wrapup

## Problem Sets

- HW1
- HW2
- HW3
- HW4
- HW5 and HW6 (combined)
- HW7 and HW8 (combined)
- HW9 and HW10 (combined)
- HW11 and HW12 (combined)

## Supplemental Readings

Week 1:

- M.E.J. Newman, "The structure and function of complex networks."
*SIAM Review***45**, 167-256 (2003). - L. Breiman, "Statistical Modeling: The Two Cultures."
*Statistical Science***16**, 199-231 (2001).

Week 2:

- M.E.J. Newman, "Power laws, Pareto distributions and Zipf's law."
*Contemporary Physics***46**(5), 323-351 (2005). - M. Mitzenmacher, "A Brief History of Generative Models for Power Law and Lognormal Distributions."
*Internet Mathematics***1**(2), 226-251 (2004). - A. Clauset, C.R. Shalizi and M.E.J. Newman, "Power-law distributions in empirical data."
*SIAM Review***51**(4), 661-703 (2009).

Week 3:

- D. Geer, D.B. Larremore "Progress is Infectious".
*IEEE Security and Privacy*10(6), p. 94-95 (2012). - S. Borgati, "Centrality and network flow."
*Social Networks***27**, 55-71 (2005). - B. Ball and M.E.J. Newman, "Friendship networks and social status."
*Network Science***1**, 16-30 (2013).

Week 4:

- B.K. Fosdick et al., "Configuring Random Graph Models with Fixed Degree Sequences." Preprint, arxiv:1608.00607 (2016).
- D.S. Callaway et al., "Are randomly grown graphs really random?"
*Physical Review E***64**, 041902 (2001). - J. Hackl and B.T. Adey, "Generation of spatially embedded random networks to model complex transportation networks." Preprint, arxiv:1609.03324 (2016).

Week 5:

- M. McPherson, L. Smith-Lovin and J.M. Cook, "Birds of a Feather: Homophily in Social Networks."
*Annual Reviews of Sociology***27**, 415-444 (2001). - M.E.J. Newman, "Mixing patterns in networks."
*Physical Review E***67**, 026126 (2003). - L. Peel, J.-C. Delvenne, and R. Lambiotte, "Multiscale mixing patterns in networks."
*Proc. Natl. Acad. Sci. USA*, Early Edition (2018). - A. Clauset, M.E.J. Newman and C. Moore, "Finding community structure in very large networks."
*Physical Review E***70**, 066111 (2004). - B.H. Good, Y.-A. de Montjoye and A. Clauset, "Performance of modularity maximization in practical contexts."
*Physical Review E***81**, 046106 (2010).

Week 6:

- B. Karrer and M.E.J. Newman, "Stochastic blockmodels and community structure in networks."
*Physical Review E***83**, 016107 (2011). - A. Clauset, C. Moore, and M.E.J. Newman, "Hierarchical structure and the prediction of missing links in networks."
*Nature***453**, 98 - 101 (2008). - B. Ball, B. Karrer and M.E.J. Newman, "An efficient and principled method for detecting communities in networks."
*Physical Review E***84**, 036103 (2011). - T. P. Peixoto, "Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models."
*Phys. Rev. E***89**, 012804 (2014)

Week 7:

- S. Goel et al., "The Structural Virality of Online Diffusion."
*Management Science***62**(1), 180-196 (2015). - J. Cheng et al., "Can cascades be predicted?."
*Proc. WWW*(2014). - D. J. Watts & P. S. Dodds, "Influentials, Networks, and Public Opinion Formation."
*J. Consumer Research***34**, 441-458 (2007). - P. S. Dodds, "Slightly generalized Generalized Contagion: Unifying simple models of biological and social spreading." Preprint, arXiv:1708.09697 (2018).
- D. Brockmann & D. Helbing, "The hidden geometry of complex, network-driven contagion phenomena."
*Science***342**, 1337-1342 (2013).

Week 8:

See links in Lecture 8 notes.

Week 9:

- P. Orbanz, "Subsampling large graphs and invariance in networks." Preprint, arxiv:1710.04217 (2018).
- A. C. Thomas & J. K. Blitztein, "Valued Ties Tell Fewer Lies: Why not to dichotomize network edges with thresholds." Preprint, arXiv:1101.0788 (2011).
- N. K. Ahmed et al., "Graph Sample and Hold: A Framework for Big-Graph Analytics." Proc. KDD (2014).
- B. Ribeiro & D. Towsley, "On the Estimation Accuracy of Degree Distributions from Graph Sampling."
*IEEE Conference on Decision and Control*(2012). - J. Blumenstock et al., "Predicting poverty and wealth from mobile phone metadata."
*Science***350**(6264), 1073-1076 (2015).

Week 9 Bonus:

- L. Peel, D. B. Larremore, & A. Clauset, "The ground truth about metadata and community detection in networks."
*Science Advances***3**(5), e1602548 (2018). - M. E. J. Newman and A. Clauset, "Structure and inference in annotated networks."
*Nature Communications***7**, 11863 (2016). - T. P. Peixoto, "Hierarchical block structures and high-resolution model selection in large networks."
*Phys. Rev. X***4**, 011047 (2014). - T. P. Peixoto, "Nonparametric Bayesian inference of the microcanonical stochastic block model."
*Phys. Rev. E***95**012317 (2018).

Week 10:

- R. Milo et al., "Network Motifs: Simple Buildling Blocks of Complex Neteworks"
*Science***298**, 824-827 (2002). - M. Middendorf et al., "Inferring network mechanisms: The Drosophila melanogaster protein interaction netework"
*Proc. Natl. Acad. Sci. USA***102**(9), 3192-3197 (2005). - B. Karrer and M.E.J. Newman, "Random graphs containing arbitrary distributions of subgraphs."
*Physical Review E***82**, 066118 (2010). - T. E. Gorochowski, C. S. Grierson, and M. di Bernardo, "Organization of feed-forward loop motifs reveals architectural principles in natural and engineered networks."
*Science Advances***4**(3), eaap9751 (2018).

Week 11:

- S. Milgram, "The Small-World Problem."
*Psychology Today***1**(1), 61-67 (1967). - D. Watts and S. Strogatz, "Collective dynamics of 'small-world' networks."
*Nature***393**, 440-442 (1998). - J. Kleinberg, "The Small-World Phenomenon, an Algorithmic Perspective."
*Proc. 32nd ACM Symposium on Theory of Computing*(2000). - D. Liben-Nowell et al., "Geographic routing in social networks."
*PNAS***102**(33), 11623-11628 (2005). - M. Barthelemy, "Spatial Networks."
*Physics Reports***499**, 11-101 (2011).

Week 12:

- S. Redner, "Citation statistics from 110 years of
*Physical Review*."*Physics Today***58**, 49-54 (2005). - M.E.J. Newman, "The first-mover advantage in scientific publication."
*European Physics Letters***86**, 68001 (2009). - A. Vazquez, A. Flammini, A. Maritan, and A. Vespignani,
"Modeling of protein interaction networks."
*Complexus***1**, 38-44 (2003).

Week 12:

- P. Holme and J. Saramaki, "Temporal Networks."
*Phys. Rep.***519**, 97-125 (2012). - D. Kempe, J. Kleinberg and A. Kumar, "Connectivity and Inference Problems for Temporal Networks."
*Journal of Computer and System Sciences***64**(2002).

Week 13:

- M. Kivela et al., "Multilayer Networks."
*J. Complex Networks***2**(3), 203-271 (2014). - P.J. Mucha et al., "Community Structure in Time-Dependent, Multiscale, and Multiplex Networks."
*Science***328**, 876-878 (2010). - J.G. Restrepo, E. Ott, and B.R. Hunt, "Onset of synchronization in large networks of coupled oscillators."
*Physical Review E***71**(3), 036151 (2005)

**Network Tools**

NetworkX, network analysis package (Python)</br>
igraph, network analysis tools (Python, C++, R)

graph-tool, network analysis and visualization software (Python, C++)</br>
GraphLab, scalable network analysis (Python, C++)</br>

**Network Visualization**

Cytoscape, network
visualization software

yEd Graph Editor, network visualization software

Graphviz,
network visualization software</br>
Gephi, network visualization software</br>
graph-tool, network analysis and visualization software</br>
webweb, network visualization tool joining Matlab and d3

MuxViz, multilayer analysis and visualization platform

**Network Data Sets**

The Colorado Index of Complex Networks (ICON; more than 4000 graphs)

US Census Education-Employment network (social, bipartite, weighted)

**Other Courses on Networks**

Network Theory (University of Michigan)

Statistical Network Analysis (Purdue University)

Networks (Cornell University)

Networks (Harvard University)

Social and Economic Networks: Models and Analysis (Coursera / Stanford)

Social Network Analysis (Coursera / University of Michigan)

Social and Information Network Analysis (Stanford)

Graphs and Networks (Yale)

Spectral Graph Theory (Yale)

The Structure of Social Data (Stanford)</br>

**Resources**

LaTeX (general) and TeXShop (Mac)

Matlab license for CU staff (includes student employees)

Mathematica license for CU students

NumPy/SciPy libraries for Python (similar to Matlab)

GNU Octave (similar to Matlab)

Wolfram Alpha (Web interface for simple integration and differentiation)

Introduction to the Modeling and Analysis of Complex Systems, by Hiroki Sayama (free online textbook)

**Things Worth Reading**

Everything you wanted to know about Data Analysis and Fitting but were afraid to ask, by Peter Young

Machine Learning, Statistical Inference and Induction Notebook (by Cosma Shalizi)

Power Law distributions, etc. Notebook (by Cosma Shalizi)

Statistics Done Wrong, The woefully complete guide (by Alex Reinhart)

Some Advice on Process for
[Research Projects]