The Library
Constructing and sampling directed graphs with given degree sequences
Tools
Tools
Tools
Kim, H, Del Genio, Charo I., Bassler, K E and Toroczkai, Z (2012) Constructing and sampling directed graphs with given degree sequences. New Journal of Physics, Vol. 14 (No. 2). 023012. doi:10.1088/1367-2630/14/2/023012 ISSN 1367-2630.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1088/1367-2630/14/2/023012
Abstract
he interactions between the components of complex networks are often directed. Proper modeling of such systems frequently requires the construction of ensembles of digraphs with a given sequence of in- and out-degrees. As the number of simple labeled graphs with a given degree sequence is typically very large even for short sequences, sampling methods are needed for statistical studies. Currently, there are two main classes of methods that generate samples. One of the existing methods first generates a restricted class of graphs and then uses a Markov chain Monte-Carlo algorithm based on edge swaps to generate other realizations. As the mixing time of this process is still unknown, the independence of the samples is not well controlled. The other class of methods is based on the configuration model that may lead to unacceptably many sample rejections due to self-loops and multiple edges. Here we present an algorithm that can directly construct all possible realizations of a given bi-degree sequence by simple digraphs. Our method is rejection-free, guarantees the independence of the constructed samples and provides their weight. The weights can then be used to compute statistical averages of network observables as if they were obtained from uniformly distributed sampling or from any other chosen distribution.
| Item Type: | Journal Article | ||||
|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||
| Journal or Publication Title: | New Journal of Physics | ||||
| Publisher: | Institute of Physics Publishing Ltd. | ||||
| ISSN: | 1367-2630 | ||||
| Official Date: | 2012 | ||||
| Dates: |
|
||||
| Volume: | Vol. 14 | ||||
| Number: | No. 2 | ||||
| Page Range: | 023012 | ||||
| DOI: | 10.1088/1367-2630/14/2/023012 | ||||
| Status: | Peer Reviewed | ||||
| Publication Status: | Published | ||||
| Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
