| |
| |
| |
Introduction and Overview | |
| |
| |
| |
Why Networks? | |
| |
| |
| |
Examples of Networks | |
| |
| |
| |
Technological Networks | |
| |
| |
| |
Social Networks | |
| |
| |
| |
Biological Networks | |
| |
| |
| |
Information Networks | |
| |
| |
| |
About this Book | |
| |
| |
| |
Preliminaries | |
| |
| |
| |
Background on Graphs | |
| |
| |
| |
Basic Definitions and Concepts | |
| |
| |
| |
Families of Graphs | |
| |
| |
| |
Graphs and Matrix Algebra | |
| |
| |
| |
Graph Data Structures and Algorithms | |
| |
| |
| |
Background in Probability and Statistics | |
| |
| |
| |
Probability | |
| |
| |
| |
Principles of Statistical Inference | |
| |
| |
| |
Methods of Statistical Inference: Tutorials | |
| |
| |
| |
Statistical Analysis of Network Data: Prelude | |
| |
| |
| |
Additional Related Topics and Reading | |
| |
| |
Exercises | |
| |
| |
| |
Mapping Networks | |
| |
| |
| |
Introduction | |
| |
| |
| |
Collecting Relational Network Data | |
| |
| |
| |
Measurement of System Elements and Interactions | |
| |
| |
| |
Enumerated, Partial, and Sampled Data | |
| |
| |
| |
Constructing Network Graph Representations | |
| |
| |
| |
Visualizing Network Graphs | |
| |
| |
| |
Elements of Graph Visualization | |
| |
| |
| |
Methods of Graph Visualization | |
| |
| |
| |
Case Studies | |
| |
| |
| |
Mapping 'Science' | |
| |
| |
| |
Mapping the Internet | |
| |
| |
| |
Mapping Dynamic Networks | |
| |
| |
| |
Additional Related Topics and Reading | |
| |
| |
Exercises | |
| |
| |
| |
Descriptive Analysis of Network Graph Characteristics | |
| |
| |
| |
Introduction | |
| |
| |
| |
Vertex and Edge Characteristics | |
| |
| |
| |
Degree | |
| |
| |
| |
Centrality | |
| |
| |
| |
Characterizing Network Cohesion | |
| |
| |
| |
Local Density | |
| |
| |
| |
Connectivity | |
| |
| |
| |
Graph Partitioning | |
| |
| |
| |
Assortativity and Mixing | |
| |
| |
| |
Case Study: Analysis of an Epileptic Seizure | |
| |
| |
| |
Characterizing Dynamic Network Graphs | |
| |
| |
| |
Additional Related Topics and Reading | |
| |
| |
Exercise | |
| |
| |
| |
Sampling and Estimation in Network Graphs | |
| |
| |
| |
Introduction | |
| |
| |
| |
Background on Statistical Sampling Theory | |
| |
| |
| |
Horvitz-Thompson Estimation for Totals | |
| |
| |
| |
Estimation of Group Size | |
| |
| |
| |
Common Network Graph Sampling Designs | |
| |
| |
| |
Induced and Incident Subgraph Sampling | |
| |
| |
| |
Star and Snowball Sampling | |
| |
| |
| |
Link Tracing | |
| |
| |
| |
Estimation of Totals in Network Graphs | |
| |
| |
| |
Vertex Totals | |
| |
| |
| |
Totals on Vertex Pairs | |
| |
| |
| |
Totals of Higher Order | |
| |
| |
| |
Effects of Design, Measurement, and Total | |
| |
| |
| |
Estimation of Network Group Size | |
| |
| |
| |
Other Network Graph Estimation Problems | |
| |
| |
| |
Additional Related Topics and Reading | |
| |
| |
Exercises | |
| |
| |
| |
Models for Network Graphs | |
| |
| |
| |
Introduction | |
| |
| |
| |
Random Graph Models | |
| |
| |
| |
Classical Random Graph Models | |
| |
| |
| |
Generalized Random Graph Models | |
| |
| |
| |
Simulating Random Graph Models | |
| |
| |
| |
Statistical Application of Random Graph Models | |
| |
| |
| |
Small-World Models | |
| |
| |
| |
The Watts-Strogatz Model | |
| |
| |
| |
Other Small-World Network Models | |
| |
| |
| |
Network Growth Models | |
| |
| |
| |
Preferential Attachment Models | |
| |
| |
| |
Copying Models | |
| |
| |
| |
Fitting Network Growth Models | |
| |
| |
| |
Exponential Random Graph Models | |
| |
| |
| |
Model Specification | |
| |
| |
| |
Fitting Exponential Random Graph Models | |
| |
| |
| |
Goodness-of-Fit and Model Degeneracy | |
| |
| |
| |
Case Study: Modeling Collaboration Among Lawyers | |
| |
| |
| |
Challenges in Modeling Network Graphs | |
| |
| |
| |
Additional Related Topics and Reading | |
| |
| |
Exercises | |
| |
| |
| |
Network Topology Inference | |
| |
| |
| |
Introduction | |
| |
| |
| |
Link Prediction | |
| |
| |
| |
Informal Scoring Methods | |
| |
| |
| |
Probabilistic Classification Methods | |
| |
| |
| |
Case Study: Predicting Lawyer Collaboration | |
| |
| |
| |
Inference of Association Networks | |
| |
| |
| |
Correlation Networks | |
| |
| |
| |
Partial Correlation Networks | |
| |
| |
| |
Gaussian Graphical Model Networks | |
| |
| |
| |
Case Study: Inferring Genetic Regulatory Interactions | |
| |
| |
| |
Tomographic Network Topology Inference | |
| |
| |
| |
Tomographic Inference of Tree Topologies | |
| |
| |
| |
Methods Based on Hierarchical Clustering | |
| |
| |
| |
Likelihood-based Methods | |
| |
| |
| |
Summarizing Collections of Trees | |
| |
| |
| |
Case Study: Computer Network Topology Identification | |
| |
| |
| |
Additional Related Topics and Reading | |
| |
| |
Exercises | |
| |
| |
| |
Modeling and Prediction for Processes on Network Graphs | |
| |
| |
| |
Introduction | |
| |
| |
| |
Nearest Neighbor Prediction | |
| |
| |
| |
Markov Random Fields | |
| |
| |
| |
Markov Random Field Models | |
| |
| |
| |
Inference and Prediction for Markov Random Fields | |
| |
| |
| |
Related Probabilistic Models | |
| |
| |
| |
Kernel-based Regression | |
| |
| |
| |
Kernel Regression on Graphs | |
| |
| |
| |
Designing Kernels on Graphs | |
| |
| |
| |
Case Study: Predicting Protein Function | |
| |
| |
| |
Modeling and Prediction for Dynamic Processes | |
| |
| |
| |
Epidemic Processes: An Illustration | |
| |
| |
| |
Other Dynamic Processes | |
| |
| |
| |
Additional Related Topics and Reading | |
| |
| |
Exercises | |
| |
| |
| |
Analysis of Network Flow Data | |
| |
| |
| |
Introduction | |
| |
| |
| |
Gravity Models | |
| |
| |
| |
Model Specification | |
| |
| |
| |
Inference for Gravity Models | |
| |
| |
| |
Traffic Matrix Estimation | |
| |
| |
| |
Static Methods | |
| |
| |
| |
Dynamic Methods | |
| |
| |
| |
Case Study: Internet Traffic Matrix Estimation | |
| |
| |
| |
Estimation of Network Flow Costs | |
| |
| |
| |
Link Costs from End-to-end Measurements | |
| |
| |
| |
Path Costs from End-to-end Measurements | |
| |
| |
| |
Additional Related Topics and Reading | |
| |
| |
Exercises | |
| |
| |
| |
Graphical Models | |
| |
| |
| |
Introduction | |
| |
| |
| |
Defining Graphical Models | |
| |
| |
| |
Directed Graphical Models | |
| |
| |
| |
Undirected Graphical Models | |
| |
| |
| |
Inference for Graphical Models | |
| |
| |
| |
Additional Related Topics and Reading | |
| |
| |
Glossary of Notation | |
| |
| |
References | |
| |
| |
Author Index | |
| |
| |
Subject Index | |