Sparse Graphs Using Exchangeable Random Measures
Open accessThe DOI matches its Crossref record; 16 of the 16 references it cites were found in a registry or an index.
Abstract
Summary: Statistical network modelling has focused on representing the graph as a discrete structure, namely the adjacency matrix. When assuming exchangeability of this array—which can aid in modelling, computations and theoretical analysis—the Aldous–Hoover theorem informs us that the graph is necessarily either dense or empty. We instead consider representing the graph as an exchangeable random measure and appeal to the Kallenberg representation theorem for this object. We explore using completely random measures (CRMs) to define the exchangeable random measure, and we show how our CRM construction enables us to achieve sparse graphs while maintaining the attractive properties of exchangeability. We relate the sparsity of the graph to the Lévy measure defining the CRM. For a specific choice of CRM, our graphs can be tuned from dense to sparse on the basis of a single parameter. We present a scalable Hamiltonian Monte Carlo algorithm for posterior inference, which we use to analyse network properties in a range of real data sets, including networks with hundreds of thousands of nodes and millions of edges.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The anatomy of a large-scale hypertextual Web search engine
Brin, S., & Page, L. (1998) · Computer Networks and ISDN Systems · doi:10.1016/s0169-7552(98)00110-x · Cited by 16,004
Gephi: An Open Source Software for Exploring and Manipulating Networks
Bastian, M., Heymann, S., & Jacomy, M. (2009) · Proceedings of the International AAAI Conference on Web and Social Media · doi:10.1609/icwsm.v3i1.13937 · Cited by 11,675
Power-Law Distributions in Empirical Data
Clauset, A., Shalizi, C. R., & Newman, M. E. J. (2009) · SIAM Review · doi:10.1137/070710111 · Cited by 8,019
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272
Newman, M. (2010) · doi:10.1093/acprof:oso/9780199206650.001.0001 · Cited by 6,595
General methods for monitoring convergence of iterative simulations
Brooks, S. P., & Gelman, A. (1998) · Journal of Computational and Graphical Statistics · doi:10.1080/10618600.1998.10474787 · Cited by 6,045
Bollobás, B. (2001) · doi:10.1017/cbo9780511814068 · Cited by 2,639 · cited 1×
“E-mail: caron@stats.ox.ac.uk 1296 F. Caron and E. B. Fox Bollobás (2001), Durrett (2007), Goldenberg et al. (2010) and Fienberg (2012).”
The political blogosphere and the 2004 U.S. election: divided they blog
Adamic, L. A., & Glance, N. (2005) · Proceedings of the 3rd international workshop on Link discovery · doi:10.1145/1134271.1134277 · Cited by 2,619
MCMC Using Hamiltonian Dynamics
Neal, R. M. (2011) · Handbook of Markov Chain Monte Carlo · doi:10.1201/b10905-6 · Cited by 2,574
Penrose, M. (2003) · doi:10.1093/acprof:oso/9780198506263.001.0001 · Cited by 2,480
Stochastic blockmodels and community structure in networks
Karrer, B., & Newman, M. E. J. (2011) · Physical Review E · doi:10.1103/physreve.83.016107 · Cited by 2,025
Clustering in weighted networks
Opsahl, T., & Panzarasa, P. (2009) · Social Networks · doi:10.1016/j.socnet.2009.02.002 · Cited by 1,037 · cited 1×
“com/datasets/) (Opsahl and Panzarasa, 2009); (e) yeast—yeast protein interaction network (http://www.”
Communicability in complex networks
Estrada, E., & Hatano, N. (2008) · Physical Review E · doi:10.1103/physreve.77.036111 · Cited by 719
GABAergic Hub Neurons Orchestrate Synchrony in Developing Hippocampal Networks
Bonifazi, P., Goldin, M., Picardo, M. A., Jorquera, I., Cattani, A., Bianconi, G., Represa, A., Ben-Ari, Y., & Cossart, R. (2009) · Science · doi:10.1126/science.1175509 · Cited by 695
Comparison of co-expression measures: mutual information, correlation, and model based indices
Song, L., Langfelder, P., & Horvath, S. (2012) · BMC Bioinformatics · doi:10.1186/1471-2105-13-328 · Cited by 460
Entropy measures for networks: Toward an information theory of complex topologies
Anand, K., & Bianconi, G. (2009) · Physical Review E · doi:10.1103/physreve.80.045102 · Cited by 368
Metadata
- Authors
- Caron, F., & Fox, E. B.
- Venue
- Journal of the Royal Statistical Society Series B: Statistical Methodology
- Publisher
- Oxford University Press (OUP)
- Published
- 2017-09-23
- Volume
- 79
- Issue
- 5
- Pages
- 1295-1366
- ISSN
- 1369-7412
- 1467-9868
- OpenAlex
- W2963730104
- Cited by
- 170
- References
- 16
- Type
- other
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.