A Review of Graph and Network Complexity from an Algorithmic Information Perspective

Area of Science:

• Network Science
• Information Theory
• Graph Theory

Background:

• Information-theoretic measures are crucial for quantifying network complexity.
• Existing methods for characterizing graphs and networks include Shannon entropy, lossless compressibility, and algorithmic complexity.
• These measures have varying strengths and limitations in identifying complex network properties.

Purpose of the Study:

• To survey and contrast information-theoretic methods for network characterization.
• To illustrate the strengths and limitations of Shannon's entropy, lossless compressibility, and algorithmic complexity.
• To analyze current definitions of algorithmic complexity for graph analysis.

Main Methods:

• Comparative analysis of information-theoretic measures.
• Review of algorithmic complexity definitions for labelled and unlabelled graphs.
• Illustration of measure fragility and invariant properties.

Main Results:

• Computable measures exhibit fragility, while algorithmic measures possess invariant properties.
• Current algorithmic complexity approaches share limitations with traditional statistical methods like Shannon entropy.
• Analysis reveals opportunities to advance beyond existing network complexity measures.

Conclusions:

• Algorithmic complexity, while offering invariant properties, faces challenges with computability.
• Traditional statistical approaches and current algorithmic complexity methods have similar limitations.
• New opportunities exist for developing more robust measures of network complexity.