# Stat 992: Theory and Methods of Network Analysis
## UW-Madison
## Karl Rohe
email: first name and last name at stat dott wisc dott edu  
office: 1239 MSC  
[Syllabus](fall15-stat992.pdf)


#### Helpful links
1) Refresh material: [An Introduction to R](http://cran.r-project.org/doc/manuals/R-intro.pdf)  
3) [Advanced R](http://adv-r.had.co.nz) by Hadley Wickham  
2) data.table is an R library that really speeds up computations on large data sets.  [Here is a cheat sheet](https://s3.amazonaws.com/assets.datacamp.com/img/blog/data+table+cheat+sheet.pdf).
4) Making beautiful documents with [R markdown](http://rmarkdown.rstudio.com) and [knitR](http://kbroman.org/knitr_knutshell/).  Here are [two](rmarkdown-cheatsheet.pdf) [cheat sheets](rmarkdown-reference.pdf).
2) Your work is useless if it is not conveyed effectively.  Please consider [visiting the campus writing center](http://writing.wisc.edu/index.html) for any/all project(s).  

#### Data
1) [Physician referral network(s)](https://questions.cms.gov/faq.php?faqId=7977).
1) [Information on physicians](https://www.cms.gov/Research-Statistics-Data-and-Systems/Statistics-Trends-and-Reports/Medicare-Provider-Charge-Data/index.html).  Click on links on left.
1) [More information on physicians](https://data.medicare.gov/views/bg9k-emty/files/rQdIQVZqsPNijOx_AgnNU4v9KnOBTB_UrxyPbgCDyK4?content_type=application%2Fzip%3B%20charset%3Dbinary&filename=physician_compare.zip) (~200MB zipped, ~600MB expanded).  [data dictionary](https://data.medicare.gov/views/bg9k-emty/files/h7l0QrAdAmn9kPZ_wabQDjD9Ph-j0rWwR_ewuVlTJd8?filename=Physician_Compare_Downloadable_Database_Dictionary.pdf&content_type=application%2Fpdf%3B%20charset%3Dbinary) and [homepage](https://data.medicare.gov/data/physician-compare)
2) Some NPI's are individuals.  Others are organizations!  [This file allows you to distinguish individuals from organizations](http://www.resdac.org/cms-data/files/nppes).
3) [A list of data sources](http://www.resdac.org/cms-data/search?f%5B0%5D=im_field_privacy_level%3A44).
2) others, more, etc. 

#### Optional text: 
Statistical Analysis of Network Data with R. By Kolaczyk and Csardi. Springer, 2014. 

### Week 1  
#### In class 
1) A starting point: MD referral networks.
1) Discussion: What year and department? What types of "network analysis things" do people do in your field?  
1) Discussion: What statistics(ish) classes have you taken?
2) Discussion: Why are you in this class?
1) What is network analysis?  
2) Why is Karl teaching this class?
2) [Syllabus](fall15-stat992.pdf)
3) Introductions to course aims. 
2) Discussion: What type of data are you interested in studying?  Topic of data source? Structure of data? 
2) Authorship issues when discussing current research.
1) Basic notation.  Graphs, nodes, edges, direction, degree, node induced subgraph, k-core
2) [Check out the data](code/downloadData.html).   Inspect [Madison](code/madison.html).



#### At home
1)  **Make sure your version of R is up to date.**  The reason that I was not able to run the code on my laptop (that was running on my desktop) is that my version of R was just a little too old.  fread in data.table was not running properly. 
1) I will assume you know how to multiply matrices.  [Here is some practice](practiceMatrixMultiplication.R).
7) I will assume you know what the eigendecomposition is.  [Here is what wikipedia says](https://en.wikipedia.org/wiki/Eigendecomposition_of_a_matrix#Eigendecomposition_of_a_matrix).  


### Week 2
#### Recap
1) What is network science?  Maybe: We study the structure of the network in order to understand its functions and the processes that happen on the network.  
2) We are studying an MD referral network (actually co-occurrence).
3) This is a type of data playground.  Pedagogical rant for future instructors.
4) Basic notation.  Graphs, nodes, edges, direction, degree, node induced subgraph, k-core.

#### In class 
1) One aim of the course is to push you to be more adventurous with trying new libraries; googling things to find answers, code snippets, etc.  The best way to quickly write code is to find someone else's!  R is a platform.
1) Continue inspecting [madison](code/madison.html). 
2) [Play with the zipcodes](code/zipcodesPlay.html)
1) Basic notation.  connected component, clusters, etc.
4) [ACS intro](code/acsIntro.html)
4) [Link edge lengths to ACS](code/acsEdgeLength.R)
1) Eigenvectors, eigendecomposition, spectral clustering V0

#### At home

1) *Make sure your version of R is up to date.*
2) [Here is a list of the common graph notation](https://webdocs.cs.ualberta.ca/~stewart/c672/Definitions.pdf).  We will use things up to and including the section on subgraphs.  Also, see graph properties on the second page. 
1) Open the [code from class](code/downloadData.Rmd) (and this [one](code/madison.html) and this [one](code/zipcodesPlay.html)) and get it running on your computer.  Remember, library(data.table) only works after installing with install.packages("data.table").  Same for igraph and other libraries. 
2) Look over the playground of possible data sets. 
3) Exercise: Pick a hospital and pick a physician characteristic.  If the characteristic is not self explanatory, describe the characteristic in words; you might have to do a google search to understand it a bit more.  Then, load the data and describe how the characteristic relates to the structure of the hospital's referral network.  What do you think explains this relationship?  Make an Rmarkdown document and describe your analysis to a friend. 
3) [Get a key](http://api.census.gov/data/key_signup.html) to download data from the [American Community Survey](https://en.wikipedia.org/wiki/American_Community_Survey).
2) I made a Piazza course.  Sorry for the delay in those who have asked... I didn't know what you were talking about!  I have sent an email invite for those enrolled.  Others are more than welcome to join.  The class is entered as "Stat 992".  If you need an invite, please send me an email.  

### Week 3
#### Announcements  

1) Forrest Crawford will be giving a guest lecture on some open problems in Thursday's class. He will give [the department seminar on Wednesday](https://www.stat.wisc.edu/sites/default/files/Seminar%20Forrest%20Crawford%2009-16-15.pdf) and we will have a roundtable discussion.  If any student or faculty has a particular interest in snowball or RDS sampling methods, we will have a round table discussion with Forrest at 1:30 in room 1217c MSC.  Of course, MSC is a nightmare to navigate!  1217c is easy to find; it is just across the hall from [Karl's office](https://dl.dropboxusercontent.com/u/4400984/HowtoFindKarlsOffice.mp4) (click link for fabulous, 11 second, student-made navigation video!).  Please feel free to circulate any of the above announcements: Thursday class, Wednesday seminar, Wednesday roundtable.
2)  We have not talked about dynamic graphs, but one interesting feature of our medicare referral data is that (i) we have multiple years of data and (ii) some years are before the implementation of the affordable care act (aka Obamacare) and some years are after the implementation.  This would be an interesting angle for a class project.


#### In class
1) Intro to network driven sampling (i.e. webcrawling and snowball sampling).
  - Intro to Markov chains. [Lecture notes](MarkovChainLecture.pdf)
  - Reference text: [Levin, Peres, Wilmer.  Markov chains and mixing times.](http://pages.uoregon.edu/dlevin/MARKOV/markovmixing.pdf)
  - unbiased estimation with Horvitz-Thompson / Inverse probability weighting / Volz-Heckathorn.  [Paper on computing the variance.](http://arxiv.org/abs/1505.05461) [Slides.](RDS-var-tech.pdf)
2) Thursday: discussion with guest [Forrest Crawford](http://crawford.research.yale.edu).

### Week 4
####Recap
1) [ACS intro](code/acsIntro.html)
4) [Link edge lengths to ACS](code/acsEdgeLength.R)
3) Have you opened the data from class?  Have you [explored any of the other data sources that we have not yet talked about?](http://www.resdac.org/cms-data/search?f%5B0%5D=im_field_privacy_level%3A44)
4) Click on the links!!!  I put them in our code documents and on this page so that you click on them.  They contain fun and important stuff.

####In class
1) [Recall that in the Madison graph](code/madison.html), it was tricky to label the nodes correctly.  Since it was an exploratory example (i.e. not for formal publication),  I didn't take the time to make these plots.  What I wanted to do then, but didn't fit into class flow, was brush! [Brushing](code/brushing.R)!  It needs Java.  Ugh.  install.packages("JGR"); library(JGR); JGR().  From here, install.packages("iplots").
  - Brushing (and dynamic graphics more generally) are amazing exploratory tools. Use these tools when you have multidimensional data that you don't (yet) understand. 
  - On new OSX machines, you might need to [install a Java update](https://support.apple.com/kb/DL1572?locale=en_US).  You will get an error to tell you this.  
2) Recall discussion of eigenvectors, eigendecomposition, spectral clustering V0. Note: SVD provides the best rank k approximation and SVD=eigen on a real symmetric matrix. [Spectral Clustering](code/spectralClusteringOnZips.html)
3) Merging two data sources for "continuous" clusters with [CASC](code/cascOnZips2.html) (click for class code).  [Click here for the original paper](http://arxiv.org/abs/1411.2158).

#### At home
Next week, we will start exploring edge directions.  There are two basic algorithms that will reveal information that is both "global" and intimately related to edge direction.

1) [pageRank](https://en.wikipedia.org/wiki/PageRank) for ranking. [Original source](http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf).  That algorithm made its creators more than 60 billion dollars; [they](http://www.forbes.com/profile/sergey-brin/) had to [share](http://www.forbes.com/profile/larry-page/) the \$ with each other :(
2) [Co-clustering](http://www.cs.toronto.edu/~osindero/mlteatalks/hartigan.pdf) for directed graphs with [Di-Sim](http://arxiv.org/abs/1204.2296).  The second link applies co-cluster to directed graphs. The first paper is the original paper on co-clustering, which was not motivated by directed graphs, but is a super fun read.
2) Data that Eva mentioned: [surgeon score card](https://projects.propublica.org/surgeons/),  [consumers checkbook](http://www.checkbook.org/surgeonratings/) rank MD's, [Dartmouth Atlas](http://www.dartmouthatlas.org) has lots of interesting things.
4) [Eva's slides](SNASeminar.pdf)

### Week 5
#### Recap
1) When you have multivariate data that you don't really understand, use brushing for dynamic visualization.
2) Eigenvectors of $A$ and the regularized $L_{sym}$ reveal partitions in the network.  If you want to find $k > 2$ clusters, find the $k$ leading eigenvectors and make an $N \times k$ matrix.  Normalize the rows and run k-means.  This is spectral clustering.
3) If you have disparate sources of network data, you can add the adjacency matrices together and then run spectral clustering!  I call this CASC, but I am not the first person to do it!  Superstar grad student Yilin Zhang is now trying to "make it better". Perhaps later in the semester she can describe her extensions.]
3) Question after class:  "Why does spectral clustering work?!" There are lots of reasons; none are fully satisfying.

#### In class
1) Finish [CASC](code/cascOnZips2.html).
1) Explore the referral network [with hierarchical clustering](code/hierarchicalClusteringZips.html). The approach used here is a combination of CASC and minimum spanning trees!  [Minimum spanning trees are amazing](https://en.wikipedia.org/wiki/Minimum_spanning_tree).  You can read about the [clustering algorithm here](http://arxiv.org/abs/1307.2302).  (Actually, the clustering algorithm actually uses a "maximum spanning tree".)
2) Relationship between normalized cuts (i.e. ncut) and eigenvectors of $L_{sym}$ [on slide 46](IntroToClustering.pdf)
3) [Why does spectral clustering work?](whyDoesSpectralWork.html)
2) [Notes on the eigendecomposition](eigenSVDlecture.pdf), the singular value decomposition, computation, etc.  
4) [Study the asymmetry in the "specialty" graph.](code/asymmetriesBySpecialty.html)


#### At home
1) Find one "external" source of data that interests you.  "External" is something that has not been analyzed in class, e.g. ACS data or the physician characteristic file. Your external data could link to NPI, hospital, or something else.  Link this data to the referral network.  Make (roughly) three summary figures to illustrate how it relates.  These could be maps, scatter plots, whatever . . . as long as they relate your data to the data we have analyzed in class. Write an abstract/summary in Markdown, [maximum 300 words](https://wordcounter.net). Include figures with captions. Due on Thursday October 8.  If you are having trouble getting started, here is [a list of possible data sources](http://www.resdac.org/cms-data/search?f%5B0%5D=im_field_privacy_level%3A44). Here are some others that Eva discussed: [surgeon score card](https://projects.propublica.org/surgeons/),  [consumers checkbook](http://www.checkbook.org/surgeonratings/) rank MD's, [Dartmouth Atlas](http://www.dartmouthatlas.org).  Finally, [here is another source](https://data.medicare.gov).
2) Here is some [cool data](https://www.cms.gov/Research-Statistics-Data-and-Systems/Statistics-Trends-and-Reports/Medicare-Provider-Charge-Data/Physician-and-Other-Supplier2013.html).  You want to click on the tab delimited link.  If you want to download the data, you will have to accept a legal agreement.  So long as you only use this for a class project, it is my understanding that this is fully within the allowances of the agreement.  

### Week 5
#### Recap

1) CASC allows you to incorporate heterogeneous sources of information.
2) Hierarchical clustering allows you to find "nested partitions".  It can be computed quickly with minimum spanning trees.  This algorithm gives a sense of the vast disparity in the flavor of clustering algorithms.
3) Algorithmic complexity, $O(n^2)$ vs $O(|E|)$. 
4) Why does spectral clustering work (three reasons).
5) Everyone has data by now... right?!?!?!  Turn it in on learn at UW.
6) I prefer homework turned in in .html via learn@uw.  However, .pdf is ok and email is also ok. 

#### In class
1) Finish [notes on the eigendecomposition](eigenSVDlecture.pdf), the singular value decomposition, computation, etc.  
2) The [Stochastic Co-Blockmodel](scbm.html) for modeling asymmetry.  
4) Finish [study the asymmetry in the "specialty" graph](code/asymmetriesBySpecialty.html). 
2) Illustrating [Stochastic Blockmodels](code/IllustratingSBMs.html) with the specialty graph.
4)  Anonymous feedback.  


### Week 6

#### Recap/announcements
1) I will give the "applied algebra" seminar this Friday at 10am in 901 Van Vleck.  I will talk about clustering graphs and making it practical.  It will review some things from class in a "seminar" format. [See the abstract here](http://www.math.wisc.edu/~zcharles/aas/index.html).  
2)  No class Tuesday Oct 20.
3)  The Stochastic Blockmodel can be "fit" with an observed $z$.  The resulting estimate of "$B$" can be interpreted as a new network; we did this for zip codes and specialty type.  If the old network is undirected, then so is $B$.  If it was directed, then so is $B$.  Either way, the SBM "approximates" the old network with a unipartite network.  However, if the underlying network is directed, then we can alternatively fit the Stochastic Co-Blockmodel.  This approximates the directed network with a bipartite network.  Each node in the bipartite graph is a "sending" node or a "receiving" node.  Each node in the original network is assigned to exactly one sending node and exactly one receiving node. When you are thinking of your projects, you will likely want to "simplify" the massive network in some way.  One way is to focus on some geographic region (e.g. Madison).  Another way is to fit an SBM with some observed $z$.
3)  [Project teams](projectTeams.html)
4)  [Project description](projectDescription.html)
4)  Feedback.


#### In class  
1)  advice in plots:  
-  use log transform in histograms.   [You can actually make a theory out of that](https://en.wikipedia.org/wiki/Variance-stabilizing_transformation)! 
-  Colors are super important.  Since we now publish on the web, use colors liberally!  Your color palette reveals how you think about your variables.  If the variable is continuous, use something continuous like col = grey(seq(1,0,len=100)). There are, of course, much better options.  The JHU faculty who write the simply statistics blog have [this to suggest](http://simplystatistics.org/2011/10/17/colors-in-r/). 
3) As we form teams, engage with your own curiosity!  Ask questions!  Do not strive for a question or an answer.  Accept that these will come with effort.  Engage with the data.  Search for papers in the literature. Throughout this task, maintain a spirit of inquiry and acknowledge that the path is uncertain.  I think this is good advice for research in general. 
4)  If you take a subgraph and it becomes [super sparse](superSparse.png), then something has gone wrong!!!  It is their connections that are interesting!  When it is so disconnected, there is very little "global structure" to understand!  The graph can be easily summarized (e.g. as X dyads, four 2-stars, and one 11-star); we don't need any algorithms!
2) Empirical regularities:  sparsity, reciprocity, degree, triangles ([transitivity ratio vs clustering coefficient](MeasuringTrianglesInGraphs.pdf)), communities at various resolutions, small diameter, motifs.
3) [Low rank matrix estimation](lowrankmatrixestimation.html).  
4) [Facts about Erdos-Renyi random graphs](ergraphs.html)

#### At home
1) At the very least, read the abstracts and introductions of the six papers in [this zip folder.](healthReadings.zip)


### Week 7

#### Recap/announcements
1)  Use log transform in histograms.  Colors are super important (continuous vs categorical)
2) Empirical regularities:  sparsity, reciprocity, degree, triangles ([transitivity ratio vs clustering coefficient](MeasuringTrianglesInGraphs.pdf)), communities at various resolutions, small diameter, motifs.
3) Email a "pre-proposal" to me by Thursday October 29.  This should be a couple paragraphs.  No pictures. Just an email and cc all group members.  The email subject line should be 992 preproposal.  


#### In class  
1) No class on Tuesday.
1) Continue [facts about Erdos-Renyi random graphs](ergraphs.html)
3) [Low rank matrix estimation](lowrankmatrixestimation.html).  


#### At home
1) Read the six papers in [this zip folder.](healthReadings.zip)
2) **Email a "pre-proposal" to me by Thursday October 29.  This should be a couple paragraphs.  No pictures. Just an email and cc all group members.  The email subject line should be 992 preproposal.**

### Week 8

#### Recap/announcements
1)  [Facts about Erdos-Renyi random graphs](ergraphs.html)
3) [Low rank matrix estimation](lowrankmatrixestimation.html).  
3) [MOAR DATA.](http://www.dartmouthatlas.org/tools/downloads.aspx)


#### In class  
1) Graphs have short pairwise distances.  (Play this game to try and find some short paths.)[http://www.cs.mcgill.ca/~rwest/wikispeedia/]

#### At home
1) Read the six papers in [this zip folder.](healthReadings.zip)
2) **Email a "pre-proposal" to me by Thursday October 29.  This should be a couple paragraphs.  No pictures. Just an email and cc all group members.  The email subject line should be 992 preproposal.**

### Week 9

#### Recap/announcements

#### In class  

#### At home


### Week 10

#### Recap/announcements

#### In class  
1) Present project proposals in class to Raj Mukherjee MD, Sara Fernandes Taylor PhD, Professor Eva DuGoff PhD, and Professor Angie Ingraham MD, MS. (November 10)


#### At home



### Week 11

#### Recap/announcements

#### In class  
1) On 11/19, [Jason Fletcher](https://www.lafollette.wisc.edu/faculty-staff/faculty/jason-fletcher) from the La Follette School of Public Affairs will talk about [his recent work](http://www.nber.org/papers/w19215).
#### At home


#### Coming up
1) proof for the power method.
2) proof of spectral convergence for A under independent edges. (1) dense. (2) sparse.
3) Davis Kahan.
3) proof for k-means step under SBM.
4) asymptotic normality for eigenvectors of A (when dense).
5) [Statistical Network Models](http://arxiv.org/pdf/0912.5410v1.pdf): 
  - Erdos-renyi; Facts,  scaling, largest component, locally tree like, diameter. See Durrett's book [Random Graph Dynamics](http://www.math.duke.edu/~rtd/RGD/RGD.pdf). 
  - inhomogeneous. 
  - ["Latent space model"](http://www.stat.cmu.edu/~brian/905-2009/all-papers/hoff-raftery-handcock-2002-jasa.pdf) vs "ERGM" approaches/questions. 
  - Aldous-hoover and graphons. 
  - Stochastic blockmodels flavored by degree, mixed, overlapping.
  - [Extensions](http://www.stat.washington.edu/research/reports/2003/tr430.pdf)
  - [Random Dot Product Model](http://papers.nips.cc/paper/3294-modeling-homophily-and-stochastic-equivalence-in-symmetric-relational-data.pdf)
5) computing the variance for RDS estimators.
6) Guest lectures.
7) [READ THIS](https://dl.dropboxusercontent.com/u/23421017/50YearsDataScience.pdf)!!!
