SpringerOpen Newsletter

Receive periodic news and updates relating to SpringerOpen.

Open Access Research

Information theoretical methods for complex network structure reconstruction

Enrique Hernández-Lemus12* and Jesús M Siqueiros-García3

Author Affiliations

1 Computational Genomics Department, National Institute of Genomic Medicine, Mexico City, México

2 Complexity in Systems Biology, Center for Complexity Sciences, National Autonomous University of México, Mexico City, Mexico

3 Ethics, Legal and Social Studies Department, National Institute Genomic Medicine, Mexico City, México

For all author emails, please log on.

Complex Adaptive Systems Modeling 2013, 1:8  doi:10.1186/2194-3206-1-8

Published: 8 April 2013

Abstract

Purpose

Complex networks seem to be ubiquitous objects in contemporary research, both in the natural and social sciences. An important area of research regarding the applicability and modeling of graph- theoretical-oriented approaches to complex systems, is the probabilistic inference of such networks. There exist different methods and algorithms designed for this purpose, most of them are inspired in statistical mechanics and rely on information theoretical grounds. An important shortcoming for most of these methods, when it comes to disentangle the actual structure of complex networks, is that they fail to distinguish between direct and indirect interactions. Here, we suggest a method to discover and assess for such indirect interactions within the framework of information theory.

Methods

Information-theoretical measures (in particular, Mutual Information) are applied for the probabilistic inference of complex networks. Data Processing Inequality is used to find and assess for direct and indirect interactions impact in complex networks.

Results

We outline the mathematical basis of information-theoretical assessment of complex network structure and discuss some examples of application in the fields of biological systems and social networks.

Conclusions

Information theory provides to the field of complex networks analysis with effective means for structural assessment with a computational burden low enough to be useful in both, Biological and Social network analysis.

Keywords:
Complex networks structure; Probabilistic network inference; Feature selection; Information theory; 94A15; 62B10; 91D30; 05C82