Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks

DOI10.1016/J.PHYSA.2014.02.060zbMath1395.68161arXiv1306.0322OpenAlexW2007512406MaRDI QIDQ1782785

Kamaludin Dingle, Ard A. Louis, Hector Zenil, Fernando Soler-Toscano

Publication date: 20 September 2018

Published in: Physica A (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1306.0322

zbMATH Keywords

Kolmogorov complexityalgorithmic probabilitycompressibilitycomplex networksgraph automorphismsnetwork biology

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Deterministic network models in operations research (90B10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25)

Related Items (1)

A computable measure of algorithmic probability by finite approximations with an application to integer sequences

Uses Software

• DIMACS
• OACC
• acss

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Entropy and the complexity of graphs revisited
• A history of graph entropy measures
• Numerical evaluation of algorithmic complexity for short strings: a glance into the innermost structure of randomness
• ASYMPTOTIC BEHAVIOR AND RATIOS OF COMPLEXITY IN CELLULAR AUTOMATA
• Conflict Anticipation in the Search for Graph Automorphisms
• Statistical mechanics of complex networks
• Chapter 19 Complexity of Networks
• The Determination of the Value of Rado's Noncomputable Function | sum(k) for Four-State Turing Machines
• Efficient Planarity Testing
• The graph isomorphism disease
• Community structure in social and biological networks
• Kolmogorov Random Graphs and the Incompressibility Method
• On Non-Computable Functions
• Collective dynamics of ‘small-world’ networks
• Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures
• On the Kolmogorov-Chaitin Complexity for short sequences
• On the Length of Programs for Computing Finite Binary Sequences
• A formal theory of inductive inference. Part II
• An introduction to Kolmogorov complexity and its applications
• Networks

This page was built for publication: Correlation of automorphism group size and topological properties with program-size complexity evaluations of graphs and complex networks