Constructing and sampling directed graphs with given degree sequences

Hyunju Kim, Charo del Genio, Kevin Bassler, Zoltán Toroczkai

Research output: Contribution to journalArticle

40 Citations (Scopus)
6 Downloads (Pure)

Abstract

The 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, 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.
Original languageEnglish
Article number023012
Number of pages23
JournalNew Journal of Physics
Volume14
DOIs
Publication statusPublished - 6 Feb 2012

Fingerprint

Degree Sequence
Directed Graph
Rejection
Digraph
Mixing Time
Markov Chain Monte Carlo Algorithms
Swap
Sampling Methods
Graph in graph theory
Complex Networks
Ensemble
Unknown
Configuration
Interaction
Modeling
Class
Independence
Model

Cite this

Constructing and sampling directed graphs with given degree sequences. / Kim, Hyunju; del Genio, Charo; Bassler, Kevin; Toroczkai, Zoltán.

In: New Journal of Physics, Vol. 14, 023012, 06.02.2012.

Research output: Contribution to journalArticle

Kim, Hyunju ; del Genio, Charo ; Bassler, Kevin ; Toroczkai, Zoltán. / Constructing and sampling directed graphs with given degree sequences. In: New Journal of Physics. 2012 ; Vol. 14.
@article{604a0fe76e2e47b388f726651eefc2b2,
title = "Constructing and sampling directed graphs with given degree sequences",
abstract = "The 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, 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.",
author = "Hyunju Kim and {del Genio}, Charo and Kevin Bassler and Zolt{\'a}n Toroczkai",
year = "2012",
month = "2",
day = "6",
doi = "10.1088/1367-2630/14/2/023012",
language = "English",
volume = "14",
journal = "New Journal of Physics",

}

TY - JOUR

T1 - Constructing and sampling directed graphs with given degree sequences

AU - Kim, Hyunju

AU - del Genio, Charo

AU - Bassler, Kevin

AU - Toroczkai, Zoltán

PY - 2012/2/6

Y1 - 2012/2/6

N2 - The 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, 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.

AB - The 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, 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.

UR - https://charodelgenio.weebly.com/directed-graph-sampling.html

U2 - 10.1088/1367-2630/14/2/023012

DO - 10.1088/1367-2630/14/2/023012

M3 - Article

VL - 14

JO - New Journal of Physics

JF - New Journal of Physics

M1 - 023012

ER -