Dedication
Preface
Acknowledgements
1.Orientation
Analogy: Bernoulli trials
What it is: Graphs vs Networks
Moving beyond graphs
How to look at it: Labeling and representation
Where it comes from: Context
Making sense of it all: Coherence
What were talking about: Common examples of network data
Internet
Social networks
Karate club
Enron email corpus
Collaboration networks
Other networks
Some common scenarios
Major Open Questions
Sparsity
Modeling network complexity
Sampling issues
Modeling temporal variation
Chapter synopses and reading guide
Binary relational data
Network sampling
Generative models
Statistical modeling paradigm
Vertex exchangeable models
Getting beyond graphons
Relatively exchangeable models
Edge exchangeable models
Relationally exchangeable models
DEDICATION
Dynamic network models
1.Binary relational data
Scenario: Patterns in international trade
Summarizing network structure
Dyad independence model
Exponential random graph models (ERGMs)
Scenario: Friendships in a high school
Network inference under sampling
Further reading
1.Network sampling
Opening example
Consistency under selection
Consistency in the p model
Significance of sampling consistency
Toward a coherent framework of network modeling
Selection from sparse networks
Scenario: Ego networks in high school friendships
Network sampling schemes
Relational sampling
Edge sampling
Hyperedge sampling
Path sampling
Snowball sampling
Units of observation
What is the sample size?
Consistency under subsampling
Further reading
1.Generative models
Specification of generative models
Preferential Attachment model
Random walk models
Erd?os-R´enyi-Gilbert model
General sequential construction
Further reading
1.Statistical modeling paradigm
The quest for coherence
An incoherent model
What is a statistical model?
Population model
Finite sample models
Coherence
Coherence in sampling models
Coherence in generative models
Statistical implications of coherence
Examples
Erd?os-R´enyi-Gilbert model under selection sampling
ERGM with selection sampling
Erd?os-R´enyi-Gilbert model under edge sampling
Invariance principles
Further reading
1.Vertex exchangeable models
Preliminaries: Formal definition of exchangeability
Implications of exchangeability
Finite exchangeable random graphs
Exchangeable ERGMs
Countable exchangeable models
Graphon models
Generative model
Exchangeability of graphon models
Aldous-Hoover theorem
Graphons and vertex exchangeability
Subsampling description
Viability of graphon models
Implication: Dense structure
Implication: Representative sampling
The emergence of graphons
Potential benefits of graphon models
Connection to de Finettis theorem
Graphon estimation
Further reading
1.Getting beyond graphons
Something must go
Sparse graphon models
Completely random measures and graphex models
Scenario: Formation of Facebook friendships
Network representation
Interpretation of vertex labels
Exchangeable point process models
Graphex representation
Sampling context
Further discussion
Variants of invariance
Relatively exchangeable models
DEDICATION
Edge exchangeable models
Relationally exchangeable models
1.Relatively exchangeable models
Scenario: heterogeneity in social networks
Stochastic blockmodels
Generalized blockmodels
Community detection and Bayesian versions of SBM
Beyond SBMs and community detection
Relative exchangeability with respect to another network
Scenario: high school social network revisited
Exchangeability relative to a social network
Lack of interference
Label equivariance
Latent space models
Relatively exchangeable random graphs
Relatively exchangeable f-processes
Relative exchangeability under arbitrary sampling
Final remarks and further reading
1.Edge exchangeable models
Scenario: Monitoring phone calls
Edge-centric view
Edge exchangeability
Interaction propensity process
Characterizing edge exchangeable random graphs
Vertex components models
Stick-breaking constructions for vertex components
Hollywood model
The Hollywood process
Role of parameters in the Hollywood model
Statistical properties of the Hollywood model
Prediction from the Hollywood model
Thresholding
Contexts for edge sampling
Concluding remarks
Connection to graphex models
Further reading
1.Relationally exchangeable models
Sampling multiway interactions (hyperedges)
Collaboration networks
Coauthorship networks
Representing multiway interaction networks
Hyperedge exchangeability
Interaction propensity process
Characterization for hyperedge exchangeable networks
Scenario: Traceroute sampling of Internet topology
Representing the data
Path exchangeability
Relational exchangeability
General Hollywood model
Markovian vertex components models
Concluding remarks and further reading
1.Dynamic network models
Scenario: Dynamics in social media activity
Modeling considerations
Network dynamics: Markov property
Modeling the initial state
Is the Markov property a good assumption?
Temporal Exponential Random Graph Model (TERGM)
Projectivity and sampling
Example: a TERGM for triangle counts
Projective Markov property
Rewiring chains and Markovian graphons
Exchangeable rewiring processes (Markovian graphons)
Graph-valued L´evy processes
Inference from graph-valued L´evy processes
Continuous time processes
Poissonian construction
Further reading
Bibliography
Index