Network Representation Using Graph Root Distributions

Abstract

Exchangeable random graphs serve as an important probabilistic framework for the statistical analysis of network data. In this work we develop an alternative parameterization for a large class of exchangeable random graphs, where the nodes are independent random vectors in a linear space equipped with an indefinite inner product, and the edge probability between two nodes equals the inner product of the corresponding node vectors. Therefore, the distribution of exchangeable random graphs in this subclass can be represented by a node sampling distribution on this linear space, which we call the graph root distribution. We study existence and identifiability of such representations, the topological relationship between the graph root distribution and the exchangeable random graph sampling distribution, and estimation of graph root distributions.

arXiv comment47 pages, 7 figures

References in corpus (13)

• Stochastic blockmodels and community structure in networks
• Matrix estimation by Universal Singular Value Thresholding
• Fast community detection by SCORE
• Modeling homophily and stochastic equivalence in symmetric relational data
• Rate-optimal graphon estimation
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Sparse graphs using exchangeable random measures
• Nonparametric graphon estimation
• Statistical inference on random dot product graphs: a survey
• Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces
• A Consistent Histogram Estimator for Exchangeable Graph Models
• Asymptotic equivalence of functional linear regression and a white noise inverse problem
• Spectral Clustering for Multiple Sparse Networks: I

Cited by in corpus (7)

• Convergence and Concentration of Empirical Measures under Wasserstein Distance in Unbounded Functional Spaces
• Bootstrapping Networks with Latent Space Structure
• On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models
• Unseeded low-rank graph matching by transform-based unsupervised point registration
• The Importance of Being Correlated: Implications of Dependence in Joint Spectral Inference across Multiple Networks
• Consistent polynomial-time unseeded graph matching for Lipschitz graphons
• Manifold structure in graph embeddings