Controlled markovian dynamics of graphs: Unbiased generation of random graphs with prescribed topological properties

E. S. Roberts; Alessia Annibale; Ton Coolen

doi:10.1007/978-1-4614-9161-3_4

Controlled markovian dynamics of graphs: Unbiased generation of random graphs with prescribed topological properties

E. S. Roberts^*, Alessia Annibale, Ton Coolen

^*Corresponding author for this work

King's College London

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

1 Citation (Scopus)

Abstract

We analyze the properties of degree-preserving Markov chains based on elementary edge switchings in undirected and directed graphs. We give exact yet simple formulas for the mobility of a graph (the number of possible moves) in terms of its adjacency matrix. This formula allows us to define acceptance probabilities for edge switchings such that the Markov chains become controlled Glauber-type detailed balance processes, designed to evolve to any required invariant measure (representing the asymptotic frequencies with which the allowed graphs are visited during the process).

Original language	English
Title of host publication	Nonlinear Maps and their Applications - Selected Contributions from the NOMA 2011 International Workshop
Publisher	Springer New York LLC
Pages	25-34
Number of pages	10
Volume	57
ISBN (Print)	9781461491606
DOIs	https://doi.org/10.1007/978-1-4614-9161-3_4
Publication status	Published - 2014
Event	3rd International Workshop on Nonlinear Maps and Their Applications, NOMA 2011 - Évora, Portugal Duration: 15 Sept 2011 → 16 Sept 2011

Conference

Conference	3rd International Workshop on Nonlinear Maps and Their Applications, NOMA 2011
Country/Territory	Portugal
City	Évora
Period	15/09/2011 → 16/09/2011

Access to Document

10.1007/978-1-4614-9161-3_4

Cite this

@inbook{8de05138076545a0bd11bf8aef1f7608,

title = "Controlled markovian dynamics of graphs: Unbiased generation of random graphs with prescribed topological properties",

abstract = "We analyze the properties of degree-preserving Markov chains based on elementary edge switchings in undirected and directed graphs. We give exact yet simple formulas for the mobility of a graph (the number of possible moves) in terms of its adjacency matrix. This formula allows us to define acceptance probabilities for edge switchings such that the Markov chains become controlled Glauber-type detailed balance processes, designed to evolve to any required invariant measure (representing the asymptotic frequencies with which the allowed graphs are visited during the process).",

author = "Roberts, {E. S.} and Alessia Annibale and Ton Coolen",

year = "2014",

doi = "10.1007/978-1-4614-9161-3_4",

language = "English",

isbn = "9781461491606",

volume = "57",

pages = "25--34",

booktitle = "Nonlinear Maps and their Applications - Selected Contributions from the NOMA 2011 International Workshop",

publisher = "Springer New York LLC",

note = "3rd International Workshop on Nonlinear Maps and Their Applications, NOMA 2011 ; Conference date: 15-09-2011 Through 16-09-2011",

}

Roberts, ES, Annibale, A & Coolen, T 2014, Controlled markovian dynamics of graphs: Unbiased generation of random graphs with prescribed topological properties. in Nonlinear Maps and their Applications - Selected Contributions from the NOMA 2011 International Workshop. vol. 57, Springer New York LLC, pp. 25-34, 3rd International Workshop on Nonlinear Maps and Their Applications, NOMA 2011, Évora, Portugal, 15/09/2011. https://doi.org/10.1007/978-1-4614-9161-3_4

Controlled markovian dynamics of graphs: Unbiased generation of random graphs with prescribed topological properties. / Roberts, E. S.; Annibale, Alessia ; Coolen, Ton.
Nonlinear Maps and their Applications - Selected Contributions from the NOMA 2011 International Workshop. Vol. 57 Springer New York LLC, 2014. p. 25-34.

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › peer-review

TY - CHAP

T1 - Controlled markovian dynamics of graphs

T2 - 3rd International Workshop on Nonlinear Maps and Their Applications, NOMA 2011

AU - Roberts, E. S.

AU - Annibale, Alessia

AU - Coolen, Ton

PY - 2014

Y1 - 2014

N2 - We analyze the properties of degree-preserving Markov chains based on elementary edge switchings in undirected and directed graphs. We give exact yet simple formulas for the mobility of a graph (the number of possible moves) in terms of its adjacency matrix. This formula allows us to define acceptance probabilities for edge switchings such that the Markov chains become controlled Glauber-type detailed balance processes, designed to evolve to any required invariant measure (representing the asymptotic frequencies with which the allowed graphs are visited during the process).

AB - We analyze the properties of degree-preserving Markov chains based on elementary edge switchings in undirected and directed graphs. We give exact yet simple formulas for the mobility of a graph (the number of possible moves) in terms of its adjacency matrix. This formula allows us to define acceptance probabilities for edge switchings such that the Markov chains become controlled Glauber-type detailed balance processes, designed to evolve to any required invariant measure (representing the asymptotic frequencies with which the allowed graphs are visited during the process).

UR - http://www.scopus.com/inward/record.url?scp=84927615491&partnerID=8YFLogxK

U2 - 10.1007/978-1-4614-9161-3_4

DO - 10.1007/978-1-4614-9161-3_4

M3 - Conference paper

AN - SCOPUS:84927615491

SN - 9781461491606

VL - 57

SP - 25

EP - 34

BT - Nonlinear Maps and their Applications - Selected Contributions from the NOMA 2011 International Workshop

PB - Springer New York LLC

Y2 - 15 September 2011 through 16 September 2011

ER -

Controlled markovian dynamics of graphs: Unbiased generation of random graphs with prescribed topological properties

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this