# bisquik

bisquik randomly samples a graph with a prescribed degree distribution.

It implements the algorithm from Bayati, Kim, and Saberi, 2010 Algorithmica 58(4):860-910 doi:10.1007/s00453-009-9340-1

## Usage

```
bisquik [options] degfile
Generate a random sample of a graph with a prescribed degree
distribution. The program reads the degrees in <degfile>
and generates an asympotically uniform sample of a random graph
with that same degree distribution. If successful, the program
outputs the edges of the graph to <degfile>.<k>.edges where
<k> is the first integer such that <degfile>.<k>.edges does not
exist.
-v, --verbose make the program chattier
-s, --stats collect sampling statistics
The statistics are written to <output>.stats
-d PATH, --dir=PATH change the output directory
The default output name is <degfile>.<k> Given PATH,
bisquik changes the path on <degfile> to PATH,
and searches for the first empty file with name
<PATH>/<degfile without path>.<k>.edges. Changing the
output directory affects all other outputs as well.
-o NAME, --output=NAME the root output name
The default output name is <degfile>.<k> Given NAME,
bisquik searches for the first empty file with name
<NAME>.<k> just like the default behavior. See --fixed
to avoid this behavior.
-n COUNT, --samples=COUNT produce COUNT samples
-t COUNT, --trials=COUNT perform COUNT trials for each sample
Each sample is not
-f NAME, --fixed=NAME a fixed output name.
--graphfile=NAME an explicit graph filename for output
--statsfile=NAME an explicit statistics filename for output
Using this option enables statistics collection
-e, --expo Sample edges with probability: exp(-di*dj/4m)*ri*rj
-a, --approx Sample edges with probability: (1-di*dj/4m)*ri*rj
These are the probability used in the paper.
--seed=<unsigned int> If seed is 0, then the program is seeded
based on the current time (the default).
-p <NVERTS>,<THETA>,<MAXDEG> --powerlaw=<NVERTS>,<THETA>,<MAXDEG>
Ignore degfile and use a synthetically generated power-law
degree distribution.
```

## Degree File Format

The file format is textual and is a list of integers:

```
File: Header\nDegreeList
Header: <int:nverts>
DegreeList: (<int:degree>\n)*nverts
```

For example, here is the degree sequence file for a triangle with one extra node

```
4
2
2
3
1
```

## High level parameters

There are three levels of sampling here:

i) samples - independent realizations of the prescribe degree graph ii) trials - the number of repetitions of the Bayati-Kim-Saberi algorithm until we generate a successful sample iii) edge samples - the number of repetition of the fast edge sampling procedure before reverting to searching for an edge (slow)

for i in xrange(samples): for j in xrange(trials): success = true G = new_graph(degrees) while G.edges_remaining(): for k in xrange(max_edge_samples): found = false if (G.sample_edge()): # try to find an edge quickly found = true break if not found: if G.still_valid(): # check if we made a mistake G.search_for_edge() else: success = false # if we did, quick this trial here break if success: G.write_graph() break # we don't need any other trials

# move on to the next sample

## Return value

The return value of the program is 0 to indicate a successful run. A negative return value indicates an error with the parameters. Also, a positive return value indicates that not all requested samples were generated. The positive value is the number of missing samples.

## Statistics collection

stats to collect:

edge_prob is **sample_prob/4m search is <0> or <1>

## Acknowledgement

This code uses the argparse.h library from Xavier Décoret.

## Notice

Copyright (2011) Sandia Corporation. Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government retains certain rights in this software.

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.