In this lesson, 
we will see a first application

of algorithmic information dynamics 
to an abstract area of mathematics -

that of graph theory -
and also to a major area in science -

that of network reconstruction 
or network reverse engineering.

We will use these concepts, 
and at least three papers,

in direct connection 
to these applications.

But, obviously all other papers 
about CTM and BDM are relevant,

including two-dimensional complexity 
and graph complexity.

So, you may remember what is
the graph spectrum of a graph.

It is a list of eigenvalues 
of its adjacency matrix,

sorted from largest to smallest.

Something very interesting is that the 
area has very few analytical results,

and a lot of what is known 
is mostly empirical.

There are some obvious eigenvalues 
related to very simple cases,

such as in the case 
of the complete graph.

In a complete graph, 
the largest eigenvalue

is proportional to 
the size of the graph.

So, it basically provides 
the size of the network,

because all the entries 
in the adjacency matrix

in a complete graph are 1.

So, it is not difficult 
to see and even prove

how it can be shown 
that the largest eigenvalue

is related to the number of nodes 
of a complete graph.

But, for non-trivial graphs,

very little is known about 
the behaviour of the eigenvalues,

with respect to classes 
of different graphs.

Usually, the largest eigenvalue is 
considered to be the most informative.

And, that's why it is traditionally
placed first in the graph spectrum.

But, not even that 
is known or true in general,

and traditionally, the rest of
the eigenvalues are ignored -

even when the first one is traditionally
associated only to the graph size.

And so, the rest may encode more 
interesting features about the graph,

but we just disregard them.

So, one project that we have started 
[which is] far from being closed,

is an investigation of the informative 
value of different eigenvalues

in graph spectra 
for different graph types.

Notice this requires 
an objective measure,

because we don't know what an eigenvalue
is measuring in different graphs.

So, it is not possible to define 
a cost function

that requires no inner feature 
of interest,

where no feature of interest 
in the graph or the eigenvalue

is known or identified - let alone 
of the association or relationship.

So, this is an obvious application 
of algorithmic information dynamics,

because we want to compare 
each eigenvalue

to the algorithmic content 
of the graph,

in order to find which one is capturing
most of the graph properties.

And, to do this we can evolve graphs.

So, as I said, 
in graph spectral theory -

traditionally, only the first eigenvalue 
is considered or kept.

Another option... 
that is also very frequent is

to take all eigenvalues to have the same
informative value or the same weight.

However, we know that they capture 
different features for different graphs.

One way to study eigenvalues is,
therefore, to plot them on a space.

Then, make them evolve, 
and take the distance

from those eigenvalues to different 
mutated versions of the same graph.

and compare against all eigenvalues 
to see why and how they change,

and whether they follow the loss or gain
in information content

after applying a perturbation to the
original graph.

So, these are some of the very first 
results we have found.

First, that the largest eigenvalue

is not by far the only one highly 
correlated to the graph complexity -

meaning that, indeed,
the other eigenvalues

are encoding important content 
of the original graphs.

And so, they shouldn't be disregarded 
in principle or a priori.

Each dot here on the screen 
is a different graph class.

A class can be, for example,
a Cayley graph,

which is a graph with particular 
algebraic properties

that have implications 
in [the] size of the graph...

automorphism group,
to which they belong.

And, having no symmetries, 
they tend to be [on] their own

in their own automorphism groups.

Another type of graph 
can be the set of lattices.

Or, another type of graph 
can be planar graphs, that is,

whose edges do not cross each other
in some embeddings

in two dimensions and so on.

So, the way we identify 
the most informative eigenvalue

is by performing the perturbation
analysis to a graph,

thereby emulating the changes 
that a graph can be subject to.

And then, we track 
the eigenvalue behaviour

against the changes 
of algorithmic probability of the graph,

and match the eigenvalue 
that best describes

the direction of the... evolving
trajectory of the graph.

More interestingly, we can do the same 
for different... measures,

such as Shannon entropy, 
and even select a feature of interest

and see which eigenvalue matches the 
Shannon entropy change for that feature,

relative to the change of algorithmic 
content of the graph and so on -

maximising the ways to characterise 
a graph by different measures,

relative to the behaviour 
of different eigenvalues.

So, this approach is very rich,
because it puts together many areas -

just as we like to do with
algorithmic information dynamics.

In particular, it combines algebraic 
and spectral graph theory,

perturbation analysis, 
algorithmic complexity,

information theory 
and dynamical systems.

In another application
of algorithmic information dynamics

to graphs and networks - different to 
the study of graph spectra -

is the evaluation of methods 
that are used to reconstruct networks

representing events happening 
among objects, such as genes,

to reconstruct 
genetic regulatory networks.

The area of network reconstruction 
is very large,

and thousands of methods exist -

but little has been done 
to find ways to evaluate these methods

with other than 
very simplistic measures.

Here is, for example, 
a pipeline that we suggested

to evaluate how much of the original 
algorithmic information content

of a network, 
represented by data,

was preserved by different algorithms 
reconstructing those networks.

And, how to compare each other
to different techniques,

including reduction methods -

such as graph spectra itself 
and motive profile analysis

using various assessing methods
including, for example,

lossless compression and, 
of course, BDM.

One approach suggested 
by algorithmic information dynamics

is simply to evaluate how good a network
reconstruction algorithm can be

at capturing the algorithmic information
content of the original network.

So, here we did it for five of the best 
and most popular algorithms

for network reconstruction 
on different graph topologies.

And, one can also see 
which parameters are best,

or can be optimised,
when reconstructing a network,

in order to keep or lose information -
such as edges -

and then find an optimal cut-off value, 
sometimes or even always necessary

when using popular network
reconstruction algorithms.

So, a similar assessment,

based on algorithmic complexity, 
can be performed.

In the next lesson,

we will see how to actually analyse 
these type of gene regulatory networks,

that are often the result of applying 
these reconstruction methods,

but can also be derived 
or validated

by performing actually 
in material experiments.

[ end of audio ]