Statistical Analysis of Networks

• Autore: Avrachenkov Konstantin
• Pubblicazione: Norwell, MA : , : Now Publishers, , 2022; ©2022
• Edizione: 1st ed.
• Descrizione fisica: 1 electronic resource (237 p.)
• Disciplina: 003
• Soggetto topico: Networking standards & protocols
• Soggetto non controllato: Network analysis, statistical analysis, network modeling, community detection, graph-based semi-supervised learning, sampling in networks
• Altri autori: DrevetonMaximilien
• Nota di contenuto: Cover -- STATISTICAL ANALYSIS OF NETWORKS -- Copyright -- Dedication -- Table of Contents -- Preface -- Chapter 1: Introduction -- Examples of Networks -- Social networks -- Face-to-face interaction networks -- Communication networks -- Information and collaboration networks -- Biological networks -- Geometrically defined network topologies -- Unifying Properties of Complex Networks -- What are the Properties Commonly Shared by Networks? -- Sparsity -- Connectivity -- Small world -- Edge transitivity -- Heavy-tailed degree distribution -- How do these Properties Arise? -- Erd˝os-Rényi random graphs -- Random geometric graphs -- Preferential attachment models -- What Are the Statistical Problems Related to Networks? -- How to Cluster Network Nodes? -- Which Nodes are Most Important in a Network? -- How to Infer Important Information in a Network? -- Book Organisation -- Book Bibliographic Position -- Funding -- Chapter 2: Random Graph Models -- Erd˝os-Rényi Random Graphs -- Definition -- Degree Distribution -- Phase Transition Phenomena -- Heuristic -- Main statements -- Proof of the connectivity phase transition -- Other Random Graph Models -- Configuration Model -- Preferential Attachment Model -- Motivation -- Model definition -- Degree distribution of the preferential attachment model -- Spatial Networks: Random Geometric Graphs, etc -- Summary -- Clustered Random Graphs: Block Models -- Stochastic Block Model -- Degree-corrected Stochastic Block Model -- Popularity Adjusted Block Model -- Exponential Random Graph Model -- Definition and First Examples -- The p1 Model -- Relationship Between θ and the log-odds -- Further Notes -- Chapter 3: Network Centrality Indices -- Overview of Centrality Indices -- Distance Based Centrality Indices -- Spectral Centrality Indices -- Hitting Time Based Centrality Indices -- Betweenness Centrality Indices. ; Game Theory Based Centrality Indices -- Axiomatic Comparison of Centrality Indices -- Applications of Centrality Indices -- Social, Bibliographic and Information Networks -- Semi-supervised Learning -- Community Detection -- Further Applications -- Further Notes -- Chapter 4: Community Detection in Networks -- Cut-based Methods -- Graph Bisection -- First relaxation method: Laplacian spectral clustering -- General Case: More Than Two Clusters -- Semi-definite Programming -- Discussion -- Complexity of spectral clustering -- Performance of spectral clustering on real data sets -- Spectral methods and dangling trees -- Modularity-based Methods -- Definition -- Efficient computation of modularity -- Greedy Algorithm -- Louvain Algorithm -- Discussion -- Bayesian Community Detection -- An Over-fitting Issue? -- Principled Approach -- Markov Chain Monte Carlo Algorithm -- Numerical Results -- Theoretical Analysis -- Modularity and Maximum A Posteriori Estimator -- Normalized Spectral Clustering as a Continuous Relaxation of Modularity Maximisation -- Information-theoretic Results for Consistent Recovery inSBMs -- Non-binary SBMs -- Information-theoretic conditions for consistent recovery -- Application to binary SBMs -- Other Particular Cases of Non-binary SBMs -- Consistency of Spectral Methods in SBM -- Heuristic: mean-field model -- Consistency of spectral clustering in SBM -- Further Notes -- Chapter 5: Graph-based Semi-supervised Learning -- Laplacian-based SSL Methods -- Label Propagation -- Label Spreading -- Generalized Laplacian -- Numerical Performance of the Laplacian-based Methods -- Learning with Small Amount of Labelled Data -- The Problem of Small Labelled Data -- Poisson Learning -- Numerical Experiments -- Other Methods -- Constrained Spectral Clustering -- Laplacian Regularization -- l1-based Methods: Sparse Label Propagation. ; Bayesian Approach to SSL and Its Theoretical Analysis -- MAP Estimator for DC-SBM with a Noisy Oracle -- Continuous Relaxation -- Upper Bound on the Number of Misclassified Nodes -- Numerical Results -- Further Notes -- Chapter 6: Community Detection in Temporal Networks -- A General Model of Temporal Networks withCommunities -- Membership and Interaction Structures -- Examples of Temporal Network Models -- Networks with Static Community Memberships -- Recovery Thresholds in SBM with Markov Interaction -- Online Likelihood-based Algorithms for MarkovDynamics -- Numerical results -- Spectral Methods for Clustering Temporal Networks -- Maximum likelihood estimator -- Numerical results -- Clustering for Long Time Horizon Using EmpiricalTransition Rates -- Markovian Evolution of Community Memberships -- Variational Expectation-Maximization Algorithm -- Belief Propagation Using the Space-time Graph -- Online Inference as a Semi-supervised Problem -- The lagging problem -- Degree-corrected Temporal SBM with MarkovCommunity Memberships -- Online Maximum A Posteriori estimator -- Continuous relaxation of the MAP -- Numerical experiments -- Further Notes -- Chapter 7: Sampling in Networks -- Overview of Sampling Methods -- Independent Uniform Sampling -- Snowball Sampling -- Metropolis-Hastings Sampling -- Respondent-driven Sampling -- Respondent-driven Sampling with Uniform Jumps -- Ratio with Tours Estimator -- Tour-based Estimators for Motif Counting -- Numerical Comparison of Sampling Methods -- Synthetic Networks -- Real-world Network: DBLP -- Further Notes -- Appendix A: Background Material from Probability,Linear Algebra and Graph Theory -- Probability -- Probability Toolbox -- Basic Probability Laws -- Concentration of Random Variables -- First moment inequalities -- Second moment inequalities -- Concentration of sums of i.i.d. random variables. ; Graph Theory -- Definitions, Vocabulary -- Adjacency Matrix -- Graph Laplacians -- Basic properties of the Laplacians -- Standard Laplacian and the number of connected components -- Linear Algebra -- Symmetric Matrices -- Norms -- Vector norms -- Matrix norms (Serre, 2010) -- Courant-Fisher Theorem -- Calculus on Graphs -- Basic Reminders -- Extension on Graphs -- Functions on graph -- Differential graphs operators -- Appendix B: Additional Lemmas Related to theProof of Theorem 5.5 -- Mean-field Solution of the Secular Equation (5.19) -- Spectral Study of a Perturbed Rank-2 Matrix -- Estimation of y* -- Concentration of y* -- Mean-field Solution of the Constrained Linear System (5.17) -- References -- Index -- About the Authors.
• Sommario/riassunto: This book is a general introduction to the statistical analysis of networks, and can serve both as a research monograph and as a textbook. Numerous fundamental tools and concepts needed for the analysis of networks are presented, such as network modeling, community detection, graph-based semi-supervised learning and sampling in networks. The description of these concepts is self-contained, with both theoretical justifications and applications provided for the presented algorithms. Researchers, including postgraduate students, working in the area of network science, complex network analysis, or social network analysis, will find up-to-date statistical methods relevant to their research tasks. This book can also serve as textbook material for courses related to the statistical approach to the analysis of complex networks. In general, the chapters are fairly independent and self-supporting, and the book could be used for course composition “à la carte”. Nevertheless, Chapter 2 is needed to a certain degree for all parts of the book. It is also recommended to read Chapter 4 before reading Chapters 5 and 6, but this is not absolutely necessary. Reading Chapter 3 can also be helpful before reading Chapters 5 and 7. As prerequisites for reading this book, a basic knowledge in probability, linear algebra and elementary notions of graph theory is advised. Appendices describing required notions from the above mentioned disciplines have been added to help readers gain further understanding.
• Titolo autorizzato: Statistical Analysis of Networks
• ISBN: 1-63828-051-7
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910637694203321
• Lo trovi qui: Univ. Federico II
• Serie: NowOpen Series