random-graph 0.0.0a1
Fast, approximately uniform, random sampling for graphs.

# Random Graphs with Given Degree Sequence

[![Build Status](https://img.shields.io/travis/jamesross2/random_graph/master?logo=travis&style=flat-square)](https://travis-ci.org/jamesross2/random_graph?style=flat-square)
[![Code Coverage](https://img.shields.io/codecov/c/github/jamesross2/random_graph?logo=codecov&style=flat-square&label=codecov)](https://codecov.io/gh/jamesross2/random_graph)
[![Code style: black](https://img.shields.io/badge/code%20style-black-000000.svg?logo=black&style=flat-square)](https://github.com/psf/black)

This is a fast, lightweight, Python package for sampling random graphs. It is designed to generate graphs with a 
given degree sequence approximately uniformly at random. It does this as quickly as possible, for as many degree 
sequences as possible, and as many graph types as possible, including simple, directed, multi-hypergraph, and
bipartite graphs.


<br>

## Package highlights

The `random_graph` package is appropriate for sampling a random graph when a specific degree sequence is required. It is 
optimised for simplicity and speed, and efficiently scales to very large graphs. It presents a set of simple functions 
for standard usage, and more advanced functionality for advanced users.

The sampling algorithm itself is a non-trivial Markov Chain Monte Carlo process (naive sampling algorithms tend to have
exponential algorithmic complexity, and do not scale to even moderately sized problems). Given a degree sequence (or 
bipartite degree sequence), the sampling algorithm first creates a non-random graph with the given degree sequence 
(greedily, and deterministically). It then applies small random transformations ('switches') to the graph. After 
sufficiently many switches, the result is a new graph with the required degree sequence, sampled from the set of all 
possible graphs approximately uniformly at random (well, pseudo-random).

The implementation used here is space and time efficient. On a basic laptop CPU, this package can sample a random graph 
in under a second (it computes well over 100,000 switch operations per second), even for graphs with large numbers of 
nodes and edges. The algorithmic complexity of each iteration is constant relative to the number of edges in the graph, 
and the memory requirements grow linearly with the number of edges in the graph, allowing the package to efficiently 
scale to very large graphs.

 For users wishing to sample graphs 
_without_ any restriction on degree sequence (such as Erdős–Rényi sampling), the very helpful 
[`NetworkX`](https://github.com/networkx/networkx) package is one of many excellent alternatives. We also recommend the 
`NetworkX` package for users wishing to further manipulate the randomly sampled graph.


<br>

## Usage

The convenient top-level functions of the package are the `sample_*_graph` functions, where `*` is one of `simple`, 
`directed`, `multi_hypergraph`, or `bipartite`. For users who desire more control over the sampling process, it is more
than possible to refer to lower-level classes and functions. These are surfaced in the submodules `graphs`, `chain`, and 
`toolbox`, all of which present helpful interfaces to more complex sampling problems. This package has been optimised 
specifically for the purpose of sampling graphs via the switch chain; for other requirements we recommend the 
comprehensive [`NetworkX`](https://github.com/networkx/networkx) package.
 
### Getting started

To begin with, make sure that the package is installed in your environment. (We may upload the package to PyPI later, 
depending on user interest.)

```bash
pip install git+https://github.com/jamesross2/random_graph
```

Next, we need to decide on a degree sequence. We can then sample a random graph from the package using the 
`sample_*` functions.

```python
import random_graph

# degree sequence determines family we will sample from
degree_sequence = (20,) * 5 + (10,) * 50  # 600 edges in total

# sample a simple graph, approximately uniformly at random, from all graphs with given degree sequence
# MCMC occurs under the hood
edges = random_graph.sample_simple_graph(degree_sequence)
```

The resulting `edges` object is a list of edges, although each edge type may change depending on the graph type. For 
simple graphs, as above, the result is a list of `{x, y}` sets; for directed and bipartite graphs, it is a list of 
`(x, y)` tuples; and for multi-hypergraphs it is a list of sets of integers (of possibly varying size). For the 
bipartite case, the vertices `x` and `y` are labelled independently--so that `(0, 0)` is an edge between two distinct
vertices, rather than a loop. 


### Advanced usage

Advanced users may wish to estimate the distribution of some random variable within the state space, such as the 
diameter or number of triangles of a graph. This is straightforward to estimate with the help of a callback function
applied during the resampling stage. Below, we give an example of estimating the proportion of bipartite graphs that are
incidence graphs of simple hypergraphs. 

```python
import random
import random_graph

# setting the random seed will ensure reproducible results
random.seed(708251)

# create a bipartite degree sequence
dx = [100, 90, 80] * 10
dy = [5] * 540
graph = random_graph.graphs.SwitchBipartiteGraph.from_degree_sequence(dx, dy)

# sample the graph, including callback every so often
resampler = random_graph.Chain(graph)
callback_history = resampler.mcmc(
    iterations=int(1e6), 
    callback=lambda g: g.to_multi_hypergraph.simple(), 
    call_every=100, 
    burn_in=int(1e6)
)

# calculate proportion of sampled graphs that are simple
simple_frac = sum(callback_history) / len(callback_history)
print(f"Proportion of sampled bipartite graphs that were H-simple: {100*simple_frac:.1f}%")

# Proportion of sampled graphs that were H-simple: 36.7%
```

The resulting `history` object now contains the MCMC sampling results of our callback function. Using more advanced 
callbacks (such as custom classes that store intermediate states, for example), allows for sufficiently complex sampling
schemes to be employed.

Currently, the number of MCMC iterations is simply set to a default value (which can be specified in the `sample_*` 
call). We hope to add functionality for estimating the number of iterations required to achieve sufficient convergence
to the uniform distribution for a given degree sequence. 


### Integration with NetworkX

For further graph operations with graphs (such as spanning trees, subgraphs, or neighbourhoods), we recommend the 
excellent [`NetworkX`](https://github.com/networkx/networkx) package. Outputs from our graph sampling package can easily
be converted into NetworkX `Graph` objects using the below code.

```python
import random_graph
import networkx as nx

# sample a basic bipartite graph approximately uniformly at random
n, d = 100, 10
edges = random_graph.sample_directed_graph(degree_sequence=((d, d),) * n)

# populate a NetworkX directed graph
graph = nx.DiGraph()
graph.add_nodes_from(range(n))
graph.add_edges_from(edges)
```

The resulting `graph` is a NetworkX directed graph with the desired vertex and edge sets. Other graph types may take 
some additional work; in particular, bipartite graphs require differently labels in the vertex bipartitions.


### More examples

This package was originally developed to count hypergraphs! Look at our [experiments](./experiments) folder for some 
simple projects that make use of the switch chain.


<br>

## Sampling algorithm and efficiency

### Switch chain

The sampling process uses a Markov Chain Monte Carlo (MCMC) process called the 'switch chain'. This chain returns a 
graph from the set of all graphs with the desired degree sequence, by applying random transformations to a graph 
repeatedly. Each transformation (or 'switch') swaps the end points of a pair of edges. The chain is defined in such a 
way that its unique stationary distribution is uniform, and that it converges to this distribution rapidly (i.e. as a 
logarithmic function of the state space size). Hence, the number of iterations grows only polynomially as a function of 
the number of edges, despite the number of graphs growing exponentially. (We are working on an automatic estimation 
process for the number of iterations required.)


### Speed

On a basic laptop CPU, this package can sample a random graph in under a second (it computes well over 100,000 switch 
operations per second), even for graphs with large numbers of nodes and edges. This allows for random graphs to be 
generated efficiently and at scale. Moreover, the speed per iteration has constant algorithmic complexity as a function 
of graph size and the number of edges. Hence, the sampling speed increases only as a function of the number of switches 
applied, and not of the graph itself, making the implementation very scalable to large graphs. 


<br>

## Contributing

We would love your contribution--anything from a [bug report](https://github.com/jamesross2/random_graph/issues/new) to a pull request!


### Setting up

We recommend working in a virtual environment for package development. Use [`direnv`](https://direnv.net/) to 
automatically activate your virtual environment.

```bash
# set up virtual environment, install required packages, and install random_graph
python -m pip install --upgrade pip virtualenv
python -m virtualenv .venv

# use direnv to activate the virtual environment whenever you are in the working directory
echo "source .venv/bin.activate > .envrc"
direnv allow

# install packages into new (activated) virtual environment
pip install -r requirements.txt
pip install -e .
```

All tests should be completed within the virtual environment, to ensure consistency. We test with tox, so any version of
Python3.6+ should work fine.


### Features to build

We would like to add all of the following to our project:

* Asymptotic testing to build a 'suggested runtime' feature for various degree sequences.
* Automatically produce warnings when degree sequences that are not rapidly mixing are provided.
* Command line hooks so that non-Python users can leverage the package directly.


### Testing

After making changes, apply the package formatting rules and check that the package still passes the tests. This is 
achieved easily with the help of our Makefile.

```bash
make help  # check allowable make commands for more information
make format
make test
tox  # check that package passes tests on all tox versions
```

That's it! We would love your contributions or suggestions.


<br>

## References

Greenhill, C. (2014, December). The switch Markov chain for sampling irregular graphs. In _Proceedings of the 
twenty-sixth annual acm-siam symposium on discrete algorithms_ (pp. 1564-1572). Society for Industrial and Applied 
Mathematics.

Erdős, P. L., Mezei, T. R., Miklós, I., & Soltész, D. (2018). Efficiently sampling the realizations of bounded, 
irregular degree sequences of bipartite and directed graphs. _PloS one_, 13(8).

Erdös, P. L., Miklós, I., & Soukup, L. (2010). Towards random uniform sampling of bipartite graphs with given degree 
sequence. arXiv preprint arXiv:1004.2612.