Network Science Analytics is divided into five thematic blocks: Introduction; Graph theory, probability and statistical inference review; Descriptive analysis and properties of large networks; Sampling, modeling and inference of networks; and Processes evolving over network graphs. In this page you will find the lecture slides we use to cover the material in each of these blocks, in addition to suggested additional reading including research papers and book chapters. Links to the slides are also available from the class schedule table.
Acknowledgment: The lecture slides here were originally prepared by myself during the first offering of this class in Spring'14. I have often borrowed figures and material organization ideas from lecture slides available in the websites of a few other great Network Science courses listed under links and resources. Since the lecture material follows closely the contents in the book
Eric D. Kolaczyk, "Statistical Analysis of Network Data: Methods and Models," Springer
I have utilized figures from the text that can be downloaded here. So if you like the slides and find them useful due credit as well as my gratitude goes to those creating that original material.
This first lecture outlines the organizational aspects of the class as well as its contents.
- Slides for this introductory block, which I will cover in the first class. We introduce the notion of network and present a "birds-eye" view of the cross-disciplinary area known as Network Science, starting with a historical background. We will continue with a series of motivating examples according to the common taxonomy of technological, social, information and biological networks. In the process, we highlight a series of intriguing relevant questions as well as analysis and computational challenges. (Updated 01/19/17)
- Introduction and Overview from Eric D. Kolaczyk, "Statistical Analysis of Network Data: Methods and Models." Available for download from the UR network.
- Overview from D. Easley and J. Kleinberg, "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".
- The "new" science of networks by D. Watts. Accesible review of the major findings in the emerging field of Network Science, with a brief discussion of their relationship with previous work in the social and mathematical sciences.
- What is Network Science? by U. Brandes et al. A short editorial from a recent Network Science journal.
- The architecture of complexity by A-L. Barabasi. A tutorial paper from the IEEE Controls Systems Magazine on how the study of complex systems necessitates a deep understanding of networks.
- The structure and function of complex networks by M. Newman. A 2003 review of the developments in the are of Networ Science, which highlights several topics and results we will cover throughout the semester.
Graph theory, probability and statistical inference review
This block is a fast-paced review of the technical background for the forthcoming material on networks analysis. It is intended as a refresher and to ensure everyone is on the same page. I will only cover the required background on graph theory and statistical inference in class. Regarding probability theory, you can get up to speed by going over the posted slides from ECE440 - Introduction to Random Processes.
- First set of slides covering basic notions and definitions relating to undirected and directed graphs, movement in a graph and connectivity, as well as the emergence of a giant connected component in many real-world graphs. We then outline graph families including complete, regular, bipartite, trees and planar graphs. Also useful are notions of algebraic graph theory, such as the adjacency, incidence and Laplacian matrices of a graph, their relationships and spectral properties. We wrap up with graph data structures and algorithms, and describe breadth-first search to e.g., calculate distances from a given vertex. I plan to cover this material in two lectures. (Updated 02/09/17)
- Second set of slides reviewing basic elements of statistical inference such as parametric and nomparametric models, and the prototypical problems of estimation, prediction and hypothesis testing. We will outline the concepts of point estimate, confidence interval and test statistic, as well as classical estimators such as the method of moments, maximum likelihood, least-squares, and maximum a posteriori (MAP). All these methods will be discussed in the context of two classical problems: inference of the mean of a distribution, and regression and prediction with linear models. I expect to cover this material in two lectures. (Updated 02/09/17)
- Preliminaries from Eric D. Kolaczyk, "Statistical Analysis of Network Data: Methods and Models." Available for download from the UR network.
- Mathematics of networks from M. E. J. Newman, "Networks: An Introduction." Available for download from the UR network.
- Graphs from D. Easley and J. Kleinberg, "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".
- First set of slides from ECE440's probability review covering sigma-algebras and the axiomatic definition of probability, conditional probability, and the notion of independence between events. We will then introduce random variables -- both discrete and continuous -- and commonly used distributions. We finish off with expectations, and joint distributions useful to study systems with multiple random inputs.
- Second set of slides from ECE440's probability review covering Markov's and Chebyshev's inequalities, and different notions of convergence for sequences of random variables (random processes). These notions of convergence allows one to establish and understand remarkable limit theorems, such as the law of large numbers and the central limit theorem. This second block is concluded with conditional probabilities and expectations, with emphasis on their usefulness for various calculations.
- Notes on probability and statistics prepared by Carlos Fernandez-Granda.
Descriptive analysis and properties of large networks
This block develops methods for the descriptive analysis of network data. The coverage goes all the way from the initial tasks of collecting and converting network measurements into a network graph representation (possibly for the sake of visualization), up to those methods for description and summarization of structure and indentification of patterns in such network graphs.
- First set of slides about network mapping, meaning the production of a network-based visualization of a complex system. We introduce three basic stages in the mapping process, namely the collection of relational data, the construction of the network graph representation and the graph visualization. The whole process is further illustrated through a couple of case studies: mapping the backbone of "Science", and visualizing the router-level Internet via the k-core decomposition. I expect to cover this material in two lectures. (Updated 02/06/17)
- Second set of slides about degree distributions, power laws and popularity as a network phenomenon. We introduce the Erdos-Renyi random graph model and evaluate its exponentially-decaying degree distribution. Interestingly, empirical studies suggest that many real-world complex networks exhibit right-skewed, heavy-tailed degree distributions best modeled as power laws. We then explain the related notion of scale-free network, and discuss common methods to visualize and fit power-law degree distributions. We conclude with the study of popularity and the description of the preferential attachment ("rich-gets-richer") model, as a simple generative network model giving rise to power-law degree distributions. I expect to cover this material in two lectures. (Updated 02/22/17)
- Third set of slides about centrality measures used to judge the importance of individual vertices in a network graph. We introduce and compare three classical measures such as closeness, betweenness, and eigenvector centrality. We then continue with link analysis algorithms for web search, and describe Hubs and Authorities as well as the PageRank algorithm for ranking nodes in graphs. After a brief review of basic definitions and results regarding Markov chains, we analyze PageRank as an equiprobable random walk in the network graph. This interpretation allows us to leverage Markov chain machinery to understand the behavior of a couple algorithmic variants. I expect to cover this materia in three lectures. (Updated 02/24/17)
- Fourth set of slides about characterzation of network cohesion. We introduce first the notion of cohesive subgroups which is naturally captured by cliques, and describe computationally affordable clique relaxations by familiarity and reachability. We continue with measures of local density such as the clustering coefficient, quantifying the extent of relationships among "equals" (homophily) through assortative coefficients; and network robustness captured by connectivity notions. We conlude with a case study about network-based analysis of epileptic seizure data in humans, leveraging several summaries of network characteristics we discussed so far. I expect to cover this material in one lecture. (Updated 02/28/17)
- Mapping Networks and Descriptive Analysis of Network Graph Characteristics from Eric D. Kolaczyk, "Statistical Analysis of Network Data: Methods and Models." Available for download from the UR network.
- The large-scale structure of networks (Section 8.3 - Degree distributions and Section 8.4 - Power laws and scale-free networks) from M. E. J. Newman, "Networks: An Introduction." Available for download from the UR network.
- Link Analysis and Web Search from D. Easley and J. Kleinberg, "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".
- Layout of Graph Visualizations, PhD Dissertation by U. Brandes. A relatively old (1999) but nevertheless useful and comprehensive treatment of automatic layout of graph visualizations.
- Embedding graphs under centrality constraints for network visualization by B. Baingana and G. B. Giannakis. A nice paper proposing structurally-constrained multidimensional scaling for large-scale graph visualization.
- Mapping the backbone of science by K. W. Boyack, R. Klavans and K. Borner. The Scientometrics paper which we overview in class as one the case studies on network graph visualization.
- Large scale networks fingerprinting and visualization using the k-core decomposition by J. I. Alvarez-Hamelin et al. A seminal NIPS paper on the use of k-core decompositions for the analysis and visualization of large scale complex networks.
- Visualizing social networks by L. C. Freeman. A nice historical review on the use of visual imagery in social network analysis.
- Emergence of scaling in random networks by A.-L. Barabasi and R. Albert. A short Science paper on scale-free power-law degree distributions encountered in large networks.
- Power-law distributions in empirical data by A. Clauset, C. R. Shalizi, and M. E. J. Newman. A comprehensive paper on principled statistical methods for discerning and quantifying power-law behavior in empirical data.
- On power-law relationships of the Internet topology by M. Faloutsos, P. Faloutsos, and C. Faloutsos. A seminal paper on power laws emerging from Internet data.
- Problems with fitting to the power-law distribution by M. L. Goldstein, S. A. Morris and G. G. Yen. A very short paper on the bias of least-squares estimates of the power-law exponent.
- A faster algorithm for betweenness centrality by U. Brandes. A quadratic-complexity algorithm to compute betweenness centrality measures, which improves signifincalty on the cubic-complexity naive (but straighforward) approach we discussed in class.
- Stability and continuity of centrality measures in weighted graphs by S. Segarra and A. Ribeiro. The paper on (in)stability of centrality measures discussed in class as a case study.
- Authoritative sources in a hyperlinked environment by J. Kleinberg. The original paper about the HITS ranking algorithm (hubs and authorities).
- The PageRank citation ranking: Bringing order to the Web by L. Page and S. Brin. The original paper by the Google co-founders.
- Graph structure in the web by A. Broder et al. A landmark paper on the study of the Web as a directed graph and its "bowtie" connectivity strucuture, while also concluding that in- and out-degree distributions behave like power laws.
- Emergent network topology at seizure onset in humans by M. Kramer, E. Kolaczyk, and H. Kirsch. A network-oriented analysis of epileptic seizure data in humans.
Sampling, modeling and inference of networks
This block describes modeling and inferential tasks for network data analytics. Smoothly transitioning from descriptive methods we first study network community identification, and then explore the effects of sampling on the extent to which characteristics of an observed network graph reflect the corresponding structural properties of the underlying system being studied. We then present models for describing an observed network graph, while we finally consider the problem of inferring a network graph based on incomplete or indirect measurements.
- First set of slides about network community detection. We start by describing the famous "strength of weak ties" hypothesis from sociology as a conceptual means of supporting the community structure found in networks. After going over a few examples of network communities, we delve into the problem of network community detection and its formulation as a clustering or graph partitioning problem. We will describe several community detection algorithms in some detail, including: (i) Girvan-Newman's method; (ii) hierarchical clustering; (iii) modularity optimization; and (iv) spectral graph partitioning. I expect to cover this material in three lectures. (Updated 03/03/17)
- Second set of slides about sampling and estimation in network graphs. We first introduce the fundamental problem of estimating a network summary characteristic from sampled graph data, and illustrate some of the inheret challenges faced. We then review basic concepts of statistical sampling theory including simple random sampling with(out) replacement and inclusion probabilites, leading to the Horvitz-Thompson estimator of totals as well as the capture-recapture method for estimation of group size. Several network graph sampling designs are then discussed, such as snowball and traceroute sampling. Horvitz-Thompson theory is subsequenly applied to estimation of vertex, edge, and higher-order totals. We conclude with the problems of estimating "hidden populations" and degree distributions. I expect to cover this material in two lectures. (Updated 03/21/17)
- Third set of slides about modeling network graphs. We introduce a number of important classes of network graph models: (i) random graph models; (ii) small-world models; (iii) network growth models; and (iv) exponential random graph models. The emphasis is on model construction, simulation, and inference of model parameters. Throughout, we illustrate some of the statistical uses to which these models have been put, including the detection of network motifs, the evaluation of proposed network generative mechanisms, and the assessment of potential predictive factors of relational ties. I expect to cover this material in three lectures. (Updated 04/11/17)
- Fourth set of slides about network topology inference, where a portion of the network graph is unobserved and we wish to infer it from measurements. We start with the link prediction problem and describe approaches based on informal scoring of potential edges, as well as classification methods possibly accounting for latent variables. Moving on to inference of association networks, we discuss (partial) correlation networks and Gaussian graphical models. In the process, we illustrate their usefulness in identifying gene-regulatory interactions from microarray data. We conclude with tomoographic network topology inference, whereby measurements are only available in the "perimeter" of the graph and it is necessary to infer the presence or absence of edges and vertices in the "interior". I expect to cover this material in three lectures. (Updated 04/18/17)
- Strong and Weak Ties and The Small-World Phenomenon from D. Easley and J. Kleinberg, "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".
- Descriptive Analysis of Network Graph Characteristics (Section 4.3.3 - Graph partitioning), Sampling and Estimation in Network Graphs, Models for Network Graphs, and Network Topology Inference from Eric D. Kolaczyk, "Statistical Analysis of Network Data: Methods and Models." Available for download from the UR network.
- Matrix algorithms and graph partitioning from M. E. J. Newman, "Networks: An Introduction." Available for download from the UR network.
- The strength of weak ties by M. S. Granovetter. A classic sociology paper studying small-scale interactions (specifically, the strenght of interpersonal ties), and showing that network analysis can relate this aspect to macro phenomena such as social cohesion and information diffusion.
- Structure and tie strengths in moblie communication networks by J. P. Onella et al. A study of a large who-calls-whom phone network, which empirically corroborates that social networks are robust to the removal of strong ties, but fall apart once sufficiently many weak ties are removed (i.e., it corroborates Granovetter's "strength of weak ties" hypothesis).
- Community structure in social and biological networks by M. Girvan and M. E. J. Newman. A divisive hierarchical clustering algorithm for community detection, based on subsequent removal of edges with highest betweenness centrality values.
- Modularity and community structure in networks by M. E. J. Newman. A landmark paper of modularity optimization for detecting and characterizing community structure in networks.
- A tutorial on spectral clustering by U. von Luxburg. A nice tutorial on the spectral clustering algorithm, useful for spectral graph partioning.
- Community detection in graphs by S. Fortunato. A thorough tutorial treatment of community detection formulations and algorithms.
- Estimating network degree distributions under sampling: An inverse problem, with applications to monitoring social media networks by Y. Zhang, E. D. Kolaczyk, and B. D. Spencer. A paper about estimating degree distributions from sampled graphs using penalized least squares.
- Estimating the size of hidden populations using snowball sampling by O. Frank and T. Snijders. A paper that leverages network sampling designs and the method of moments to estimate the size of hidden populations.
- A survey of statistical network models by A. Goldenberg et al. A nice review paper of statistical network models, touching upon both static and dynamic models for longitudinal (temporal) data.
- The small-world problem by S. Milgram. The original paper on the ingenious experiment that motivated the expression "six degrees of separation".
- Collective dynamics of `small-world' world by D. Watts and S. H. Strogatz. The celebrated small-world model which adds a little bit of randomness by rewiring some of the edges in a regular graph.
- Emergence of scaling in random networks by A.-L. Barabasi and R. Albert. A short Science paper on scale-free power-law degree distributions encountered in large networks, and their emergence using simple preferential attachment network-growth models.
- An introduction to exponential random graph (p*) models for social networks by G. Robbins et al. A beautiful tutorial on exponential random graph models for statistical analysis of social network data.
- The link prediction problem for social networks by D. Liben-Nowell and J. Kleinberg. A study on various informal scoring methods for link prediction in social networks.
- Modeling homophily and stochastic equivalence in symmetric relational data by P. D. Hoff. A NIPS paper proposing the use of logistic regression with latent variables for modeling ties among actors in a social network.
- Network tomography: Recent developments by R. Castro et al. A survey on network tomography problems including that of topology inference of tree topologies.
- Muticast topology inference from measured end-to-end loss by N. G. Duffield et al. A paper on leveraging estimates of shared packet losses among pairs of leaf nodes in a multicast tree to infer the unknown tree topology using hierarchical clustering and likelihood-based approaches.
Processes evolving over network graphs
- First set of slides about prediction of static processes defined on network graphs. We start with simple nearest-neighbor prediction, and then transition to more sophisticated model-based approaches that describe vertex attributes in terms of the given network graph structure. Specifically, we study Markov random field models in some detail with emphasis on estimation of model parameters and sampling-based prediction. We conclude with kernel-based regression on graphs, and give examples of kernels that derive from the topology of the network graph to capture similarities among vertex attributes. I expect to cover this material in two lectures. (Updated 04/26/17)
- Second set of slides about modeling of epidemic processes. Our discussion kicks off with the overly simplistic, yet insightful branching process model. In this case, we show that the epidemic exhibits a dichotomous spreading behavior depending the value of the so-termed reproductive number - either it dies off after finite time or it goes on forever. We then discuss the widely adopted SIR model and its stochastic description in terms of continuous-time Markov chains, while touching upon aspects of simulation and inference of model parameters. We finally revisit the SIR model when allowing for arbitrary contact networks, draw connections with the SIS variant which allows for reinfections, and show that the SIRS model captures the observed tendency for epidemics of certain diseases to synchronize across a population. I expect to cover this material in two lectures. (Updated 05/02/17)
- Third set of slides about analysis of network flow data. We start with the class of gravity models used to describe observations of the traffic matrix, both to obtain an uderstanding as to how potentially relevant factors affect flow volumes and to be able to make predictions of future flow volumes. We continue with the fundamental problem of traffic matrix estimation, where the goal is to recover unobserved traffic matrix entries from ubiquitous link totals. Here we discuss three statistical methods for traffic estimation, deriving from principles of least squares and Gaussian models, from Poisson models and from entropy minimization. We conclude with the problem of modeling and inference of network cost parameters, studied both at the level of links and of paths. Throughout, the techniques will be illustrated with several case studies including Internet traffic matrix estimation, unveiling of network traffic anomalies, link-count prediction and dynamic delay cartography. I expect to cover this material in three lectures. (Updated 04/26/16)
- Modeling and Prediction for Processes on Network Graphs and Analysis of Network Flow Data from Eric D. Kolaczyk, "Statistical Analysis of Network Data: Methods and Models." Available for download from the UR network.
- Epidemics from D. Easley and J. Kleinberg, "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".
- Maximum likelihood estimation of gravity model parameters by A. Shen. A paper showing that under mild conditions, ML estimates of gravity model parameters exist and are unique.
- Network tomography: Estimating source-destination traffic intensities from link data by Y. Vardi. A landmark paper on statistical methods for traffic matrix estimation.
- Bayesian inference on network traffic using link count data by C. Tebaldi and M. West. A Bayesian treatment of the traffic matrix estimation formulation put forth by Vardi.
- Dynamic network cartography by G. Mateos and K. Rajawat. A tutorial paper from the IEEE Signal Processing Magazine describing three of the case studies on the analysis of network flow data.