Different flavors of randomness: comparing random graph models with fixed degree sequences

Wolfgang E. Schlauch*, Emőke Ágnes Horvát, Katharina A. Zweig

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

When a structural characteristic of a network is measured, the observed value needs to be compared to its expected value in a random graph model to assess the statistical significance of its occurrence. The random graph model with which the observed graph is compared is chosen to be structurally similar to the real-world network in some aspects and totally random in all others. To make the analysis of the expected value amenable, the random graph model is also chosen to be as simple as possible. The most common random graph models maintain the degree sequence of the observed graph or at least approximate it. In cases where multi-edges and self-loops are not allowed, typically the fixed degree sequence model (FDSM) is used. Since it is computationally expensive, in this article, we discuss whether one of the following three approximative models can replace it: the configuration model, its simplified version (eCFG), and the mathematical approximation we term simple independence model. While the latter models are more scalable than the FDSM, we show that there are several networks for which they cannot be meaningfully applied. We investigate based on some examples whether, and if so in which cases, these approximating models can replace the computationally more involved FDSM.

Original languageEnglish (US)
Article number36
Pages (from-to)1-14
Number of pages14
JournalSocial Network Analysis and Mining
Volume5
Issue number1
DOIs
StatePublished - Jan 1 2015

Keywords

  • Average neighbor degree
  • Co-occurrence
  • Complex networks
  • Random graph models

ASJC Scopus subject areas

  • Information Systems
  • Communication
  • Media Technology
  • Human-Computer Interaction
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Different flavors of randomness: comparing random graph models with fixed degree sequences'. Together they form a unique fingerprint.

Cite this