Information Measures to Characterize Networks

Currently, network-based approaches are ubiquitous to model complex systems which occur in various scientific disciplines. Especially the fact that many real world phenomena can be modelled by using non-random network topologies, powerful methods to analyze their structural properties are essential. In our proposal, we mainly focus on structural network characterization. Network characterization is generally understood as the task of deriving characteristic (structural) features of a network under consideration to describe its structural complexity. When using information-theoretic methods, one possibility is to firstly derive a probability distribution taking structural features of the network into account. Then, classical information measures like Shannon`s-entropies can be used to quantify the structural information content and interpreted as complexity of a network. However, a major problem of some classical information measures for networks is that the time complexity of the underlying algorithms is often not appropriate for practical use. Also, mathematical properties of such information measures representing the structural information content of a graph (these are often used in mathematical chemistry) are almost unexplored so far. The goal of this research project is twofold: First we want to explore relationships and important mathematical properties of the mentioned information measures. Second, by making use of the established results, we would like to improve the usage of these measures for problems in QSPR (Quantitative Structure-Property Relationships) that is a sub-area of mathematical chemistry. Especially, we put the emphasis on applying (existing and novel) information measures to databases containing chemical structure data represented by graphs to find which measures are suitable to characterize chemical structures meaningfully.

This project dealt with structural network characterization by using information-theoretic measures. Quantitative network characterization can generally be understood as the problem of deriving characteristic (structural) features of a network under consideration to describe its structural complexity quantitatively. In our case, we used entropic quantities such as various graph entropies to do so. By using information-theoretic methods, one derives a probability distribution by taking structural features of the network into account. A still intricate question is what kind of structural complexity a given measure captures. The goal of this project was twofold: First, to investigate the mathematical apparatus and second, to (ideally) apply the findings in Chemoinformatics and for QSPR (Quantitative Structure-Property Relationships).Regarding the first part, a major result of this project dealt with proving novel relationships which describe the interaction between such information-theoretic quantities. Given the fact that numerous measures have been developed, this question has been far from trivial. Also, we extended this framework to probabilistic inequalities and obtained fascinating results. In addition, we investigated extremal properties of the information-theoretic graph measures; this problem turned out to be extremely challenging. In summary, the mentioned research contributed to the problem of measuring the complexity of networks that has been highly relevant in practice (e.g. Internet, Biology, Chemistry etc.). Another problem we tackled in this project relates to investigate how unique those information-theoretic graph measures are. With other words, we explored the ability of the measures to discriminate graphs which are structurally different. As a result, we found that most of the measures known are not unique on exhaustively generated graph. This result can be used for detecting graph isomorphism and to create unique fingerprints for graphs. In summary we believe that our theoretical results contributed to establish an Information Theory of Networks significantly. Second, we employed the achieved results to explore the measures for their use in Chemoinformatics and Chemometrics. We found interesting and important properties of descriptors which can be used to design better and efficient applications in the mentioned areas. An important finding is that most of the available molecular descriptors (we put the emphasis on structural descriptors) capture structural information very similarly and could be therefore obsolete. This result raised the question how useful molecular descriptors are.