Low-algorithmic-complexity entropy-deceiving graphs

In estimating the complexity of objects, in particular, of graphs, it is common practice to rely on graph- and information-theoretic measures. Here, using integer sequences with properties such as Borel normality, we explain how these measures are not independent of the way in which an object, such as a graph, can be described or observed. From observations that can reconstruct the same graph and are therefore essentially translations of the same description, we see that when applying a computable measure such as the Shannon entropy, not only is it necessary to preselect a feature of interest where there is one, and to make an arbitrary selection where there is not, but also more general properties, such as the causal likelihood of a graph as a measure (opposed to randomness), can be largely misrepresented by computable measures such as the entropy and entropy rate. We introduce recursive and nonrecursive (uncomputable) graphs and graph constructions based on these integer sequences, whose different lossless descriptions have disparate entropy values, thereby enabling the study and exploration of a measure's range of applications and demonstrating the weaknesses of computable measures of complexity.

Figure 1

Basic node and link growth properties and corresponding fitted (polynomial) lines. The relation between node and link growth determines the edge density, which at the limit is 0.

Figure 2

Graph-theoretic and dynamic properties of the recursive ZK graph. Despite the trivial construction of the recursive network, it displays all sorts of interesting convergent and divergent nontrivial graph-theoretic, dynamic, and complexity properties. For example, the clustering coefficient of the undirected graph asymptotically converges to 0.65 and some properties increase or decrease linearly while others do so polynomially. The entropy of different graph descriptions (even for fully accurate descriptions, and not because of a lack of information from the observer point of view) diverge and become trivially dependent on other simple functions (e.g., edge density or degree sequence normality). In contrast, methods based on the algorithmic probability (cf. V) assign a lower complexity to the graph than both entropy and lossless compression algorithms (e.g., Compress, depicted here) that are based on the entropy rate (word repetition). While useful for quantifying specific features of the graph that may appear interesting, no graph-theoretic or entropic measure can account for the low (algorithmic) randomness and therefore (high) causal content of the network.

Figure 3

ZK randomness and information content according to the lossless compression entropy and a technique, other than compression, that uses the concept of algorithmic probability to approximate the algorithmic complexity [18, 19, 20]. This means that randomness characterizations by algorithmic complexity are robust, as they are independent of object description and are, therefore, in an essential way, parameter-free, meaning that there is no need for preselection or arbitrary selection of features of interest for proper graph profiling.

Figure 4

Histograms of degree distributions of $\pi$ networks using 10 000 (left) and $10\times {10}^6$ (right) digits of $\pi$ (a) in base 2 and (b) in base 10 undirected and with no self-loops. (c) A graph based on the 64 calculated bits of a partially computable $\mathrm{\Omega }$ Chaitin number [29]. It appears to have some structure but any regularity will eventually vanish, as it is a Martin-Löf algorithmic random number [30].

Figure 5

A regular antelope graph (left) and an Erdös-Rényi graph (right) with the same number of edges and nodes and, therefore, the same adjacency matrix dimension and exactly the same edge density, $0.03979...$, can have very different properties. Specifically, one can be recursively (algorithmically) generated, while the other is random looking. One would wish to capture this essential difference.

Figure 6

Box plot of entropy values applied to the degree-sequence distribution of 10 scale-free (B-A) and 10 E-R graphs with $n=50$ nodes and the same parameters. Results may mislead as to the generative quality of each group of graphs, suggesting that B-A graphs are as random as or more random than E-R graphs, despite their recursive (causal/algorithmic and deterministic) nature, whereas in fact this should make B-A networks more random than E-R graphs. Here the E-R graphs have exactly the same edge density as the B-A graphs for four and five preferential attached edges per node. This plot illustrates how, for all purposes, the entropy can be easily fooled and cannot tell higher causal content from apparent randomness. One can always update the ensemble distribution to accommodate special cases but only after gaining knowledge by other methods.

Figure 7

(a) Treelike and (b) radial representation of the same ZK graph with maximal entropy degree sequence by construction, starting from iteration 2 and proceeding to iteration 8, adding a node at a time.