Research Article: Entropy Bounds for Hierarchical Molecular Networks

Date Published: August 28, 2008

Publisher: Public Library of Science

Author(s): Matthias Dehmer, Stephan Borgert, Frank Emmert-Streib, Enrico Scalas.

Abstract: In this paper we derive entropy bounds for hierarchical networks. More precisely, starting from a recently introduced measure to determine the topological entropy of non-hierarchical networks, we provide bounds for estimating the entropy of hierarchical graphs. Apart from bounds to estimate the entropy of a single hierarchical graph, we see that the derived bounds can also be used for characterizing graph classes. Our contribution is an important extension to previous results about the entropy of non-hierarchical networks because for practical applications hierarchical networks are playing an important role in chemistry and biology. In addition to the derivation of the entropy bounds, we provide a numerical analysis for two special graph classes, rooted trees and generalized trees, and demonstrate hereby not only the computational feasibility of our method but also learn about its characteristics and interpretability with respect to data analysis.

Partial Text: The investigation of topological aspects of chemical structures concerns a major part of the research in chemical graph theory and mathematical chemistry [1], [2], [3], [4]. Following, e.g., [5], [6], [7], [1], [2], [8], [9], classical and current research topics in chemical graph theory involve, e.g., modeling of chemical molecules by means of graphs, graph polynomials, graph-theoretical matrices, enumeration of chemical structures, and aspects of quantitative structure analysis like measuring the structural similarity of graphs and structural information. Further, a lot of the above mentioned contributions can be integrated under the following thematic categories which are well know in chemistry: QSAR and QSPR. QSAR (Quantitative structure-activity relationship) deals with descripting pharmacokinetic processes as well as biological activity or chemical reactivity [10], [11]. In contrast, QSPR (Quantitative Structure-Property Relationship) generally addresses the problem to convert chemical structures into molecular descriptors which are relevant to a physico-chemical property or a biological activity [11], [12]. However, a main problem in QSPR is to investigate relationships between molecular structure and physicochemical properties, e.g., the topological complexity of chemical structures [7], [13], [14], [11].