Probability Seminar: Harry Crane, Rutgers University
Probabilistic symmetries in networks
I discuss various refinements and extensions of the principle of exchangeability, focusing on 3 specific cases:
1. Relative exchangeability, by which the distribution of a random graph is invariant with respect to the symmetries of some other structure.
2. Combinatorial Markov processes for temporally varying networks.
3. Edge exchangeable random graphs, a new invariance principle that resolves a major challenge in modeling network datasets that are sparse and/or exhibit power law degree distributions.
Each case leads to a characterization theorem that parallels prior work by Aldous-Hoover-Kallenberg (in case 1), Levy-Ito-Khintchine (in case 2), and de Finetti and Kingman (in case 3). Though the discussion applies more generally, I phrase much of the presentation in the specific context of random graphs.