| |
| |
| |
| 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 | |