Entropy Bounds for Hierarchical Molecular Networks Authors: Matthias Dehmer, Stephan Borgert, Frank Emmert-Streib Published: 2008, PLOS ONE DOI: 10.1371/journal.pone.0003079 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. INTRODUCTION 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] . This paper mainly deals with a challenging problem of quantitative graph analysis: Deriving bounds for the entropies of hierarchical graphs. An important application area of information-theoretic methods applied to networks is, e.g., QSPR where our main focus lies on the examination of graph classes which are widely used in chemical graph theory and computational biology. Generally, there are two main directions in quantitative graph analysis: (i) Comparing and (ii) characterizing networks. Network comparison addresses the problem of measuring their structural similarity or distance, see, e.g., [15] , [16] , [17] , [18] , [19] , [20] , [21] , [22] . In contrast, to characterize a network means that one has to infer structural network statistics which capture certain structural information of the networks [23] , [24] , [25] , [26] . For giving a short review on information-theoretic methods to characterize graphs [6] , [7] , [14] , [27] , [28] , [29] , we want to emphasize that the problem of quantifying certain structural information of systems was a starting point of an emerging field that deals with applying information-theoretic techniques to networks, e.g., for investigating living systems [30] , [31] , [32] , [33] , [34] , [35] . As a fundament, SHANNON [36] extended the concept of entropy that was known in thermodynamics for transmitting information. For this, he considered a message transmitted through information channels as a certain set of symbols denoted as an outcome which was selected from the ensemble of all k such sets containing the same total number of symbols N [27] . By assigning probabilities p 1 , p 2 ,…, p k to each i -th outcome based on the quantities where N i denotes the number of symbols of the i -th outcome, SHANNON characterized the entropy H as the uncertainty of the expected outcome [27] . Then, the classical SHANNON-entropy formula to measure the average entropy of information per communication symbol can be expressed by (1) H m is often called the mean information. Additionally, BRILLOUIN [37] defined the total information as (2) Now, the topics we just mentioned [30] , [31] , [32] , [33] , [34] , [35] have been mainly influenced by the, at that time, novel insight that an inferred or constructed graph structure can be considered as the result of a certain information process or communication between the elements of the underlying system [14] , [36] . As a consequence [7] , [38] , Equation (1) and (3) Equation (2) can be now interpreted as the mean information content and the total information content (4) of a graph G . Here, | V | denotes the number of vertices of a graph G , k denotes the number of different (obtained) sets of vertices, | V i | is the number of elements in the i -th set of vertices, and it holds . The first attempt in this direction was given by [34] who developed a technique to determine the structural information content of a graph. This technique is based on the principle of finding distinguishable vertices of a graph to apply SHANNON's entropy (Equation (3) and Equation (4)) for determining the information content of such a graph-based system. Also, [38] , [39] , [40] , [41] investigated this problem by using algebraic methods, i.e., determining the automorphism groups of graphs. We remark that the mentioned methods, e.g., [38] , [39] , [40] , [41] , [34] , [35] for measuring the structural information content of a graph-based system are based on the following principle: Starting from a certain equivalence criterion, a graph-based system with n elements can be partitioned into k classes, see, e.g., [14] . As a consequence, a probability distribution can be obtained that leads directly to the definition of an entropy of the system under consideration (Equation (3) and Equation (4)). Following [14] , [38] , [28] , the structural information content of such a system is interpreted as the entropy of the underlying graph topology. As a remark, we note that graph entropy definitions which are rooted in information theory can be found in [42] , [43] , [44] , [45] . A major contribution of this paper addresses the problem of finding bounds for the entropies of hierarchical graphs, which often occurs in chemical graph theory and computational and systems biology. Here, the term “hierarchical” means that we deal with graphs having a distinct vertex that is called a root. To achieve this goal, we use an approach for determining the entropy of undirected and connected graphs that has been recently presented in [28] . In contrast to the classical methods which we have already outlined above, this method is based on assigning a probability value to each vertex in a graph by using a special information functional. The information functional we have presented in [28] is based on metrical properties of graphs, more precisely, on so-called j -spheres. In terms of practical applications, we want to point that the task of deriving bounds for the entropies of graphs is crucial because the exact entropy value can often not be calculated concretely, especially regarding large graphs. For this reason, entropy bounds for special graph classes help to reduce the complexity of such problems and can be also used for characterizing graphs or graph classes by using information-theoretic measures. As mentioned, hierarchical (rooted) graph structures do have a large application potential in chemical graph theory and computational biology. Therefore, we restrict our analysis on such graph structures. A further reason for focusing on rooted graphs is, to our knowledge, such a study does not exist. Another contribution of this paper deals with demonstrating the practical ability of the used graph entropy approach [28] by interpreting the produced numerical results. Starting from two graph classes, ordinary rooted trees and so-called generalized trees [46] , [47] , we show that our entropy measure captures important structural information meaningfully. To summarize the main contribution of this paper, Figure (1) shows the overall approach exemplarily. ANALYSIS In this section, we briefly outline some applications of hierarchical graphs in chemical graph theory and computational biology. There is a universe of problems dealing with trees for modeling and analyzing chemical structures [48] , [1] , [2] , [3] , [4] . However, also rooted tree structures are of particular interest because, e.g., considering such graph classes often helps to solve more general graph problems. In the following, we state some interesting applications of rooted trees in chemical graphs theory: Enumeration and coding problems of chemical structures by using rooted trees [49] , [50] , [51] , [52] . Describing so-called signatures as molecular descriptors for problems in QSAR [53] . Graph polynomials of hierarchical graphs [54] . Chemical graph analysis by using algebraic and metrical graph properties [55] , [56] , [57] , [58] . - Enumeration and coding problems of chemical structures by using rooted trees [49] , [50] , [51] , [52] . - Describing so-called signatures as molecular descriptors for problems in QSAR [53] . - Graph polynomials of hierarchical graphs [54] . - Chemical graph analysis by using algebraic and metrical graph properties [55] , [56] , [57] , [58] . BIOLOGY Tree structures have been intensely investigated for solving and modeling biological problems. In particular, rooted trees often serve as an important graph representation for many biological classification problems as well as for problems in evolutionary biology [59] . To summarize some known approaches involving hierarchical graph structures, we state the following listing: Reconstruction problems and so-called supertree methods in phylogenetics [60] , [61] , [62] , [63] , [59] . Modeling and analyzing RNA structures [64] , [65] . Supervised and unsupervised graph classification problems in computational biology [66] , [67] . Clustering problems in computational biology [68] , [69] . - Reconstruction problems and so-called supertree methods in phylogenetics [60] , [61] , [62] , [63] , [59] . - Modeling and analyzing RNA structures [64] , [65] . - Supervised and unsupervised graph classification problems in computational biology [66] , [67] . - Clustering problems in computational biology [68] , [69] . A METHOD FOR DETERMINING THE ENTROPY OF GRAPHS In this section, we briefly repeat the method to measure the entropy of arbitrary undirected and connected networks, see [28] . As mentioned, we will interpret and define the structural information content as the entropy of the underlying graph topology [28] . The method we want to use is mainly based on the principle to assign a probability value to each vertex in a graph by using a certain information functional for quantifying structural information in a graph and, hence, for determining its entropy. The information functional that has been used [28] is based on determining the so-called j -spheres of a graph. Before outlining the main construction steps of this approach, we want to mention that [70] also used so-called vertex distance degree sequences (DDS) to develop the idea of a graph center for chemical structures. Interestingly, the derived DDS-distributions correspond to vertex distributions by using j -spheres. Similarly to the just described idea, one main idea of the approach of [28] to determine the entropy of a graph was to use a connectivity concept to express neighborhood relations of its vertices. Finally, it turned out that a natural procedure for expressing such relations is to calculate the number of the first neighboring vertices, the number of the second neighboring vertices, etc. and, hence, this just corresponds to the definition of the j -sphere. As an example, Figure (2) shows the process of determining j -spheres visually. For example, we get | S 1 ( v i , G )| = 5 and | S 2 ( v i , G )| = 9. In order to repeat the main construction step of the above mentioned graph entropy method, we first express some mathematical preliminaries [71] , [72] , [28] . We define an undirected, finite and connected graph by G  = ( V,E ),| V |<∞, . G is called connected if for arbitrary vertices v i and v j there exists an undirected path from v i to v j . Otherwise, we call G unconnected. G UC denotes the set of finite, undirected and connected graphs. The degree of a vertex v ∈ V is denoted by δ ( v ) and equals the number of edges e ∈ E which are incident with v . In order to measure distances between vertices in a graph, we denote d ( u,v ) as distance between u ∈ V and v ∈ V expressed as the minimum length of a path between u,v . We notice that d ( u,v ) is a metric. We call the quantity σ ( v ) = max u ∈ V d ( u,v ) the eccentricity of v ∈ V . Further, ρ ( G ) = max v ∈ V σ ( v ) is called the diameter of G . The j -sphere of a vertex v i regarding G ∈ G UC is defined as the set, (5) Now, we state the definition of a special information functional that has been introduced in [28] to define the entropy of a graph. Here, the information functional f V quantifies structural information of a graph G by using the cardinalities of the corresponding j -spheres. Definition 2.1 Let G ∈ G UC with arbitrary vertex labels . For the vertex v i ∈ V , the information functional f V is defined as (6) f V ( v i ) captures structural information of G by using metrical properties of G. The parameters α and c k are introduced to weight structural characteristics or differences of G in each sphere, e.g., a vertex with a large degree. As a remark, we generally see that it always (7) (8) (9) holds [28] . Hence, the c k have to be chosen such that they are not equal, e.g, c 1 > c 2 >…> c ρ . Finally, we observe that the variation of c k and α aims to study the local information spread in a network. Definition 2.2 The vertex probabilities are defined by the quantities (10) Definition 2.3 Let G  = ( V,E )∈ G UC . Then, we define the entropy of G by (11) As outlined in [28] , we recall that the process of defining information functionals and, hence, the entropy of a graph by using structural properties or graph-theoretical quantities is not unique. Consequently, each information functional captures structural information of a given graph differently. Further, we pointed out [28] that the parameter α can always be determined via an optimization procedure based on a given data set and, hence, is uniquely defined for a given classification problem. BOUNDS FOR THE ENTROPIES OF HIERARCHICAL GRAPHS In this section, we derive bounds for the entropies of hierarchical graphs. For this, we use the entropy measure explained in the previous section. As mentioned, in this paper we choose the class of rooted trees and so-called generalized trees [47] . We notice that a generalized tree contains an ordinary rooted tree as a special case [47] . Further, it turned out that generalized trees can be very useful for solving current problems in applied discrete mathematics, computer science and systems biology [47] , [73] , [74] , [66] . To start with the problem of finding entropy bounds, we first define the mentioned graph classes. Directed generalized trees have already been defined in [47] . Definition 2.4 An undirected graph is called undirected tree if this graph is connected and cycle free. An undirected rooted tree T  = ( V,E ) is an undirected graph which has exactly one vertex r ∈ V for which every edge is directed away from the root r. Then, all vertices in T are uniquely accessible from r. The level of a vertex v in a rooted tree T is simply the length of the path from r to v. The path with the largest path length from the root to a leaf is denoted as h. Definition 2.5 As a special case of T  = ( V,E ) we also define an ordinary w-tree denoted as T w where w is a natural number. For the root vertex r, it holds δ ( r ) =  w and for all internal vertices r ∈ V holds δ ( v ) =  w +1. Leaves are vertices without successors. A w-tree is fully occupied, denoted by T w o , if all leaves possess the same height h. Definition 2.6 Let T  = ( V,E 1 ) be an undirected finite rooted tree . | L | denotes the cardinality of the level set L : = { l 0 , l 1 …, l h }. The longest length of a path in T is denoted as h. It holds h  = | L |−1. Λ∶ V → L is a surjective mapping and it is called a multi level function if it assigns to each vertex an element of the level set L. A graph H  = ( V,E GT ) is called a finite, undirected generalized tree if its edge set can be represented by the union E GT : =  E 1 ∪ E 2 ∪ E 3 , where E 1 forms the edge set of the underlying undirected rooted tree T. E 2 denotes the set of horizontal Across-edges. A horizontal Across-edge does not change a level i. E 3 denotes the set of edges which change at least one level. As an example, Figure (3) shows an undirected rooted tree T and its corresponding undirected generalized tree H . It holds | L | = 4 and h  = | L |−1 = 3. Starting from the definition of the information functional f V (see Equation (6)), we first express a technical assertion proven in [75] that states a relationship between certain vertex probabilities. Starting from the definition of f V , this assertion expresses that it is always possible to infer inequalities between the corresponding vertex probabilities. In order to achieve this, we also use simple estimations of parameters which we introduce in Lemma (2.1). Finally, we will see that by applying this lemma, we can easily derive entropy bounds for the graph classes under consideration. Hence, the following lemma serves as a fundament for the proofs of some theorems we want state in this section. Lemma 2.1 Let T be a rooted tree with a certain height h and let f V be the information functional represented by Equation (6) . Further, we define the quantities (12) It holds (13) where (14) and . p V ( v ik ) denotes the vertex probability of v ik regarding f V . Further, v ik denotes the k-th vertex on the i-th level , 1≤ i ≤ h ,1≤ k ≤ σ i . σ i denotes the number of vertices on level i. In the following, we derive entropy bounds for hierarchical networks by applying Lemma (2.1). Because Lemma (2.1) provides inequalities between vertex probabilities for each vertex in a graph, the main idea for inferring entropy bounds is to add up the obtained inequalities. As a result, we get relations between graph entropy measures for hierarchical networks which can be interpreted as entropy bounds. Also, the conclusion of Lemma (2.1) implies that by varying the Inequalities (13), special entropy bounds can be obtained. Theorem 2.2 Let T be a rooted tree. For the entropy of T, it holds the inequality (15) where (16) Proof : To start the proof, we consider Inequality (13) in Lemma (2.1). If we multiply this inequality by -1, we get (17) Now, by using the assertion of Lemma (2.1) and the monotonicity property of the logarithm function, we obtain (18) If we perform this step for each vertex v ik ∈ V and then add up the obtained inequalities, we get Because by definition it holds we obviously get (19) Now, by using the definition of the graph entropy (see Definition (2.3)), Inequality (19) finally becomes to This completes the proof of the theorem. By considering special classes of rooted trees, we obviously get special bounds for the corresponding entropies. Theorem 2.3 Let T w o be a fully occupied w-tree. For the graph entropy of T w o holds (20) Proof : Let T w o be a fully occupied w -tree. Therefore, it holds ρ  = 2 h . Starting from the root vertex v 01 , all other vertices are reachable. Hence, we obtain | S h ( v 01 , T w o )| =  w h . Then, we clearly get | S j ( v ik ,T w o )|< w h , 1≤ j ≤2 h . Hence, we can set ω  =  w h . Now, the proof of the Theorem (2.3) can be obtained by analogously applying the same technique and steps of the proof of Theorem (2.2). Theorem 2.4 Let T w be an ordinary w-tree. For the graph entropy of T w holds (21) Proof : Let T w be an ordinary w -tree. Actually, it holds ω ≤ w h . From this, and by applying Lemma (2.1), we yield (22) Finally, we obtain the assertion of the theorem by applying the same technique and steps performed in the proof of Theorem (2.2). We emphasize that each information functional captures structural information of a graph differently. Obviously, the resulting graph entropies are also different. If we now apply Theorem (2.2) and additionally assume an abstract information functional f * , we find as a consequence of the previous theorems that one can infer a statement that expresses a relationship between the resulting graph entropies. These kind of inequalities can be used to study the influence of an information functional on the final graph entropies. Corollary 2.5 Let T be a rooted tree and let f * ( v ik ) be an information functional such that (23) p V ( v ik ) and p * ( v ik ) denotes the vertex probability value ( k-th vertex on the i-th level ) regarding f V and f * . Then, it holds (24) - E 1 forms the edge set of the underlying undirected rooted tree T. - E 2 denotes the set of horizontal Across-edges. A horizontal Across-edge does not change a level i. - E 3 denotes the set of edges which change at least one level. ENTROPY BOUNDS FOR GENERALIZED TREES In this section, we give a first attempt to state entropy bounds for certain classes of generalized trees. By only allowing generalized trees with specific edge sets, we get bounds for the entropies of special classes of generalized trees. The assertion of the next theorem means the following: The entropy of a specific generalized tree can be characterized by the entropy of another generalized tree that is extremal with respect to a certain structural property. Theorem 2.6 Let H  = ( V,E GT ) be a generalized tree with E GT : =  E 1 ∪ E 2 , i.e., H possesses Across-edges only. Starting from H, we define H * as the generalized tree with the maximal number of Across-Edges on each level i ,1≤ i ≤ h . First, there exist positive real coefficients c k which satisfy the inequality system (25) Second, it holds (26) Proof : We assume H  = ( V,E GT ) such that E GT  =  E 1 ∪ E 2 . Besides edges e ∈ E 1 , H possesses Across-edges e ∈ E 2 only. Then, we first determine Now, we consider H * and find that the total number of Across-edges for each level equals . Except for the root vertex v 01 , we further see that in particular | S 1 ( v ik , H * )|≥| S 1 ( v ik , H )| holds. This corresponds to the fact that H * has normally more connections than H . Finally, the cardinalities of the remaining j -spheres of H * increase correspondingly. Therefore, we conclude that we can find coefficients c k >0 such that the Inequality System ( 25 ) holds. But from this, we directly obtain (27) if α >1, 1≤ i ≤ h , 1≤ k ≤ σ i . f H V ( v ik ) and denotes the information functional f V regarding H and H * , respectively. We want to emphasize that it holds . Similarly as in Lemma (2.1), by using the quantities we yield (28) Finally, Equation (26) can be obtained by applying the assertion of Theorem (2.2). We want to remark that by using the main argument of Theorem (2.6), one can easily express similar assertions for other specific generalized tree classes. To finalize this section, we state a simple lemma concerning the maximum entropy of a graph. Then, we apply this assertion to generalized trees. Lemma 2.7 Let K | V |,| V | be the complete graph with | V | vertices . K | V |,| V | maximizes the graph entropy with respect to the information functional f V , i.e. , (29) Theorem 2.8 Let H  = ( V H ,E ) be an arbitrary generalized tree and let H | V |,| V | be the complete generalized tree such that | V H |≤| V |. It holds (30) Proof : The proof follows directly by using the monotonicity property of the logarithm function and the assertion of Lemma (2.7). Corollary 2.9 Let H *  = ( V * , E * ) and it holds | V * |≤| V |. (31) - First, there exist positive real coefficients c k which satisfy the inequality system (25) - Second, it holds (26) RESULTS AND DISCUSSION This section aims to demonstrate that our entropic measure is able to distinguish certain graph classes of hierarchical graphs structurally by comparing the resulting cumulative entropy distributions. As a result of our numerical analysis, we will find that the calculated entropy distributions can be clearly distinguished and, hence, also the graph classes under consideration. Thus, this proves that the entropy measure captures significant structural information. To start, we give a short overview on the key steps we performed to carry out our numerical analysis: Generate the data classes C α RT and C α GT . For this, we randomly create rooted trees with a fixed height h . Further, we use these trees to generate generalized trees (see also below). Choose the parameters c k . Vary α to compute I f V for different classes C α RT and C α GT . Compute the mean of the entropies for each such class denoted by μ and the variances σ 2 . Compute and interpret the cumulative entropy distributions for C α RT and C α GT . We remark that the intuitive meaning of the entropy I f V ( G ) has been already explained in [28] . Now, we start our numerical section with defining some data classes. These data classes emerge from starting with fixed sets of hierarchical graphs and by varying certain parameters. Definition 3.1 The class C α RT denotes a certain set of rooted trees whose entropies have been computed by using the value α and the coefficient vector ( c 1 , c 2 ,…, c ρm ). We set Correspondingly, C α GT denotes a certain set of generalized trees whose entropies have been computed by also using the value α and ( c 1 , c 2 ,…, c ρm ). In order to compute the graph entropies concretely, we choose the c k values such that holds, and set c 1 : = 6, c 2 : = 5, c 3 : = 4, c 4 : = 3, c 5 : = 2, c 6 : = 1. A class C α RT was generated by providing a fixed value h as the height of each tree . Further, each has an unique root vertex and the remaining vertices and edges were created randomly. To generate a class C α GT , we first compute an arbitrary random tree with height h as mentioned and, then, a certain number of additional edges of a generalized tree randomly. The numerical results of our study are summarized in Table (1) . As we have already mentioned, we computed the entropies of certain classes of rooted and generalized trees with a fixed height h by varying the α -value. We notice that by providing a fixed height h , the number of vertices of T or H can be nevertheless extremely different. Now, from Table (1) we see that the resulting entropies of generalized trees are in average larger than the entropies of rooted trees, depending on α . This corresponds to our intuition that a generalized tree can be generally considered as structurally more complex than an ordinary rooted tree. To argue in this way, we apply a definition due to [11] that states, the higher the information content (entropy) of a system is, the more complex is the system. Further, one finds that the variances of the generated tree and generalized tree classes can be clearly distinguished. This can be also explained by the fact that a set of generalized trees is in average more structurally complex and diverse than a set of rooted trees with the same height h . Also, we observe that the larger the α -value of C α RT and C α GT is, the smaller is the resulting mean and variance. Additionally, we also find that the entropy of a graph decreases with an increasing α -value. In the following, we interpret the cumulative entropy distributions (for h  = 8) which are shown in Figure (4) and Figure (5) . Such a distribution expresses the percentage rate of graphs (of the cardinality of C α RT or C α GT ) which possess an entropy value less or equal I f V ( T ) or I f V ( H ). As an important observation, we find that for α ∈{2,3,4,5,10} the cumulative entropy distributions of C α RT (see Figure (4) ) are clearly different from the corresponding cumulative distributions of C α GT (see Figure (5) ). Hence, we interpret this result such that the entropy measure (by incorporating the information functional f V ) is able to detect that we deal with different graph classes. The reason why the distribution for C 1 RT and C 1 GT seems to be almost equal is related to the fact that our entropy measure has always a maximum at α  = 1. For this case, the entropies of trees- and generalized trees are almost equal. We remark that we have already been proven that the entropy functional (by using f V ) possesses for every graph a maximum at α  = 1, see [28] . As the main result of this section, we find that our entropy measure captures important structural information meaningfully and, hence, detects that rooted and generalized trees manifest structurally different graph classes. The x -axis corresponds to the entropy I f V ( T ) and the y -axis represents the cumulative entropy distribution for C 1 RT - C 5 RT and C 10 RT . The x -axis corresponds to the entropy I f V ( H ) and the y -axis represents the cumulative entropy distribution for C 1 GT - C 5 GT and C 10 GT . It holds |C α RT | = |C α GT | = 100. α varies in natural numbers from 1 to 10, the step size is equal to 1. TABLE: μ represent the means of the entropies for each class C α RT and C α GT and σ 2 denotes the corresponding variance. h = 7 C 1 RT C 1 GT C 2 RT C 2 GT C 3 RT C 3 GT C 4 RT C 4 GT C 5 RT C 5 GT μ 6.029 6.218 1.766 2.846 1.123 1.987 0.895 1.629 0.775 1.423 σ 2 0.595 0.614 0.828 1.221 0.611 1.110 0.506 0.955 0.444 0.841 C 6 RT C 6 GT C 7 RT C 7 GT C 8 RT C 8 GT C 9 RT C 9 GT C 10 RT C 10 GT μ 0.701 1.287 0.649 1.188 0.610 1.113 0.580 1.054 0.556 1.005 σ 2 0.402 0.758 0.373 0.696 0.351 0.648 0.333 0.611 0.320 0.580 - Generate the data classes C α RT and C α GT . For this, we randomly create rooted trees with a fixed height h . Further, we use these trees to generate generalized trees (see also below). - Choose the parameters c k . - Vary α to compute I f V for different classes C α RT and C α GT . - Compute the mean of the entropies for each such class denoted by μ and the variances σ 2 . - Compute and interpret the cumulative entropy distributions for C α RT and C α GT . SUMMARY AND CONCLUSION In this paper, we investigated the problem of finding entropy bounds for hierarchical graphs. Based on an entropic measure to determine the entropy of graphs, we derived certain estimations for the corresponding entropies. We now summarize the main contributions and arguments of our paper as follows: We defined two classes of hierarchical graphs, rooted trees and generalized trees. A generalized tree is structurally more complex than an ordinary rooted tree because it contains a rooted tree as a special case. As a main result, we proved entropy bounds for rooted trees as well as for generalized trees. Also, assuming specific structural properties of the graph classes under consideration led us to characteristic bounds. It is important to note that we presented only one method for finding those entropy bounds, different bounds can be derived by using different entropy measures and techniques. To classify these bounds, we call the derived bounds implicit bounds because the entropy of a graph was estimated by a quantity that contains another graph entropy expression. Generally, bounds to estimate the entropy of graphs are very useful for practical applications because the real entropy value is often difficult to obtain. Particularly, an interesting result represents Corollary (2.5). From this assertion, we found that an information functional (e.g., f V or f * ) has an influence on the resulting graph entropy because each such functional quantifies structural information differently. Hence, Corollary (2.5) can be used for describing relations of the resulting entropies by using different information functional. Further, we performed a numerical study to demonstrate the practical ability of our graph entropy measure. Based on two generated graph classes of rooted and generalized trees, we computed the entropies of each such class by varying the free parameter α . Then, we calculated the cumulative entropy distributions for these classes. From the obtained results we could conclude that our entropy measure can distinguish between rooted trees and generalized trees. This implied that the used entropy measure captures significant structural information because we know that rooted trees and generalized trees are different graph classes. REFERENCES [1] Bonchev D Rouvray DH 1991 Chemical Graph Theory. Introduction and Fundamentals Abacus Press [2] Diudea MV Gutman I Jäntschi L 2001 Molecular Topology Nova Publishing [3] Gutman I Polansky OE 1986 Mathematical Concepts in Organic Chemistry Springer [4] Trinajstić N 1992 Chemical Graph Theory CRC Press [5] Batagelj V 1988 Similarity measures between structured objects. Graovac A Dubrovnik/Yugoslavia: Proceedings of an International Course and Conference on the Interfaces between Mathematics, Chemistry and Computer Sciences 25 40 [6] Bonchev D Trinajstić N 1977 Information theory, distance matrix and molecular branching. Journal of Chemical Physics 67 4397 4533 [7] Bonchev D 1983 Information Theoretic Indices for Characterization of Chemical Structures Chichester Research Studies Press [8] Rupp M Proschak E Schneider G 2007 Kernel approach to molecular similarity based on iterative graph similarity. J Chem Inf Comput Sci 47 2280 2286 [9] Skvortsova MI Baskin II Stankevich IV Palyulin VA Zefirov NS 1998 Molecular similarity. I. Analytical description of the set of graph similarity measures. J Chem Inf Comput Sci 38 785 790 [10] Benigni R 2003 Quantitative Structure-Activity Relationship (QSAR) Models of Mutagens and Carcinogens CRC Press [11] Devillers J Balaban AT 2000 Topological Indices and Related Descriptors in QSAR and QSPAR CRC Press [12] Diudea MV 2001 QSPR/QSAR Studies by Molecular Descriptors Nova Publishing [13] Bonchev D 2000 Overall connectivities and topological complexities: A new powerful tool for QSPR/QSAR. J Chem Inf Comput Sci 40(4) 934 941 [14] Bonchev D 2003 Complexity in Chemistry. Introduction and Fundamentals Taylor and Francis [15] Bunke H 1983 What is the distance between graphs? Bulletin of the EATCS 20 35 39 [16] Bunke H 2000 Recent developments in graph matching. 15-th International Conference on Pattern Recognition 2 117 124 [17] Bunke H Neuhaus M 2007 Graph matching. Exact and error-tolerant methods and the automatic learning of edit costs. Cook D Holder LB Mining Graph Data Wiley-Interscience 17 32 [18] Sobik F 1982 Graphmetriken und Klassifikation strukturierter Objekte. ZKI-Informationen, Akad Wiss DDR 2(82) 63 122 [19] Sobik F 1986 Modellierung von Vergleichsprozessen auf der Grundlage von Ähnlichkeitsmaßen für Graphen. ZKI-Informationen, Akad Wiss DDR 4 104 144 [20] Kaden F Graphmetriken und Distanzgraphen. ZKI-Informationen, Akad Wiss DDR 2(82) 1 63 [21] Zelinka B 1975 On a certain distance between isomorphism classes of graphs. Časopis pro pest. Mathematiky 100 371 373 [22] Zhu P Wilson RC 2005 A study of graph spectra for comparing graphs. 16-th British Machine Vision Conference, Oxford Brookes University [23] Brinkmeier M Schank T 2005 Network statistics. Brandes U Erlebach T Network Analysis, Lecture Notes of Computer Science Springer 293 317 [24] Dorogovtsev SN Mendes JFF 2003 Evolution of Networks. From Biological Networks to the Internet and WWW Oxford University Press [25] Barabási AL 2003 How Everything Is Connected to Everything Else and What It Means Plume, Reissue edition [26] Mason O Verwoerd M 2007 Graph theory and networks in biology. IET Systems Biology 1(2) 89 119 [27] Bonchev D Rouvray DH 2005 Complexity in Chemistry, Biology, and Ecology Mathematical and Computational Chemistry, Springer [28] Dehmer M Emmert-Streib F 2008 Structural information content of networks: Graph entropy based on local vertex functionals. Computational Biology and Chemistry 32 131 138 [29] Sahu PK Lee SL 2008 Net-sign identity information index: A novel approach towards numerical characterization of chemical signed graph theory. Chemical Physics Letters In press [30] Morowitz H 1953 Some order-disorder considerations in living systems. Bull Math Biophys 17 81 86 [31] Quastler H 1953 Information Theory in Biology University of Illinois Press [32] Dancoff S Quastler H 1953 Information content and error rate of living things. Quastler H Essays on the Use of Information Theory in Biology University of Illinois Press 263 274 [33] Linshitz H 1953 The information content of a battery cell. Quastler H Essays on the Use of Information Theory in Biology University of Illinois Press 14 15 [34] Rashewsky N 1955 Life, information theory, and topology. Bull Math Biophys 17 229 235 [35] Trucco E 1956 A note on the information content of graphs. Bulletin of Mathematical Biology 18(2) 129 135 [36] Shannon CE Weaver W 1997 The Mathematical Theory of Communication University of Illinois Press [37] Brillouin L 1956 Science and Information Theory New York Academic Press [38] Mowshowitz A 1968 Entropy and the complexity of the graphs I: An index of the relative complexity of a graph. Bull Math Biophys 30 175 204 [39] Mowshowitz A 1968 Entropy and the complexity of graphs II: The information content of digraphs and infinite graphs. Bull Math Biophys 30 225 240 [40] Mowshowitz A 1968 Entropy and the complexity of graphs III: Graphs with prescribed information content. Bull Math Biophys 30 387 414 [41] Mowshowitz A 1968 Entropy and the complexity of graphs IV: Entropy measures and graphical structure. Bull Math Biophys 30 533 546 [42] Fujii JI Yuki S 1997 Entropy and coding for graphs. Int J Math Stat Sci 6(1) 63 77 [43] Kieffer J Yang E 1997 Ergodic behavior of graph entropy. Electronic Research Announcements of the American Mathematical Society 3 11 16 [44] Körner J 1973 Coding of an information source having ambiguous alphabet and the entropy of graphs. Transactions of the 6-th Prague Conference on Information Theory 411 425 [45] Simonyi G 2001 Perfect graphs and graph entropy. An updated survey. Ramirez-Alfonsin J Reed B Perfect Graphs John Wiley & Sons 293 328 [46] Harary F 1969 Graph Theory Addison Wesley Publishing Company [47] Mehler A Dehmer M Gleim R 2004 Towards logical hypertext structure — A graph-theoretic perspective. Böhme T Heyer G Proceedings of the Fourth International Workshop on Innovative Internet Computing Systems (I2CS '04), Lecture Notes in Computer Science 3473 136 150 [48] Aringhieri R Hansen P Malucelli F 2001 A linear algorithm for the hyper-wiener index of chemical trees. J Chem Inf Comput Sci 41(4) 958 963 [49] Aringhieri R Hansen P Malucelli F 2003 Chemical trees enumeration algorithms. 4OR, A Quarterly Journal of Operations Research 1(1) 67 83 [50] Müller WR Szymanski K Knop JV Trinajstić N 1995 A comparison between the matula numbers and bit-tuple notation for rooted trees. J Chem Inf Comput Sci 35(2) 211 213 [51] Matula DW 1968 A natural rooted tree enumeration by prime factorization. SIAM Review 10 273 [52] Elk SB 1990 A canonical ordering of polybenzenes and polyadamantanes using a prime factorization technique. J Math Chem 4 55 68 [53] Visco DP Pophale RS Rintoul MD Faulon JL 2002 Developing a methodology for an inverse quantitative structure-activity relationship using the signature molecular descriptor. Journal of Molecular Graphics and Modelling 20 429 438 [54] Zmazeka B Žerovnik J 2007 The hosoya-wiener polynomial of weighted trees. Croatica Chemica Acta 80(1) 75 80 [55] Bohanec S Perdih M 1993 Symmetry of chemical structures: A novel method of graph automorphism group determination. J Chem Inf Comput Sci 33 719 726 [56] Chepoi V 1996 On distances in benzenoid systems. J Chem Inf Comput Sci 36 1169 1172 [57] Liu SC Tong LD Yeh JY 2000 Trees with the minimum wiener number. International Journal of Quantum Chemistry 78(5) 331 340 [58] Skorobogatov VA Dobrynin AA 1988 Metrical analysis of graphs. MATCH 23 105 155 [59] Semple C Steel M 2000 A supertree method for rooted trees. Discrete Applied Mathematics 105(1-3) 147 158 [60] Felsenstein J 2003 Inferring Phylogenies Sinauer Associates [61] Foulds LR 1992 Graph Theory Applications Springer [62] Steel M Dress A Boker S 2000 Simple but fundamental limitations on supertree and consensus tree methods. Systematic Biology 49 363 368 [63] Semple C Steel M 2003 Phylogenetics. Graduate Series Mathematics and its Applications Oxford University Press [64] Höchstmann M Töller T Giegerich R Kurtz S 2003 Local similarity in RNA secondary structures. Proceedings of the IEEE Computational Systems Bioinformatics Conference (CSB'03) 159 168 [65] Shapiro BA Zhang K 1990 Comparing multiple RNA secondary structures using tree comparisons. Comp Appl Biosci 6(4) 309 318 [66] Emmert-Streib F Dehmer M Kilian J 2005 Classification of large graphs by a local tree decomposition. Arabnia HR Scime A Proceedings of DMIN'05, International Conference on Data Mining, Las Vegas, June 20–23 200 207 [67] Horváth T Gärtner T Wrobel S 2005 Cyclic pattern kernels for predictive graph mining. Proceedings of the 2004 ACM SIGKDD, International Conference on Knowledge Discovery and Data Mining 158 167 [68] Gambin A Slonimski PP 2005 Hierarchical clustering based upon contextual alignment of proteins: A different way to approach phylogeny. Comptes Rendus Biologies 328(1) 1 22 [69] Morihiro H Tatsuya A Hitoshi N 2006 A novel clustering method for analysis of biological networks using maximal components of graphs. IPSJ SIG Technical Reports 99 1 8 [70] Bonchev D 1989 The concept for the center of a chemical structure and its applications. Journal of Molecular Structure: Theochem 185 155 168 [71] Bang-Jensen J Gutin G 2002 Digraphs. Theory, Algorithms and Applications London, Berlin, Heidelberg Springer [72] Halin R 1989 Graphentheorie Akademie Verlag [73] Dehmer M Emmert-Streib F Mehler A Kilian J 2006 Measuring the structural similarity of web-based documents: A novel approach. International Journal of Computational Intelligence 3(1) 1 7 [74] Emmert-Streib F Dehmer M Liu J Mühlhäuser M 2006 Ranking genes from DNA microarray data of cervical cancer by a local tree comparison. International Journal of Biomedical Science 1(1) 17 22 [75] Dehmer M 2008 Information processing in complex networks: Graph entropy and information functionals. Applied Mathematics and Computation 201 82 94