A review of graph and network complexity from an algorithmic information perspective

Hector Zenil*, Narsis A. Kiani, Jesper Tegnér

*Corresponding author for this work

Research output: Contribution to journalReview articlepeer-review

43 Scopus citations


Information-theoretic-based measures have been useful in quantifying network complexity. Here we briefly survey and contrast (algorithmic) information-theoretic methods which have been used to characterize graphs and networks. We illustrate the strengths and limitations of Shannon's entropy, lossless compressibility and algorithmic complexity when used to identify aspects and properties of complex networks. We review the fragility of computable measures on the one hand and the invariant properties of algorithmic measures on the other demonstrating how current approaches to algorithmic complexity are misguided and suffer of similar limitations than traditional statistical approaches such as Shannon entropy. Finally, we review some current definitions of algorithmic complexity which are used in analyzing labelled and unlabelled graphs. This analysis opens up several new opportunities to advance beyond traditional measures.

Original languageEnglish (US)
Article number551
Issue number8
StatePublished - Aug 1 2018

Bibliographical note

Publisher Copyright:
© 2018 by the authors.


  • Algorithmic information theory
  • Algorithmic probability
  • Algorithmic randomness
  • Biological networks
  • Complex networks
  • Kolmogorov-Chaitin complexity

ASJC Scopus subject areas

  • Information Systems
  • Mathematical Physics
  • Physics and Astronomy (miscellaneous)
  • Electrical and Electronic Engineering


Dive into the research topics of 'A review of graph and network complexity from an algorithmic information perspective'. Together they form a unique fingerprint.

Cite this