Probabilistic Foundations of Statistical Network Analysis presents a fresh and insightful perspective on the fundamental tenets and major challenges of modern network analysis. Its lucid exposition provides necessary background for understanding the essential ideas behind exchangeable and dynamic neMONOGRAPHS ON STATISTICS ANDAPPLIED PROBABILITYEditors: F. Bunea, P. Fryzlewicz, R. Henderson, N. KeidingT. Louis, R Smith, and W. WongStochastic Analysis for Gaussian Random Processes and FieldsWith Applicationsvidyadhar S. Mandrekar and Leszek gawarecki(2015)145Semialgebraic Statistics and Latent Tree modelsPiotr Zwiernik(2015)146Inferential ModelsReasoning with UncertaintRyan Martin and Chuanhui liu(2016)147Perfect SimulationMark L. Huber (2016)[48State-Space Methods for Time Series Analysisheory, Applications and SoftwareJose Casals, Alfredo Garcia-Hiernaux, Miguel Jerez, Sonia Sotoca,and A. Alexandre trindade (2016)149Hidden markov Models for Time seriesAn Introduction Using R, Second EditionWalter Zucchini, lain L. MacDonald, and Roland Langrock(2016)150Joint Modeling of Longitudinal and Time-to-Event DataRobert M. Elashoff, Gang Li, and Ning Li (2016)151Multi-State Survival Models for Interval-Censored DataArdo van den Hout(2016)152Generalized Linear models with random effectsUnificd Analysis via H-likclihood, Sccond EditionYoungjo Lee, John A Nelder, and Yudi Puwitan (2017)153Absolute riskMethods and Applications in Clinical Management and Public HealthRuth M. Pfeiffer and Mitchell H. Gail(2017)151Asymptotic analysis of Mixed Effects ModelsTheory, Applications, and Open ProblemsJiming jiang (2017)155Missing and Modified Data in Nonparametric EstimationWith R ExamplesSam Efromovich(2017)156Probabilistic Foundations of Statistical Network AnalysisHarry Crane (2018)157For more information about this series please visit:https://www.crcpress.com/chapman--hallcrc-monographs-on-statistics--applied-probabiLity/bookSeriEs/cHmonstAappMonographs on Statistics and applied probability 157ProbabilisticFoundationsof statisticalNetwork AnalysisHarry CraneRutgers UniversityNew Jersey, USACRC CRCPressBoca Raton London New yorkCRC Press is an imprint of theTaylor Francis Group, an informa businessA ChaPman hall bookCRC PressTaylor Francis Group6000 Broken Sound Park way Nw, Suite 300Boca raton FL 33487-2742o 2018 by Taylor Francis Group, LLCCRC Press is an imprint of Taylor Francis Group, an Informa businessNo claim to original u.s. govern ment worksPrinted on acid-free paperVersion date: 20180313International Standard Book Numher-13: 978-1-1385-8599-7(Hardback)International Standard Book Number-13: 978-1-1386-3015-4(Paperback)his book contains information obtained from authentic and highly regarded sources. Reasonableefforts have been made to publish reliable data and information, but the author and publisher cannotassume responsibility for the validity of all materials or the consequences of their use. The authors andovright holders of all materialind apologize to copyright holders if permission to publish in this form has not been obtained. If anycopyright material has not been acknowledged please write and let us know so we may rectify in anyfutiExcept as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced,transmitted, or utilized in any form by any electronic, mechanical, or other means, now known orhereafter invented, including photocopying, microfilming, and recording, or in any informationstorage or retrieval system, without written permission from the publishersFor permission to photocopy or use material electronically from this work, please accesswww.copyright.com(http://www.copyright.com/)orcontacttheCopyrightClearanceCenterInc(CCC), 222 Rosewood Drive, Danvers, MAO1923, 978-750-8400. CCC is a not-for-profit organizationhat provides licenses and registration for a variety of users. For organizations that have been granteda photocopy license by the CCC, a separate system of pay ment has been arrangedTrademark Notice: Product or corporate names may be trademarks or registered trademarks, andare used only for identification and explanation without intent to infringeVisit the Taylor& francis Web site athttp://www.taylorandfrancis.comand the crc Press web site athttp://www.crcpress.comTo Howard and JohnTaylor francisTaylor francis Grouphttp://taylorandfrancis.comContentsAcknowledgments1 Orientation1.1 Analogy: Bernoulli trials1.2 What it is: Graph1.3 How to look at it: Labeling and representation1. 4 Where it comes from: Contextse of it all: Coherence1.6 What we're talking about: Examples of network data81.6.1 Internet1. 6.2 Social networks91. 6.3 Karate club1. 6. 4 Enron101. 6.5 Collaboration networks1.6.6 Blockchain and cryptocurrency networks101.6.7 Other networks16. 8 Some common scenarios1. 7 Major open questions1.7.1 Sparsity1.7.2 Modeling network complexity1.7.3 Sampling issues1.7.4 Modeling network dynamics141. 8 Toward a Probabilistic Foundation for Statistical Network Analysi142 Binary relational data152.1 Scenario: Patterns in international trade172.1.1 Summarizing network structure182.2 Dyad independence model182.3 Exponential random graph models(ERGMs2.4 Scenario: Friendships in a high school212.5 Network inference under sampling2.6 Further reading23VIllllCONTENTS3 Network sampling253.1 Opening example3.2latency273.2.1 Consistency of the PI model3.3 Significance of sampling consistency3.3.1 Toward a coherent framework for network modeling3.4 Selection from sparse networks3.5 Scenario: Ego networks in high school friendships3.6 Network sampling schemes363.6.1 Relational sampling3736.1.1上 dge sampling373.6. 1.2 Hyperedge sampling393.6.1.3 Path sampli3.6.2 Snow ball sampling3.7 Units of observation433.8We sample size?443.9 Consistency under subsampling463.10 Further reading3.11 Solutions to exercises3.11.1 Exercise 3.1483.11.2 Exercise 3.2493. 11. 3 Exercise 3.33.11.4 Exercise 3. 4504 Generative models514.1 Specification of generative models4.2 Generative model 1: Preferential attachment model524.3 Generative model 2: random walk models564.4 Generative model 3: Erdos-Renyi-Gilbert model574.5 Generative model 4: General sequential construction574.6 Further reading585 Statistical modeling paradigm595.1 The quest for coherence5.2 An incoherent model5. 3 What is a statistical model?635.3.1 Population model645.3.2 Finite sample models645.4 Coherence665.4.1 Coherence in sampling models675.4.2 Coherence in generative models685.5 Statistical implications of coherence5.6 Examples5.6.1 Example 1: Erdos-Renyi-Gilbert model under selectionmplingCONTENTS5.6.2 Example 2: ERGM under selection sampling5.6.3 Example 3: Erdos-Renyi-Gilbert model under edge sam-pling5.7 Invariance principles735.8 Further reading5.9 Solutions to exercises755.9.1 Exercise 56 Vertex exchangeable models6.1 Preliminaries: Formal definition of exchangeability6.2 Implications of exchangeability6.3 Finite exchangeable random graphs826.3.1 Exchangeable ergms846. 4 Countable exchtble models6.4.1 Graphon models866. 4.1.1 Generative model866. 4.2 Aldous-H6.4.3 Graphons and vertex exchangeability6.4.4 Subsampling description916.5 Viability of graphon models6.5.1 Implication 1: Dense structure6.5.2 Implication 2: Representative sampling6.5.3 The emergence of graphons976.6 Potential benefits of graphon model6.6.1 Connection to de finetti's theorem6.6.2 Graphon estimation106.7 Further reading1046. 8 Solutions to exercises1046.8.1 Exercise 6.16.8.2 Exercise 6.21056.8.3 Exercise 6.31056.8.4 Exercise 6.41066.8.5 Exercise 6.51076.8.6 Exercise 6.61076.8.7E6.71086.8. 8 Exercise 6.8l087 Getting beyond graphons1117.1 Something must gol127.2 Sparse graphon models1147.3 Completely random measures and graphex models1167.3.1 Scenario: Formation of Facebook friendships1177.3.2 Network representation1187.3.3 Interpretation of vertex labels1197.3.4 Exchangeable point process models120