Algorithmic complexity of motifs clusters superfamilies of networks

​Representing biological systems as networks has proved to be very powerful. For example, local graph analysis of substructures such as subgraph overrepresentation (or motifs) has elucidated different sub-types of networks. Here we report that using numerical approximations of Kolmogorov complexity, by means of algorithmic probability, clusters different classes of networks. For this, we numerically estimate the algorithmic probability of the sub-matrices from the adjacency matrix of the original network (hence including motifs). We conclude that algorithmic information theory is a powerful tool supplementing other network analysis techniques.

DOI: 10.1109/BIBM.2013.6732768

Algorithmic complexity of motifs clusters superfamilies of networks .pdf

Algorithmic probability Complex networks Information content Information theory Kolmogorov complexity Network motifs Network typology