arXiv:1802.05843v1 [] 16 Feb 2018

Parameter-free Network Sparsification and Data
Reduction by Minimal Algorithmic
Information Loss
Hector Zenil1,2,3,4 , Narsis A. Kiani1,2,3,4 , Jesper Tegnér2,3,5
1
Algorithmic Dynamics Lab, Centre for Molecular Medicine,
Karolinska Institute, Stockholm, Sweden
2
Unit of Computational Medicine, Department of Medicine
Solna, Karolinska Institute, Stockholm, Sweden
3
Science for Life Laboratory (SciLifeLab), Stockholm, Sweden
4
Algorithmic Nature Group, LABORES for the Natural and
Digital Sciences, Paris, France
5
Biological and Environmental Sciences and Engineering Division,
Computer, Electrical and Mathematical Sciences and Engineering
Division, King Abdullah University of Science and
Technology (KAUST), Kingdom of Saudi Arabia
{hector.zenil, narsis.kiani, jesper.tegner}@ki.se
Abstract
The study of large and complex datasets, or big data, organized as
networks has emerged as one of the central challenges in most areas
of science and technology. Cellular and molecular networks in biology
is one of the prime examples. Henceforth, a number of techniques for
data dimensionality reduction, especially in the context of networks,
have been developed. Yet, current techniques require a predefined metric upon which to minimize the data size. Here we introduce a family
of parameter-free algorithms based on (algorithmic) information theory that are designed to minimize the loss of any (enumerable computable) property contributing to the object’s algorithmic content and
thus important to preserve in a process of data dimension reduction
when forcing the algorithm to delete first the least important features.
Being independent of any particular criterion, they are universal in a
fundamental mathematical sense. Using suboptimal approximations of
efficient (polynomial) estimations we demonstrate how to preserve network properties outperforming other (leading) algorithms for network
dimension reduction. Our method preserves all graph-theoretic indices
measured, ranging from degree distribution, clustering-coefficient, edge
betweenness, and degree and eigenvector centralities. We conclude and
demonstrate numerically that our parameter-free, Minimal Information Loss Sparsification (MILS) method is robust, has the potential
to maximize the preservation of all recursively enumerable features in
data and networks, and achieves equal to significantly better results
than other data reduction and network sparsification methods.
Keywords: coarse-graining; renormalization; algorithmic probability; feature selection; algorithmic graph sparsification; causal image
segmentation.

1

1

Introduction and Motivation

There is an increasing need for reduction techniques of high-dimensional
data in areas ranging from the social to the molecular sciences. The upshot,
from the standpoint of data analysis, has been referred to as the “curse of
dimensionality” [4].
Life scientists are finding themselves required to cope with huge highdimnesional data sets, and they face challenges extracting and interpreting
the wealth of available information. The main purpose of data dimensionality reduction can be seen as involving a balance between two different goals
and constraints. On the one hand, it is advantageous to minimize the loss
of information of important features, and on the other hand, to maximize
the preservation of important properties, usually defined in terms of a usercentric, subjective criterion. Graphs have been used as an efficient formal
structure for representing data. Network science is now central to many areas, including molecular biology, serving as a framework for reconstructing
and analyzing relations among biological units [3, 15, 26, 5].
The main aim of dimension reduction in a network is to approximate a
network with a sparse network. There are several methods available in the
literature for graph sparsification. Chew [10] used the shortest-path distance
between every pair of vertices as a criterion for sparsifying a network. The
concept of cut problems has been utilized for sparsification by Benczur and
Karger [7]. In what is one of the latest methods, spectral similarity of graph
Laplacians has been used for sparsification by [31].
For network dimensionality reduction one may choose as a criterion the
preservation of graph-theoretic properties such as graph distance, clustering
coefficient or degree distribution, or a finite (usually small) combination of
these or other indices. But no finitely computable approach can find all
possible features of interest in a dataset. For example, all those recursively
enumerable features that the set of all Turing machines can characterize, all
at the same time [35], which means that the observer is forced to make an
arbitrary choice of pre-selected (and thus foreknown) features of interest (see
e.g. [39]). Here we introduce an optimal parameter-free (and in that sense
‘universal’) algorithm for data features, particularly node and edge information ranking (InfoRank) and dimension reduction, which we refere to as
MILS, denoting Minimal Information Loss Sparsification. The algorithm is
independent of approximating method and can be implemented with Shannon Entropy or lossless compression. Here we use a state-of-the-art method
to approximate algorithmic complexity based on the concept of Algorithmic
Probability [40].
2

2
2.1

Preliminaries and Background
Cellular automata

We will use space-time diagrams of cellular automata to illustrate the way
in which the algorithm operates.
A cellular automaton is a computer program that applies in parallel a
global rule composed of local rules on a tape of cells with symbols (e.g.
binary). Thoroughly studied in [41], Elementary Cellular Automata (or
ECA) are one-dimensional cellular automata that take into consideration in
their local rules the cell next to the centre and the centre cell.
In the case of 1-dimensional CA it is common to introduce the radius of
the neighbourhood template, which can be written as h−r, −r+1, . . . , r−1, ri
and has length 2r + 1 cells. With a given radius r the local rule is a function
|S|(2r+1)

|S|(2r+1)

f : Z|S|
→ Z|S| with Z|S|
rules.
Elementary Cellular Automata (ECA) have a radius r = 1 (closest neighbours), having the neighbourhood template h−1, 0, 1i, meaning that the
neighbourhood comprises a central cell. From this it follows that the rule
3
space for ECA contains 22 = 256 rules.
Enumeration of ECA rules: It is common to follow the lexicographic
ordering scheme introduced by Wolfram [41]. According to this encoding,
the 256 ECA rules can be encoded by 8-bits.
A space-time diagram captures the evolution of a cellular automaton for
a given initial condition and is read from the top starting from time step
t = 0 (the initial condition) and evolves towards the bottom of the diagram
(see Fig. 2).

2.2

Graph/network theory and information theory

Definition 2.1. A graph is an ordered pair G = (V, E) comprising a set
V of nodes or vertices and a set E of edges or links, which are 2-element
subsets of V .
Definition 2.2. The spectrum of a graph is the list of Eigenvalues from the
graph adjacency matrix sorted from largest to smallest.
Definition 2.3. Given a simple graph G with n = |E| vertices, its Laplacian
matrix Ln×n is defined by L = D − A. where D is the degree matrix and A
is the adjacency matrix of the graph.
In what follows, we will use the terms nodes and vertex, and links and
edges, interchangeably.
3

2.3

Classical Information Theory and Shannon Entropy

Central to information theory is the concept of Shannon’s information Entropy, which quantifies the average number of bits needed to store or communicate the statistical description of an object.
For an ensemble X(R, p(xi )), where R is the set of possible outcomes
(the random variable), n = |R| and p(xi ) is the probability of an outcome
in R. The Shannon Entropy of X is then given by
Definition 2.4.
H(X) = −

n
X

p(xi ) log2 p(xi )

(1)

i=1

Which implies that to calculate H(X) one has to know or assume the
mass distribution probability of ensemble X.

2.4

Graph complexity

The algorithmic information content of a graph denoted by C(G) is given
by the so-called algorithmic Coding theorem [20, 13, 29]:
C(G) = − log2 AP (G)
where AP (G) is the Algorithmic Probability of the adjacency matrix of G
defined by the output frequency probability of being produced by a random 2-dimensional Turing machine (a typical deterministic Turing machine
whose single head can also move up and down as well as left and right) starting from an empty 2-dimensional grid (instead of the typical 1-dimensional
tape Turing machine) as defined in [33].
A Turing machine is a general abstraction of a computer program similar to cellular automata but sequential that given an input produces an
output and halts. The Turing machine is thus an algorithmic mechanistic
causal explanation of the output and is at the centre of the algorithms here
introduced. The idea is to find a short Turing machine that explains an
object (e.g. a network) by explaining smaller overlapping segments of the
object [34, 37].

2.5

Element information value/contribution

All methods are based on the information difference among the elements of
an object, in other words, on the information contribution of the elements
of a system to the whole, e.g. a network. This is based on a concept of
4

algorithmic/causal perturbation analysis as introduced in [33, 37, 38]. The
procedure consists in the perturbation of all elements of a system by the
removal of elements whose effects on its algorithmic information content are
measured and ranked accordingly.
Technically, let G be a network with edges e1 , . . . , en ∈ E (the same can
be done for nodes), G\ei be G with edge ei removed, and I the information
difference or information value/contribution of ei to G given by
I(G, ei ) = C(G) − C(G\ei )
Where C(G) is the algorithmic information content of the graph G as
defined in [33] (see Methods).
When taking the difference C(G) − C(G\ei ) by itself we will refer to it
as the graph (dis)similarity between graph G and G\ei .
I applied to graphs suggests a similarity distance between graphs based
on algorithmic information content (in [36]. We show that this similarity
measure can classify networks by the family they belong to, differentiating
variant synthetic and natural network topologies similar to graph motifs, as
shown in [25]).
In the description of the algorithm that follows, replacing the underlying methods to approximate the (algorithmic) information content by, e.g.,
Shannon entropy or lossless compression algorithms represents special cases
of the more general algorithm based on algorithmic complexity, and thus it
covers all these less powerful cases. The idea of a dynamic study/calculus
of the (possible) changes that can be wrought upon an object to evaluate
the contribution of each of its components for different purposes was introduced in [38], and here we extend these ideas to the area of data/network
dimension reduction.

2.6

Graph information content

The concept of algorithmic probability (also known as Levin’s semi-measure)
yields a method for approximating Kolmogorov complexity related to the
frequency of patterns in the adjacency matrix of a network, including therefore the number of subgraphs in a network. The algorithmic probability [30, 20, 9] of a subgraph H ∈ G is a measure that describes the probability that a random computer program p will produce H when run on
a 2-dimensional tape universal (prefix-free1 ) Turing machine U . That is,
1

The group of valid programs forms a prefix-free set (no element is a prefix of any
other, a property necessary to keep 0 < m(G) < 1).

5

A

B

Figure 1: A: Reduction/coarse-graining of space-time evolutions of Elementary Cellular Automata (ECA rules 22 and 158) by minimization of algorithmic information loss. Depicted are steps after application of MILS
starting from original (A) and second step (B), highlighting the regions that
are earmarked to be omitted (coloured in grey) versus the features that are
kept and carried out along the way, thereby optimally preserving the main
properties of these objects, properties whose persistence enables a ranking
of such features. Unlike Entropy and other statistical approaches, the algorithm can also approximate (and thus preserve/extract) features that are of
an algorithmic nature that are not statistically apparent (see [40, 39]).

6

P
m(G) = p:U (p)=H∈G 1/2|p| . An example of a popular 2-dimensional tape
Turing machine is Langton’s ant [19], commonly referred to as a Turmite.
The probability semi-measure m(G) is related to Kolmogorov complexity
C(G) in that m(G) is at least the maximum term in the summation of programs m(G) ≥ 2−C(G) , given that the shortest program carries the greatest
weight in the sum. The algorithmic Coding Theorem [13] further establishes
the connection between m(G) and C(G) as ([20]): | − log2 m(G) − C(G)| < c
(Eq. 1), where c is some fixed constant, independent of s. The theorem
implies that [13] one can estimate the Kolmogorov complexity of a graph
from the frequency of production from running random programs by simply
rewriting Eq. (1) as: C(G0 ) = − log2 m(G) + O(1).
In [14] a technique was advanced for approximating m(G) (hence K) by
means of a function that considers all Turing machines of increasing size (by
number of states). Indeed, for small values of n states and k colours (usually
2 colours only), D(n, k) is computable for values of the Busy Beaver problem [27] that are known, providing a means to numerically approximate the
Kolmogorov complexity of small graphs, such as network motifs. The Coding theorem then establishes that graphs produced with lower frequency by
random computer programs have higher Kolmogorov complexity, and vice
versa. Here we will use the Block decomposition method (BDM) as an estimator of algorithmic complexity, but the algorithm and methods introduced
are independent of the particular method used to approximate algorithmic
complexity.
The BDM consists in decomposing the adjacency matrix of a graph into
subgraphs of sizes for which complexity values have been estimated, then
reconstructing an approximation of the Kolmogorov complexity of the graph
by adding the complexity of the individual pieces according to the rules of
information theory, as follows:
C(G) =

X

log2 (nu ) + C(ru )

(2)

(ru ,nu )∈Adj(G)d×d

where Adj(G)d×d represents the set with elements (ru , nu ), obtained
when decomposing the adjacency matrix of G into all subgraphs contained
in G of size d. In each (ru , nu ) pair, ru is one such submatrix of the adjacency matrix and nu its multiplicity (number of occurrences). As can be
seen from the formula, repeated subgraphs only contribute to the complexity value with the subgraph BDM complexity value once plus a logarithmic
term as a function of the number of occurrences. This is because the information content of subgraphs is only sub-additive, as one would expect from

7

the growth of their description lengths. Applications of m(G) and C(G)
have been explored in [14, 29, 28, 34], and include applications to graph
theory and complex networks [33] and [34] where the technique was first
introduced.

2.7

Minimal Information Loss Sparsification (MILS) algorithm

MILS is a parameter-free algorithm as it does not need to be instructed or
designed to preserve any particular property, and maximizes the preservation
of all elements contributing to the algorithmic information content of the
data.
The MILS algorithm pseudo-code is as follows. Let G be a graph, then:
1. Calculate G\Ej∗ for all subsets j ∈ E ∗ where E ∗ denotes all non-empty
proper subsets of edges {e1 , . . . , en }.
2. Remove the edge subset Ej∗ such that C(G\Ej∗ ) < |C(G\Ei∗ )| for all
subsets i, where |C| is the absolute value of C.
3. Repeat 1 such that G := G\{e}∗j until final target size is reached.
The algorithm’s time complexity class is clearly in O(exp) because of the
subsets’ operation. A more efficient but suboptimal version of MILS iterates
over single elements (nodes or edges) or singletons.
1. Calculate G\ei for all i ∈ {e1 , . . . , en }.
2. Remove edge ej such that C(G\ej ) < |C(G\ei )|.
3. Repeat 1 with G := G\ej until final target size is reached.
We call ej a neutral information edge because it is the edge that contributes less to the information content of G (in particular, it minimizes
information loss or the introduction of spurious information) to the network
according to the information difference when removed from the original network.
The above pseudo-code assumes that there is a unique such ej which
may not necessarily be the case. In the Supplementary Information there is
a description of the exact algorithm that guarantees the uniqueness of Gn
and also determines its polynomial time computational class ≤ O(n2 ). We
use this more efficient version in all our experiments reported in the Results
section, and even in this limited form the procedure excels at preserving
important characteristics of the networks.
8

MILS is, by design, optimal and universal in the computability and
algorithmic-information theory sense, and only dependent on the method
for approximating algorithmic complexity in the preservation of any possible feature of interest that contributes to the (algorithmic) information
content of a network G such as, evidently, its degree distribution and other
graph-theoretic, algebraic or topological features, even those not necessarily captured by any graph theoretic measure or classical information approach [39].

2.8

Algorithmic Information Rank

MILS immediately suggests a powerful method for ranking nodes and edges
by their contribution to the information content of a network. By running
MILS one produces a reversed ranking from least informative to greatest
informative edges.
The pseudo-code of the algorithmic information rank (InfoRank) method
of an object such as a network G can be described as follows:
1. Apply MILS on a network G.
2. Let s = {e1 , . . . , en } be the list of edges of G sorted by MILS deletion
order after n iterations
3. The list of edges sorted by their information content from lowest to
greatest contribution to G after reindexation is the (algorithmic) information rank (InfoRank) of the E ∈ G (the same algorithm may be
applied to nodes, or to any data element of a dataset, e.g. a row or
column in a spreadsheet).
The InfoRank algorithm induced by the exponential version of MILS is
the most powerful but also, evidently, the most computationally expensive.
The pseudo-code of the InfoRank algorithm above, however, is in the same
complexity time class as the singleton version of MILS (i.e. removing a
single element at a time, or several when they collide), that is, in O(n2 )
time, as we will prove.

3

Results

Fig. 1 demonstrates the basic concept behind the algorithms introduced here
using as a case study a simple string. Identified inflection points are natural
breaking points for algorithmic partitioning, and the identification of different parts of the sequence and their contribution to the full-length sequence
9

Figure 2: MILS or neutral edge deletion (blue) outperforms random edge
deletion (red) at preserving both edge degree distribution (top, showing
removed edges) and edge betweenness distribution (bottom) on an ErdösRényi random graph of node size 100 and low edge density (∼ 4%) after up
to 60 edges were removed (degree distribution comparison) and 150 edges
were removed (edge betweenness) out of a total of 200 edges (notice also the
scale differences on the x-axis).
illustrates the way in which segments with high or low algorithmic content
can be ranked, selected or preserved for dimensional reduction purposes.
The method approximates the generating mechanism of each segment by
finding candidate generating mechanisms that explain part of the data by
finding the computer programs that produce the data and are in turn placed
together in sequence to produce the full object with the sequence itself a
model of the entire dataset. In other words, an algorithmic (causal) likelihood is approximated with hundreds to millions of small computer programs
as a function of the algorithmic randomness of the data (the less algorithmically complex, the greater the number of candidate models) [14, 29, 40].
We demonstrate that MILS preserves essential local and global properties of synthetic and natural networks of different types and topologies,

10

Figure 3: MILS mean clustering coefficient preservation against two other
sophisticated graph sparsification methods based on graph spectral and transitive reduction techniques on biological, electric and social networks taken
from [25]. The transitive method does not allow selection of edges to be
deleted and in some cases it either fails to significantly reduce the network
size if no cycles are present (such as, generally, in electric and genetic networks) and/or takes the clustering coefficient to 0 (e.g. for protein networks)
if cycles are only local. Comparisons with other methods are unnecessary
because they destroy local or global properties by design, such as clustering
coefficients for the spanning tree algorithm.

11

Figure 4: Histograms showing preservation of degree distribution from 20%
to 80% edge removal. Green highlights the overlapping and preservation
area of the distributions after random deletion (top), MILS and spectral
removal (bottom pairs).
12

performing at least as well as but usually better than other algorithms. We
took a sample of well-known and previously thoroughly studied networks
from [25]. These included genetic regulatory networks, protein, power grid
and social networks. We applied MILS to each of these networks and compared with two powerful sparsification methods: Transitive reduction [1]
and Spectral sparsification [31]. A transitive reduction of a directed graph
is therefore a graph with as few edges as possible that has the same reachability relation as the given graph. A good introduction to spectral graph
sparsification may be found in [6]. The method was designed to reduce the
network dimension based upon spectral similarity of graph Laplacians which
guarantees the preservation of important properties of the graph by way of
its adjacency matrix Laplacian spectrum.
Fig. 2 shows how MILS preserves the degree distribution and the edge
betweenness distribution of a typical synthetically (recursively) generated
Erdös-Rényi (ER) random graph (in this example of low edge density it is
very sparse) compared with random edge deletion and spectral sparsification. While MILS is not significantly better at preserving the clustering
coefficient of random networks, Fig. 3 shows that MILS does significantly
better at preserving the clustering coefficient of real-world (biological, social
and electric grid) networks taken from [25], outperforming both Transitive
and Spectral reduction/sparsification methods. Figs. 5(SI), 6(SI) and 7(SI)
illustrate how MILS outperforms spectral sparsification at preserving edge
betweenness, and degree and eigenvector centralities.

3.1

Uniqueness and time complexity

Let N be a network and I(N, n) the information difference (or information
value) of an element n ∈ N to N defined by I(N, n) = C(N ) − C(N \n).
If n is a neutral element then it does not contribute to the algorithmic
information content of N (by definition) thus I(N, n) = log n meaning that
n is part of the dynamical causal path of N and N can regenerate n by its
normal dynamical course. In general, however, if there is no element n, such
that I(N, n) = log n the most neutral element n in N to be removed in the
application of MILS is I(N, n) = min{|C(N ) − C(N \n)| ∼ log(n))}, that
is, the elements closest to log(n).
For MILS to be a proper algorithm, we need the element (e.g. node
or edge) deletion procedure to determine a unique graph in a deterministic
fashion. But if two or more than two elements have the same information
value the algorithm becomes ambiguous.
The problem is that there may be elements such that I(n1 ) = I(n2 )
13

and the algorithm cannot uniquely decide to remove n1 or n2 first potentially (and likely) leading to (slightly) different final results. The following
algorithm tweak avoids this problem and shows that the algorithm is robust.
Theorem 3.1. MILS is a well-defined and produces the same output for the
same input (is deterministic).
Let {n} ⊂ N be a subset of element of N where N can be a graph, a
cellular automaton or any other object whose size is to be reduced by application of MILS. Let I(N, ni ) = I(N, nj ) for element ni and nj ∈ {n}, then
MILS will remove {n} from N at the same time. This set deletion condition
makes MILS a proper algorithm.
This also produces a speedup with the MILS time complexity now ranging between the original O(n(n − 1)/2) ∼ O(n2 ) and constant time for
{n} = N i.e. when every node has the same information value and thus
they are all deleted at the same time. For example, any attempt to reduce
the dimension of the complete graph (either by e.g. single-node or singleedge deletion) will produce an empty graph. A minor, and perhaps useful
variation of the algorithm, is an heuristic allowing a random selection of an
element when they have the same information value.

4

Discussion

Because approximations to algorithmic complexity are lower semicomputable (computable from below), the algorithms introduced here inherit
the same limitations and advantages. One limitation is that exact values are
not finitely attainable in general, but among the advantages is the universality and asymptotic robustness of the approximating methods [14, 29]. The
method followed here, called the BDM (standing for Block Decomposition
Method) has been designed to produce results in linear time for a noncomputable task (by exchanging computation time for memory, running the
algorithm and reusing the results), and its accuracy can always be increased
by increasing the computational effort (only once), converging at the limit
to the actual values of the algorithmic complexity of an object, independent
of the chosen representation language or reference programming language
(per the so-called invariance theorem [24]). The algorithms are designed
to maximize the preservation of information while deleting the information
that contributes the least to the algorithmic content, thus allowing an unbiased non-usercentric approach to algorithmic dimension reduction, that
is, the reduction of the model explaining the data to a model explaining
most/or the main features of the data.
14

The algorithm and methods introduced here are independent of the
method used to approximate algorithmic complexity. Here we used a stateof-the-art method based on Algorithmic Probability as introduced previously [34, 14, 29, 40]. Our rationale is that checksum procedures and embedded decompression instructions popular in lossless compression algorithms
such as LZW are not sufficiently sensitive to detect such minor changes [?]
required in the kind of resolution needed for MILS to work. Furthermore,
Shannon entropy has even greater limitations, as it is only constrained to
detect trivial statistical regularities when no other updating procedure is
available to properly calculate the likelihood and prior of the underlying
ensemble [40].

5

Conclusion

We have demonstrated that MILS outperforms general and leading dimensionality reduction algorithms for networks and, interestingly, MILS can be
generalized to any data, as we have shown on space-time diagrams of discrete dynamical systems (cellular automata) that can also be seen as images,
thus making the algorithms here introduced also applicable to challenges of
image segmentation, the chief advantage being that MILS is optimal whenever using optimal methods to approximate algorithmic complexity. To test
the algorithm we used a number of well-known networks commonly used in
the literature to test other algorithms, on which we also applied algorithms
that have been reported to lead other algorithms. The results provide evidence that MILS seems to outperform these algorithms on all indices at
preserving all features of possible interest that we define as all possible features that are recursively enumerable and therefore possible to characterize
using a universal Turing machine, unlike measures that are computable and
cannot, even in principle, achieve such a goal. Our results are in this sense
what is to be expected from theory of algorithmic information, but moreover, they also importantly demonstrates that our numerical approximations
to uncomputable measures are sufficiently accurate to outperform current
heuristic techniques for dimensionality reduction.

Acknowledgements
H.Z. acknowledges the support of the Swedish Research Council (Vetenskapsrådet) grant No. 2015-05299.

15

References
[1] A.V. Aho, M.R. Garey, J.D.Ullman, The transitive reduction of a
directed graph, SIAM Journal on Computing 1 (2): 131–137, 1972.
[2] R. Albert, H. Jeong, A.L. Barabasi, Error and attack tolerance of
complex networks, Nature Jul 27;406(6794):378–82, 2000.
[3] R. Albert and A.-L. Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74, 47, 2002.
[4] C.F. Aliferis, A. Statnikov, and I. Tsamardinos, Challenges in the
Analysis of Mass-Throughput Data: A Technical Commentary from
the Statistical Machine Learning Perspective, Cancer Inform, 2: 133–
162, 2006.
[5] U. Alon,
Collection of Complex Networks. Uri Alon
Homepage
2007
(accessed
on
July
2013).
http://
www.weizmann.ac.il/mcb/UriAlon/groupNetworksData.html.
[6] J. Batson, D.A. Spielman, N. Srivastava, and S.-H. Teng, Spectral
Sparsification of Graphs: Theory and Algorithms, vol. 56:8, Communications of the ACM, 2013.
[7] A. Benczur and David R. Karger. Approximating s-t minimum cuts in
O(n2)time. In Proceedings of The Twenty-Eighth Annual ACM Symposium On The Theory Of Computing (STOC 96), pages 4755, May
1996
[8] S. Carmi, S. Havlin, S. Kirkpatrick, Y. Shavitt, E. Shir, A model
of Internet topology using k-shell decomposition, Proc Natl Acad Sci
USA 104: 11150–11154, 2007.
[9] G.J. Chaitin. On the length of programs for computing finite binary
sequences Journal of the ACM, 13(4):547–569, 1966.
[10] P. Chew. There are planar graphs almost as good as the complete
graph, J. Comput. Syst. Sci., 39:205–219, 1989.
[11] R.L. Cilibrasi, P.M.B. Vitányi, Clustering by compression, IEEE
Trans. Inform. Theory, 51:12, 15231545, 2005.
[12] R.L. Cilibrasi, P.M.B. Vitányi, The Google Similarity Distance, IEEE
Trans. Knowledge and Data Engineering, 19:3, 370-383, 2007.
16

[13] T.M. Cover and J.A. Thomas, Elements of Information Theory, 2nd
Edition, Wiley-Blackwell, 2009.
[14] J.-P. Delahaye and H. Zenil, Numerical Evaluation of the Complexity
of Short Strings: A Glance Into the Innermost Structure of Algorithmic Randomness, Applied Mathematics and Computation 219, 63–77,
2012.
[15] S.N. Dorogovtsev and J.F.F. Mendes, Evolution of Networks, Adv.
Phys. 51, 1079, 2002.
[16] R.L.. Graham, P Hell, On the history of the minimum spanning tree
problem–Annals of the History of Computing, vol 1:7, 43–57, 1985.
[17] M. Kitsak, L.K. Gallos, S. Havlin, F. Liljeros, L. Muchnik, H.E. Stanley, H.A. Makse, Identification of influential spreaders in complex networks. Nat Phys 6: 888–893, 2010.
[18] A.N. Kolmogorov. Three approaches to the quantitative definition
of information, Problems of Information and Transmission, 1(1):1–7,
1965.
[19] C.G. Langton, Studying artificial life with cellular automata, Physica
D: Nonlinear Phenomena, 22 (1-3): 120–149, 1986.
[20] L.A. Levin. Laws of information conservation (non-growth) and aspects of the foundation of probability theory, Problems of Information
Transmission, 10(3):206–210, 1974.
[21] M. Li and P.M.B. Vitányi, An Introduction to Kolmogorov Complexity
and Its Applications, 3rd. Ed. Springer, 2008.
[22] M. Li, X. Chen, X. Li, B. Ma, P.M.B. Vitányi, The similarity metric,
IEEE Trans. Inform. Th., 50:12, 32503264, 2004.
[23] M. Liu, B. Liu, F. Wei, Graphs determined by their (signless) Laplacian spectra, Electronic Journal of Linear Algebra, 22, pp. 112–124,
2011.
[24] M. Li, P.M.B. Vitányi, An Introduction to Kolmogorov Complexity
and Its Applications, Springer; 3rd ed. 2008.
[25] R. Milo, S. Itzkovitz, N. Kashtan, R. Levitt, S. Shen-Orr, V. Ayzenshtat, M. Sheffer, U. Alon, Superfamilies of designed and evolved networks, Science 303, 1538–1542, 2004.
17

[26] M.E.J. Newman, The structure and function of complex networks,
SIAM Review 45 (2): 167–256, 2003.
[27] T. Rado, On Non-Computable Functions, Bell System Technical J.,
41, 877–884, May 1962.
[28] F. Soler-Toscano, H. Zenil, J.-P. Delahaye and N. Gauvrit, Correspondence and Independence of Numerical Evaluations of Algorithmic
Information Measures, Computability, vol. 2, no. 2, pp. 125–140, 2013.
[29] F. Soler-Toscano, H. Zenil, J.-P. Delahaye and N. Gauvrit, Calculating
Kolmogorov Complexity from the Frequency Output Distributions of
Small Turing Machines, PLoS ONE 9(5), e96223, 2014.
[30] R.J. Solomonoff, A formal theory of inductive inference: Parts 1 and
2. Information and Control, 7:1–22 and 224–254, 1964.
[31] D.A. Spielman, N. Srivastava, Graph sparsification by effective resistances, Proceedings of the fortieth annual ACM symposium on Theory
of computing (STOC ’08), 563–568, 2008.
[32] D.A. Spielman, S.-H.Teng, Spectral Sparsification of Graphs, SIAM
J. Comput., 40(4), 981–1025, 2011.
[33] H. Zenil, F. Soler-Toscano, K. Dingle and A. Louis, Graph Automorphisms and Topological Characterization of Complex Networks by Algorithmic Information Content, Physica A: Statistical Mechanics and
its Applications, vol. 404, pp. 341–358, 2014.
[34] H. Zenil, F. Soler-Toscano, J.-P. Delahaye and N. Gauvrit, TwoDimensional Kolmogorov Complexity and Validation of the Coding
Theorem Method by Compressibility, 2013.
[35] H. Zenil, Algorithmic Data Analytics, Small Data Matters and Correlation versus Causation. In M. Ott, W. Pietsch, J. Wernecke (eds.),
Berechenbarkeit der Welt? Philosophie und Wissenschaft im Zeitalter
von Big Data, Springer Verlag, pp. 453–475, 2017.
[36] H. Zenil, N.A. Kiani and J. Tegnér, Quantifying Loss of Information in Network-based Dimensionality Reduction Techniques,
arXiv:1504.06249 , 2015.
[37] H. Zenil, N.A. Kiani and J. Tegnér, Methods of Information Theory
and Algorithmic Complexity for Network Biology, arXiv:1401.3604,
2014.
18

[38] H Zenil, N.A. Kiani, F. Marabita, Y. Deng, S. Elias, A. Schmidt, G.
Ball, J. Tegnér, An Algorithmic Information Calculus for Causal Discovery and Reprogramming Systems, https://doi.org/10.1101/185637
(preprint).
[39] H. Zenil, N.A. Kiani and J. Tegnér, Low Algorithmic Complexity
Entropy-deceiving Graphs, Physics Reviews E. 96, 012308, 2017.
[40] H. Zenil, F. Soler-Toscano, N.A. Kiani, S. Hernández-Orozco, A.
Rueda-Toicen, A Decomposition Method for Global Evaluation of
Shannon Entropy and Local Estimations of Algorithmic Complexity,
arXiv:1609.00110 [].
[41] S. Wolfram, A New Kind of Science, Wolfram Media, Champaign IL.,
2002.

19

Supplementary Information
5.1

Spectral sparsification

The goal of network sparsification in general is to approximate a given graph
G by a sparse graph H on the same set of vertices. If H is close to G in
some appropriate metric, then H can be used as a signature preserving important properties of G for faster computation after reducing the size of
G and without introducing too much error. Obvious trivial sparsification
methods include edge deletion by some criterion such as the outermost ones
(called the k-shell method [8, 17], often used to identify the core and the
periphery of the network), but most of them (such as this shell one) are
rather arbitrary or ad-hoc, rather than general methods aimed at preserving important algebraic, topological or dynamical properties of the original
graph, all of which constitute and contribute to the information content of
the graph, that is, the necessary information to fully describe a network and
reconstruct the network from that description.
A popular sparsification algorithm is the spanning tree [16] designed to
preserve node distance but clearly destroy all other local node properties,
such as the clustering coefficient. Not many non-trivial methods for network sparsification exist today. Some clearly destroy local properties, such
as the spanning tree algorithm, which destroys the clustering coefficient. It
is acknowledged [31, 32, 6], however, that spectral graph sparsification is
among the most efficient, both at preserving important algebraic and dynamical properties of a network and in terms of fast calculation. In part
the dearth of methods is due to a lack of assessment tools to decide whether
one method is better than another in general terms rather than designed to
preserve one or another specific graph theoretic property (e.g. the transitive edge deletion method destroys the clustering coefficient of the original
graph [1]). The spectral method considered in this paper is a high-quality
algorithm described in [6, 31].
Transitive reduction was introduced in [1]. A graph G is said to be
transitive if, for every pair of vertices u and v, not necessarily distinct,
(u, v) ∈ G whenever there is a directed path in G from u to v. That is, if
there is a path from a vertex x to a vertex y in graph G, there must also
be a path from x to y in the transitive reduction of G, and vice versa. If
a given graph is a finite directed acyclic graph, its transitive reduction is
unique, and is a subgraph of the given graph.
Graph sparsification is the approximation of an arbitrary graph by a
sparse graph. Here we compare MILS against random, simple (e.g. span-

20

ning tree) and two powerful graph sparsification and reduction methods
(spectral and transitive). Spectral graph sparsification is based on the spectral similarity of graph Laplacians. A spectral sparsifier is a subgraph of
the original whose Laplacian quadratic form is approximately the same as
that of the original graph on all real vector inputs. Spectral graph sparsification is a stronger notion than cut sparsifiers [32] and is considered one of
the most, if not the most, sophisticated sparsification or network reduction
method, as it is believed to preserve some of the most important algebraic,
topological and potentially dynamical properties of a network.

5.2

Graph-theoretic measures

The global clustering coefficient of G is the fraction of paths of length 2 in g
that are closed over all paths of length two in G. The mean or average clustering coefficient is the mean over all local clustering coefficients of vertices
of G.
The betweenness centrality for a vertex i in a connected graph is given
P
nis,t
by s,t∈v∧s6=i∧t6=i ns,t
, where ns,t is the number of shortest paths from s to t
i
and ns,t is the number of shortest paths from s to t passing through i. The
ni

ratio ns,t
is taken to be zero when there is no path from s to t.
s,t
Degree centrality is a measure of the centrality of a node in a network
and is defined as the number of edges (including self-loops) that lead into
or out of the node. The degree centrality of G is the list of nonnegative
integers (“degree centralities”) lying between 0 and n − 1 inclusive, where n
is the number of vertices of G, and identifies nodes in the network by their
influence on other nodes in their immediate neighbourhood.
Eigenvector centrality is a list of normalized nonnegative numbers (“eigenvector centralities”, also known as Gould indices) that are particular centrality measures of the vertices of a graph. Eigenvector centrality is a measure
of the centrality of a node in a network based on the weighted sum of centralities of its neighbours. It therefore identifies nodes in the network that
are connected to many other well-connected nodes. For undirected graphs,
the vector of eigenvector centralities c satisfies the equation c = 1/λ1 a.c,
where λ1 is the largest eigenvalue of the graph’s adjacency matrix a.

21

Figure 5: Stacked histograms showing edge betweenness preservation of
MILS versus spectral sparsification across different families of networks. The
similarity in height of each segment is an indication of the preservation of
such properties. Blue bars (MILS) approximate yellow (original) bars better
than spectral sparsification. On average MILS was 1.5 times the edge betweenness distribution of these representative graphs measured by the area
similarity of the respective bars.

22

Figure 6: Stacked histograms showing the preservation of degree centrality after application of MILS versus spectral sparsification across different
families of networks: bars with height closest to the original graph signify
better preservation. Blue bars (MILS) approximate yellow (original) bars
compared with spectral sparsification. MILS slightly outperforms spectral
sparsification in this test but never did worse.

23

Figure 7: Stacked histograms showing eigenvector centrality preservation of
MILS versus spectral sparsification across the different families of networks:
bars with height closest to the graph’s original bar signify better edge betweenness distribution preservation. Blue bars (MILS) approximate yellow
(original) bars better than spectral sparsification both in distribution shape
and individual bar height. On average MILS preserved the eigenvector centrality distribution of these representative networks 1.5 times better.

24

