# State-Dependent Kernel Selection for Conditional Sampling of Graphs

@article{Scott2018StateDependentKS, title={State-Dependent Kernel Selection for Conditional Sampling of Graphs}, author={James Scott and Axel Gandy}, journal={Journal of Computational and Graphical Statistics}, year={2018}, volume={29}, pages={847 - 858} }

Abstract This article introduces new efficient algorithms for two problems: sampling conditional on vertex degrees in unweighted graphs, and conditional on vertex strengths in weighted graphs. The resulting conditional distributions provide the basis for exact tests on social networks and two-way contingency tables. The algorithms are able to sample conditional on the presence or absence of an arbitrary set of edges. Existing samplers based on MCMC or sequential importance sampling are… Expand

#### Supplemental Code

#### Topics from this paper

#### References

SHOWING 1-10 OF 56 REFERENCES

Sampling for Conditional Inference on Network Data

- Mathematics
- 2013

Random graphs with given vertex degrees have been widely used as a model for many real-world complex networks. However, both statistical inference and analytic study of such networks present great… Expand

A Sequential Importance Sampling Algorithm for Generating Random Graphs with Prescribed Degrees

- Mathematics, Computer Science
- Internet Math.
- 2011

An extension of a combinatorial characterization due to Erdős and Gallai is used to develop a sequential algorithm for generating a random labeled graph with a given degree sequence, which allows for surprisingly efficient sequential importance sampling. Expand

Random graphs with arbitrary degree distributions and their applications.

- Mathematics, Physics
- Physical review. E, Statistical, nonlinear, and soft matter physics
- 2001

It is demonstrated that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph. Expand

An Efficient MCMC Algorithm to Sample Binary Matrices with Fixed Marginals

- Mathematics
- 2008

Uniform sampling of binary matrices with fixed margins is known as a difficult problem. Two classes of algorithms to sample from a distribution not too different from the uniform are studied in the… Expand

Conditional Inference on Tables With Structural Zeros

- Mathematics
- 2007

We develop a set of sequential importance sampling (SIS) strategies for sampling nearly uniformly from two-way zero-one or contingency tables with fixed marginal sums and a given set of structural… Expand

An Exponential Family of Probability Distributions for Directed Graphs

- Mathematics
- 1981

Abstract Directed graph (or digraph) data arise in many fields, especially in contemporary research on structures of social relationships. We describe an exponential family of distributions that can… Expand

Markov chain Monte Carlo exact inference for social networks

- Mathematics, Computer Science
- Soc. Networks
- 2007

It is shown how one of the proposed Metropolis–Hastings algorithms can be modified to generate from the conditional distribution of the triad census given the in-degrees, the out-degree and the number of mutual dyads. Expand

Enumeration and simulation methods for 0–1 matrices with given marginals

- Mathematics
- 1991

Data in the form of zero-one matrices where conditioning on the marginals is relevant arise in diverse fields such as social networks and ecology; directed graphs constitute an important special… Expand

A Sequential Algorithm for Generating Random Graphs

- Mathematics, Computer Science
- Algorithmica
- 2009

A nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range and it is shown that for d=O(n1/2−τ), the algorithm can generate an asymptotically uniform d-regular graph. Expand

Markov chain Monte Carlo exact tests for incomplete two-way contingency tables

- Mathematics
- 2005

We consider testing the quasi-independence hypothesis for two-way contingency tables which contain some structural zero cells. For sparse contingency tables where the large sample approximation is… Expand