Moments of uniform random multigraphs with fixed degree sequences

DOI10.1137/19M1288772MaRDI QIDQ5037554zbMATH OpenOpenAlexFDO

Authors Philip Chodrow

Publication date 1 March 2022

Published in SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1909.09037

zbMATH Keywords

Markov chain Monte Carloestimationsocial networksrandom graphscommunity structure

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Random graphs (graph-theoretic aspects) (05C80) Social networks; opinion dynamics (91D30) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: We study the expected adjacency matrix of a uniformly random multigraph with fixed degree sequence $mathbfdinmathbb{Z}_{+}^n$. This matrix arises in a variety of analyses of networked data sets, including modularity-maximization and mean-field theories of spreading processes. Its structure is well-understood for large, sparse, simple graphs: the expected number of edges between nodes $i$ and $j$ is roughly $frac{d}_i{d}_{j}su{m}_{e}ll{d}_{e}ll$. Many network data sets are neither large, sparse, nor simple, and in these cases the standard approximation no longer applies. We derive a novel estimator using a dynamical approach: the estimator emerges from the stationarity conditions of a class of Markov Chain Monte Carlo algorithms for graph sampling. We derive error bounds for this estimator, and provide an efficient scheme with which to compute it. We test the estimator on synthetic and empirical degree sequences, finding that it enjoys relative error against ground truth a full order of magnitude smaller than the standard approximation. We then compare modularity maximization techniques using both the standard and novel estimator, finding that the qualitative structure of the optimization landscape depends significantly on the estimator choice. Our results emphasize the importance of using carefully specified random graph models in data scientific applications.

Recommendations

• The method of moments and degree distributions for network models
• Random graphs with a given degree sequence
• Concentration and regularization of random graphs
• Configuring random graph models with fixed degree sequences
• Fast uniform generation of random graphs with given degree sequences

Cites work

• scientific article; zbMATH DE number 2043967 (Why is no real title available?)
• A critical point for random graphs with a given degree sequence
• A polynomial bound on the mixing time of a Markov chain for sampling regular directed graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• A sequential importance sampling algorithm for generating random graphs with prescribed degrees
• An Exponential Family of Probability Distributions for Directed Graphs
• An efficient MCMC algorithm to sample binary matrices with fixed marginals
• Clustering of sparse data via network communities -- a prototype study of a large online market
• Computing and Combinatorics
• Configuration models of random hypergraphs
• Configuring random graph models with fixed degree sequences
• Connected components in random graphs with given expected degree sequences
• Connected realizations of joint-degree matrices
• Dual variational methods in critical point theory and applications
• Elements of Information Theory
• Fast unfolding of communities in large networks
• Fast uniform generation of regular graphs
• Limit laws for self-loops and multiple edges in the configuration model
• Making multigraphs simple by a sequence of double edge swaps
• Maximum likelihood estimation in the -model
• Mountain passes and saddle points
• On Finding Graph Clusterings with Maximum Modularity
• Random graphs with a given degree sequence
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• The average distances in random graphs with given expected degrees
• The mixing time of switch Markov chains: a unified approach
• The number of graphs and a random graph with a given degree sequence
• The switch Markov chain for sampling irregular graphs (extended abstract)
• Uncovering space-independent communities in spatial networks
• Uniform generation of random regular graphs of moderate degree

Cited in

(1)

• Limitations of Chung Lu random graph generation

This page was built for publication: Moments of uniform random multigraphs with fixed degree sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5037554)