A survey of recent results in (generalized) graph entropies
---
paper_title: ENTROPY AND THE COMPLEXITY OF GRAPHS: II. THE INFORMATION CONTENT OF DIGRAPHS AND INFINITE GRAPHS

paper_content:

of the structural information content of an (undirected) graph X was defined, and its properties explored. The class of graphs on which Ig is defined is here enlarged to include directed graphs (digraphs). Most of the properties of I 0 observed in the undirected case are seen to hold for digraphs. The greater generality of digraphs allows for a construction which shows that there exists a digraph having information content equal to the entropy of an arbitrary partition of a given positive integer. The measure Ig is also extended to a measure defined on infinite (undirected) graphs. The properties of this extension are discussed, and its applicability to the problem of measuring the complexity of algorithms is considered.
---
paper_title: A note on the information content of graphs

paper_content:

The role played by the group of a graph in determining sets of equivalent points is exposed and illustrated by a few simple examples.
---
paper_title: A history of graph entropy measures

paper_content:

This survey seeks to describe methods for measuring the entropy of graphs and to demonstrate the wide applicability of entropy measures. Setting the scene with a review of classical measures for determining the structural information content of graphs, we discuss graph entropy measures which play an important role in a variety of problem areas, including biology, chemistry, and sociology. In addition, we examine relationships between selected entropy measures, illustrating differences quantitatively with concrete examples.
---
paper_title: Entropy and the complexity of graphs: III. Graphs with prescribed information content

paper_content:

The connection between the adjacency matrix and the automorphisms of a digraph is used to develop a method for studying the automorphism group and, thus, the information content (Mowshowitz 1968a, b) of a digraph. An algorithm is given for constructing digraphs with zero information content, and the properties of such digraphs are examined. Moreover, an algorithm for computing the automorphism group of a digraph is presented and is used to find conditions which insure that two digraphs have the same information content. This algorithm is further used to determine the information content of digraphs whose adjacency matrices have prescribed properties.
---
paper_title: Entropy and the complexity of graphs: IV. Entropy measures and graphical structure

paper_content:

The structural information contentI g (X) of a graphX was treated in detail in three previous papers (Mowshowitz 1968a, 1968b, 1968c). Those investigations ofI g point up the desirability of defining and examining other entropy-like measures on graphs. To this end the chromatic information contentI c (X) of a graphX is defined as the minimum entropy over all finite probability schemes constructed from chromatic decompositions having rank equal to the chromatic number ofX. Graph-theoretic results concerning chromatic number are used to establish basic properties ofI c on arbitrary graphs. Moreover, the behavior ofI c on certain special classes of graphs is examined. The peculiar structural characteristics of a graph on which the respective behaviors of the entropy-like measuresI c andI g depend are also discussed.
---
paper_title: Life, information theory, and topology

paper_content:

The information content of an organism determines to a large extent its ability to perform the basic vital functions: selection of food, breaking up of the food molecules into appropriate parts, selection of those parts, and their assimilation. The information content needed is very large and requires a sufficiently large complexity of the organism. The information content of an organism is largely determined by the information content of the constituent organic molecules. The information content of the latter is in its turn determined by the number of physically distinguishable atoms or radicals of which the molecule is composed. The different arrangements of atoms in a molecule are represented by the structural formula, which is basically a graph. It is shown that the topology of this graph also determines to a large extent the information content. Different points of a graph may be physically indistinguishable; in general, however, they are different in regard to their topological properties. A study of the relations between the topological properties of graphs and their information content is suggested, and several theorems are demonstrated. A relation between topology and living processes is thus found also on the molecular level.
---
paper_title: Entropy and the complexity of graphs. I. An index of the relative complexity of a graph.

paper_content:

The structural information content (Rashevsky, 1955; Trucco 1956a, b)I g (X) of a graphX is defined as the entropy of the finite probability scheme constructed from the orbits of its automorphism groupG(X). The behavior ofI g on various graph operations—complement, sum, join, cartesian product and composition, is examined. The principal result of the paper is the characterization of a class of graph product operations on whichI g is semi-additive. That is to say, conditions are found for binary operations o and ∇ defined on graphs and groups, respectively, which are sufficient to insure thatI g (X o Y)=I g (X)+I g (Y)−H XY , whereH XY is a certain conditional entropy defined relative to the orbits ofG(X o Y) andG(X) ∇G(Y).
---
paper_title: Identities and Inequalities for Tree Entropy

paper_content:

The notion of tree entropy was introduced by the author as a normalized limit of the number of spanning trees in finite graphs, but is defined on random infinite rooted graphs. We give some new expressions for tree entropy; one uses Fuglede-Kadison determinants, while another uses effective resistance. We use the latter to prove that tree entropy respects stochastic domination. We also prove that tree entropy is non-negative in the unweighted case, a special case of which establishes Lueck's Determinant Conjecture for Cayley-graph Laplacians. We use techniques from the theory of operators affiliated to von Neumann algebras.
---
paper_title: Generalized graph entropies

paper_content:

This article deals with generalized entropies for graphs. These entropies result from applying information measures to a graph using various schemes for defining probability distributions over the elements (e.g., vertices) of the graph. We introduce a new class of generalized measures, develop their properties, compute the measures for selected graphs, and briefly discuss potential applications to classification and clustering problems. © 2011 Wiley Periodicals, Inc. Complexity, 17,45–50, 2011 © 2011 Wiley Periodicals, Inc.
---
paper_title: A note on the information content of graphs

paper_content:

The role played by the group of a graph in determining sets of equivalent points is exposed and illustrated by a few simple examples.
---
paper_title: A history of graph entropy measures

paper_content:

This survey seeks to describe methods for measuring the entropy of graphs and to demonstrate the wide applicability of entropy measures. Setting the scene with a review of classical measures for determining the structural information content of graphs, we discuss graph entropy measures which play an important role in a variety of problem areas, including biology, chemistry, and sociology. In addition, we examine relationships between selected entropy measures, illustrating differences quantitatively with concrete examples.
---
paper_title: A Large Scale Analysis of Information-Theoretic Network Complexity Measures Using Chemical Structures

paper_content:

This paper aims to investigate information-theoretic network complexity measures which have already been intensely used in mathematical- and medicinal chemistry including drug design. Numerous such measures have been developed so far but many of them lack a meaningful interpretation, e.g., we want to examine which kind of structural information they detect. Therefore, our main contribution is to shed light on the relatedness between some selected information measures for graphs by performing a large scale analysis using chemical networks. Starting from several sets containing real and synthetic chemical structures represented by graphs, we study the relatedness between a classical (partition-based) complexity measure called the topological information content of a graph and some others inferred by a different paradigm leading to partition-independent measures. Moreover, we evaluate the uniqueness of network complexity measures numerically. Generally, a high uniqueness is an important and desirable property when designing novel topological descriptors having the potential to be applied to large chemical databases.
---
paper_title: Asymptotic enumeration of spanning trees

paper_content:

We give new general formulas for the asymptotics of the number of spanning trees of a large graph. A special case answers a question of McKay (1983) for regular graphs. The general answer involves a quantity for infinite graphs that we call "tree entropy", which we show is a logarithm of a normalized determinant of the graph Laplacian for infinite graphs. Tree entropy is also expressed using random walks. We relate tree entropy to the metric entropy of the uniform spanning forest process on quasi-transitive amenable graphs, extending a result of Burton and Pemantle (1993).
---
paper_title: Life, information theory, and topology

paper_content:

The information content of an organism determines to a large extent its ability to perform the basic vital functions: selection of food, breaking up of the food molecules into appropriate parts, selection of those parts, and their assimilation. The information content needed is very large and requires a sufficiently large complexity of the organism. The information content of an organism is largely determined by the information content of the constituent organic molecules. The information content of the latter is in its turn determined by the number of physically distinguishable atoms or radicals of which the molecule is composed. The different arrangements of atoms in a molecule are represented by the structural formula, which is basically a graph. It is shown that the topology of this graph also determines to a large extent the information content. Different points of a graph may be physically indistinguishable; in general, however, they are different in regard to their topological properties. A study of the relations between the topological properties of graphs and their information content is suggested, and several theorems are demonstrated. A relation between topology and living processes is thus found also on the molecular level.
---
paper_title: Novel topological descriptors for analyzing biological networks

paper_content:

Background ::: Topological descriptors, other graph measures, and in a broader sense, graph-theoretical methods, have been proven as powerful tools to perform biological network analysis. However, the majority of the developed descriptors and graph-theoretical methods does not have the ability to take vertex- and edge-labels into account, e.g., atom- and bond-types when considering molecular graphs. Indeed, this feature is important to characterize biological networks more meaningfully instead of only considering pure topological information.
---
paper_title: Inequalities for entropy-based measures of network information content

paper_content:

This paper presents a method for establishing relations between entropy-based measures applied to graphs. A special class of relations called implicit information inequalities or implicit entropy bounds is developed. A number of entropy-based measures of the structural information content of a graph have been developed over the past several decades, but little attention has been paid to relations among these measures. The research reported here aims to remedy this deficiency.
---
paper_title: A history of graph entropy measures

paper_content:

This survey seeks to describe methods for measuring the entropy of graphs and to demonstrate the wide applicability of entropy measures. Setting the scene with a review of classical measures for determining the structural information content of graphs, we discuss graph entropy measures which play an important role in a variety of problem areas, including biology, chemistry, and sociology. In addition, we examine relationships between selected entropy measures, illustrating differences quantitatively with concrete examples.
---
paper_title: Connections between Classical and Parametric Network Entropies

paper_content:

This paper explores relationships between classical and parametric measures of graph (or network) complexity. Classical measures are based on vertex decompositions induced by equivalence relations. Parametric measures, on the other hand, are constructed by using information functions to assign probabilities to the vertices. The inequalities established in this paper relating classical and parametric measures lay a foundation for systematic classification of entropy-based measures of graph complexity.
---
paper_title: Connections between Classical and Parametric Network Entropies

paper_content:

This paper explores relationships between classical and parametric measures of graph (or network) complexity. Classical measures are based on vertex decompositions induced by equivalence relations. Parametric measures, on the other hand, are constructed by using information functions to assign probabilities to the vertices. The inequalities established in this paper relating classical and parametric measures lay a foundation for systematic classification of entropy-based measures of graph complexity.
---
paper_title: Information processing in complex networks: Graph entropy and information functionals

paper_content:

This paper introduces a general framework for defining the entropy of a graph. Our definition is based on a local information graph and on information functionals derived from the topological structure of a given graph. More precisely, an information functional quantifies structural information of a graph based on a derived probability distribution. Such a probability distribution leads directly to an entropy of a graph. Then, the structural information content of a graph will be is interpreted and defined as the derived graph entropy. Another major contribution of this paper is the investigation of relationships between graph entropies. In addition to this, we provide numerical results demonstrating not only the feasibility of our method, which has polynomial time complexity, but also its usefulness with regard to practical applications aiming to an understanding of information processing in complex networks.
---
paper_title: Life, information theory, and topology

paper_content:

The information content of an organism determines to a large extent its ability to perform the basic vital functions: selection of food, breaking up of the food molecules into appropriate parts, selection of those parts, and their assimilation. The information content needed is very large and requires a sufficiently large complexity of the organism. The information content of an organism is largely determined by the information content of the constituent organic molecules. The information content of the latter is in its turn determined by the number of physically distinguishable atoms or radicals of which the molecule is composed. The different arrangements of atoms in a molecule are represented by the structural formula, which is basically a graph. It is shown that the topology of this graph also determines to a large extent the information content. Different points of a graph may be physically indistinguishable; in general, however, they are different in regard to their topological properties. A study of the relations between the topological properties of graphs and their information content is suggested, and several theorems are demonstrated. A relation between topology and living processes is thus found also on the molecular level.
---
paper_title: Information theoretic measures of UHG graphs with low computational complexity

paper_content:

We introduce a novel graph class we call universal hierarchical graphs (UHG) whose topology can be found numerously in problems representing, e.g., temporal, spacial or general process structures of systems. For this graph class we show, that we can naturally assign two probability distributions, for nodes and for edges, which lead us directly to the definition of the entropy and joint entropy and, hence, mutual information establishing an information theory for this graph class. Furthermore, we provide some results under which conditions these constraint probability distributions maximize the corresponding entropy. Also, we demonstrate that these entropic measures can be computed efficiently which is a prerequisite for every large scale practical application and show some numerical examples.
---
paper_title: Information theoretic measures of UHG graphs with low computational complexity

paper_content:

We introduce a novel graph class we call universal hierarchical graphs (UHG) whose topology can be found numerously in problems representing, e.g., temporal, spacial or general process structures of systems. For this graph class we show, that we can naturally assign two probability distributions, for nodes and for edges, which lead us directly to the definition of the entropy and joint entropy and, hence, mutual information establishing an information theory for this graph class. Furthermore, we provide some results under which conditions these constraint probability distributions maximize the corresponding entropy. Also, we demonstrate that these entropic measures can be computed efficiently which is a prerequisite for every large scale practical application and show some numerical examples.
---
paper_title: Mathematical concepts in organic chemistry

paper_content:

A Chemistry and Topology.- 1 Topological Aspects in Chemistry.- 1.1 Topology in Chemistry.- 1.2 Abstraction in Science and How Far One Can Go.- 2 Molecular Topology.- 2.1 What is Molecular Topology?.- 2.2 Geometry, Symmetry, Topology.- 2.3 Definition of Molecular Topology.- B Chemistry and Graph Theory.- 3 Chemical Graphs.- 4 Fundamentals of Graph Theory.- 4.1 The Definition of a Graph.- 4.1.1 Relations.- 4.1.2 The First Definition of a Graph.- 4.1.3 The Second Definition of a Graph.- 4.1.4 Vertices and Edges.- 4.1.5 Isomorphic Graphs and Graph Automorphisms.- 4.1.6 Special Graphs.- 4.2 Subgraphs.- 4.2.1 Sachs Graphs.- 4.2.2 Matchings.- 4.3 Graph Spectral Theory.- 4.3.1 The Adjacency Matrix.- 4.3.2 The Spectrum of a Graph.- 4.3.3 The Sachs Theorem.- 4.3.4 The ?-Polynomial.- 4.4 Graph Operations.- 5 Graph Theory and Molecular Orbitals.- 6 Special Molecular Graphs.- 6.1 Acyclic Molecules.- 6.1.1 Trees.- 6.1.2 The Path and the Star.- 6.1.3 The Characteristic Polynomial of Trees.- 6.1.4 Trees with Greatest Number of Matchings.- 6.1.5 The Spectrum of the Path.- 6.2 The Cycle.- 6.3 Alternant Molecules.- 6.3.1 Bipartite Graphs.- 6.3.2 The Pairing Theorem.- 6.3.3 Some Consequences of the Pairing Theorem.- 6.4 Benzenoid Molecules.- 6.4.1 Benzenoid Graphs.- 6.4.2 The Characteristic Polynomial of Benzenoid Graphs.- 6.5 Hydrocarbons and Molecules with Heteroatoms.- 6.5.1 On the Question of the Molecular Graph.- 6.5.2 The Characteristic Polynomial of Weighted Graphs.- 6.5.3 Some Regularities in the Electronic Structure of Heteroconjugated Molecules.- C Chemistry and Group Theory.- 7 Fundamentals of Group Theory.- 7.1 The Symmetry Group of an Equilateral Triangle.- 7.2 Order, Classes and Representations of a Group.- 7.3 Reducible and Irreducible Representations.- 7.4 Characters and Reduction of a Reducible Representation.- 7.5 Subgroups and Sidegroups - Products of Groups.- 7.6 Abelian Groups.- 7.7 Abstract Groups and Group Isomorphism.- 8 Symmetry Groups.- 8.1 Notation of Symmetry Elements and Representations.- 8.2 Some Symmetry Groups.- 8.2.1 Rotation Groups.- 8.2.2 Groups with More than One n-Fold Axis, n > 2.- 8.2.3 Groups of Collinear Molecules.- 8.3 Transformation Properties and Direct Products of Irreducible Representations.- 8.3.1 Transformation Properties.- 8.3.2 Rules Concerning the Direct Product of Irreducible Representations.- 8.4 Some Applications of Symmetry Groups.- 8.4.1 Electric Dipole Moment.- 8.4.2 Polarizability.- 8.4.3 Motions of Atomic Nuclei: Translations, Rotations and Vibrations.- 8.4.4 Transition Probabilities for the Absorption of Light.- 8.4.5 Transition Probabilities in Raman Spectra.- 8.4.6 Group Theory and Quantum Chemistry.- 8.4.7 Orbital and State Correlations.- 9 Automorphism Groups.- 9.1 Automorphism of a Graph.- 9.2 The Automorphism Group A(G1).- 9.3 Cycle Structure of Permutations.- 9.4 Isomorphism of Graphs and of Automorphism Groups 112..- 9.5 Notation of some Permutation Groups.- 9.6 Direct Product and Wreath Product.- 9.7 The Representation of Automorphism Groups as Group Products.- 10 Some Interrelations between Symmetry and Automorphism Groups.- 10.1 The Idea of Rigid Molecules.- 10.2 Local Symmetries.- 10.3 Non-Rigid Molecules.- 10.4 What Determines the Respective Orders of the Symmetry and the Automorphism Group of a Given Molecule?.- D Special Topics.- 11 Topological Indices.- 11.1 Indices Based on the Distance Matrix.- 11.1.1 The Wiener Number and Related Quantities.- 11.1.2 Applications of the Wiener Number.- 11.2 Hosoya's Topological Index.- 11.2.1 Definition and Chemical Applications of Hosoya's Index.- 11.2.2 Mathematical Properties of Hosoya's Index.- 11.2.3 Example: Hosoya's Index of the Path and the Cycle.- 11.2.4 Some Inequalities for Hosoya's Index.- 12 Thermodynamic Stability of Conjugated Molecules.- 12.1 Total ?-Electron Energy and Thermodynamic Stability of Conjugated Molecules.- 12.2 Total ?-Electron Energy and Molecular Topology.- 12.3 The Energy of a Graph.- 12.4 The Coulson Integral Formula.- 12.5 Some Further Applications of the Coulson Integral Formula.- 12.6 Bounds for Total ?-Electron Energy.- 12.7 More on the McClelland Formula.- 12.8 Conclusion: Factors Determining the Total ?-Electron Energy.- 12.9 Use of Total ?-Electron Energy in Chemistry.- 13 Topological Effect on Molecular Orbitals.- 13.1 Topologically Related Isomers.- 13.2 Interlacing Rule.- 13.3 PE Spectra of Topomers.- 13.4 TEMO and a-Electron Systems.- 13.5 TEMO and Symmetry.- Appendices.- Appendix 1 Matrices.- Appendix 2 Determinants.- Appendix 3 Eigenvalues and Eigenvectors.- Appendix 4 Polynomials.- Appendix 5 Characters of Irreducible Representations of Symmetry Groups.- Appendix 6 The Symbols Used.- Literature.- References.
---
paper_title: Entropy Bounds for Hierarchical Molecular Networks

paper_content:

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.
---
paper_title: Entropy Bounds for Hierarchical Molecular Networks

paper_content:

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.
---
paper_title: Information theoretic measures of UHG graphs with low computational complexity

paper_content:

We introduce a novel graph class we call universal hierarchical graphs (UHG) whose topology can be found numerously in problems representing, e.g., temporal, spacial or general process structures of systems. For this graph class we show, that we can naturally assign two probability distributions, for nodes and for edges, which lead us directly to the definition of the entropy and joint entropy and, hence, mutual information establishing an information theory for this graph class. Furthermore, we provide some results under which conditions these constraint probability distributions maximize the corresponding entropy. Also, we demonstrate that these entropic measures can be computed efficiently which is a prerequisite for every large scale practical application and show some numerical examples.
---
paper_title: Information processing in complex networks: Graph entropy and information functionals

paper_content:

This paper introduces a general framework for defining the entropy of a graph. Our definition is based on a local information graph and on information functionals derived from the topological structure of a given graph. More precisely, an information functional quantifies structural information of a graph based on a derived probability distribution. Such a probability distribution leads directly to an entropy of a graph. Then, the structural information content of a graph will be is interpreted and defined as the derived graph entropy. Another major contribution of this paper is the investigation of relationships between graph entropies. In addition to this, we provide numerical results demonstrating not only the feasibility of our method, which has polynomial time complexity, but also its usefulness with regard to practical applications aiming to an understanding of information processing in complex networks.
---
paper_title: Recent Developments in Quantitative Graph Theory: Information Inequalities for Networks

paper_content:

In this article, we tackle a challenging problem in quantitative graph theory. We establish relations between graph entropy measures representing the structural information content of networks. In particular, we prove formal relations between quantitative network measures based on Shannon's entropy to study the relatedness of those measures. In order to establish such information inequalities for graphs, we focus on graph entropy measures based on information functionals. To prove such relations, we use known graph classes whose instances have been proven useful in various scientific areas. Our results extend the foregoing work on information inequalities for graphs.
---
paper_title: Degree Powers in Graphs with Forbidden Subgraphs

paper_content:

Yuster and Caro initiated the study of the sum of powers of the degrees of graphs with forbidden subgraphs. We settle two of their conjectures.
---
paper_title: Entropy bounds for dendrimers

paper_content:

Abstract Many graph invariants have been used for the construction of entropy-based measures to characterize the structure of complex networks. When considering Shannon entropy-based graph measures, there has been very little work to find their extremal values. A reason for this might be the fact that Shannon’s entropy represents a multivariate function and all probability values are not equal to zero when considering graph entropies. Dehmer and Kraus proved some extremal results for graph entropies which are based on information functionals and express some conjectures generated by numerical simulations to find extremal values of graph entropies. Dehmer and Kraus discussed the extremal values of entropies for dendrimers. In this paper, we continue to study the extremal values of graph entropy for dendrimers, which has most interesting applications in molecular structure networks, and also in the pharmaceutical and biomedical area. Among all dendrimers with n vertices, we obtain the extremal values of graph entropy based on different well-known information functionals. Numerical experiments verifies our results.
---
paper_title: Chemical graph theory

paper_content:

Abstract The concept of Ulam sub-graphs is discussed and it is shown that such sub-graphs may be used without difficulty for establishing the characteristic polynomials of general (vertex- and edge-weighted) graphs. The use of Ulam sub-graphs in obtaining characteristic polynomials is compared with the construction of such polynomials via the Heilbronner formula, and it is found that the latter approach is simpler, when it is applicable.
---
paper_title: Triangles in a complete chromatic graph

paper_content:

Suppose that in a complete graph on N points, each edge is given arbitrarily either the color red or the color blue, but the total number of blue edges is fixed at T . We find the minimum number of monochromatic triangles in the graph as a function of N and T . The maximum number of monochromatic triangles presents a more difficult problem. Here we propose a reasonable conjecture supported by examples.
---
paper_title: On Sets of Acquaintances and Strangers at any Party

paper_content:

It is our purpose to prove a more general result when the number 6 is replaced by any positive integer N (see Theorem 1 below). It is convenient to transform the problem into an equivalent problem concerning points and lines. The N persons involved are replaced by points Ak, k =1, * *, N, no three of which are collinear and if two persons are acquainted a line is drawn joining the corresponding pair of points. If the two persons are strangers then no line is drawn. Thus each collection of N people gives rise to a corresponding configuration of N points and L lines where 0? L < N(N1)/2. If three people are mutually acquainted the corresponding figure is a triangle which we will call a full triangle. If three people are pairwise strangers the corresponding figure consists of three points with no lines joining any pair. We call such a figure an empty triangle. Any set of three points not the vertices of a full triangle, nor an empty triangle, will be called a partial triangle. Notice that a given point may simultaneously be a vertex of several triangles from each category. With these definitions we have
---
paper_title: Extremality of degree-based graph entropies

paper_content:

Abstract Many graph invariants have been used for the construction of entropy-based measures to characterize the structure of complex networks. Based on Shannon’s entropy, we study graph entropies which are based on vertex degrees by using so-called information functionals. When considering Shannon entropy-based graph measures, there has been very little work to find their extremal values. The main contribution of this paper is to prove some extremal values for the underlying graph entropy of certain families of graphs and to find the connection between the graph entropy and the sum of degree powers. Further, conjectures to determine extremal values of graph entropies are given.
---
paper_title: A Note on Distance-based Graph Entropies

paper_content:

A variety of problems in, e.g., discrete mathematics, computer science, information theory, statistics, chemistry, biology, etc., deal with inferring and characterizing relational structures by using graph measures. In this sense, it has been proven that information-theoretic quantities representing graph entropies possess useful properties such as a meaningful structural interpretation and uniqueness. As classical work, many distance-based graph entropies, e.g., the ones due to Bonchev et al. and related quantities have been proposed and studied. Our contribution is to explore graph entropies that are based on a novel information functional, which is the number of vertices with distance \(k\) to a given vertex. In particular, we investigate some properties thereof leading to a better understanding of this new information-theoretic quantity.
---
paper_title: Degree-based entropies of networks revisited

paper_content:

Studies on the information content of graphs and networks have been initiated in the late fifties based on the seminal work due to Shannon and Rashevsky. Various graph parameters have been used for the construction of entropy-based measures to characterize the structure of complex networks. Based on Shannon's entropy, in Cao et?al. (Extremality of degree-based graph entropies, Inform. Sci. 278 (2014) 22-33), we studied graph entropies which are based on vertex degrees by using so-called information functionals. As a matter of fact, there has been very little work to find their extremal values when considered Shannon entropy-based graph measures. We pursue with this line of research by proving further extremal properties of the degree-based graph entropies.
---
paper_title: A Note on Distance-based Graph Entropies

paper_content:

A variety of problems in, e.g., discrete mathematics, computer science, information theory, statistics, chemistry, biology, etc., deal with inferring and characterizing relational structures by using graph measures. In this sense, it has been proven that information-theoretic quantities representing graph entropies possess useful properties such as a meaningful structural interpretation and uniqueness. As classical work, many distance-based graph entropies, e.g., the ones due to Bonchev et al. and related quantities have been proposed and studied. Our contribution is to explore graph entropies that are based on a novel information functional, which is the number of vertices with distance \(k\) to a given vertex. In particular, we investigate some properties thereof leading to a better understanding of this new information-theoretic quantity.
---
paper_title: Entropy bounds for dendrimers

paper_content:

Abstract Many graph invariants have been used for the construction of entropy-based measures to characterize the structure of complex networks. When considering Shannon entropy-based graph measures, there has been very little work to find their extremal values. A reason for this might be the fact that Shannon’s entropy represents a multivariate function and all probability values are not equal to zero when considering graph entropies. Dehmer and Kraus proved some extremal results for graph entropies which are based on information functionals and express some conjectures generated by numerical simulations to find extremal values of graph entropies. Dehmer and Kraus discussed the extremal values of entropies for dendrimers. In this paper, we continue to study the extremal values of graph entropy for dendrimers, which has most interesting applications in molecular structure networks, and also in the pharmaceutical and biomedical area. Among all dendrimers with n vertices, we obtain the extremal values of graph entropy based on different well-known information functionals. Numerical experiments verifies our results.
---
paper_title: INFORMATION-THEORETIC CONCEPTS FOR THE ANALYSIS OF COMPLEX NETWORKS

paper_content:

In this article, we present information-theoretic concepts for analyzing complex networks. We see that the application of information-theoretic concepts to networks leads to interesting tasks and gives a possibility for understanding information processing in networks. The main contribution of this article is a method for determining the structural information content of graphs that is based on a tree decomposition. It turns out that the computational complexity of the underlying algorithm is polynomial. Finally, we present some numerical results to study the influence of the used methods on the resulting information contents.
---
paper_title: A Large Scale Analysis of Information-Theoretic Network Complexity Measures Using Chemical Structures

paper_content:

This paper aims to investigate information-theoretic network complexity measures which have already been intensely used in mathematical- and medicinal chemistry including drug design. Numerous such measures have been developed so far but many of them lack a meaningful interpretation, e.g., we want to examine which kind of structural information they detect. Therefore, our main contribution is to shed light on the relatedness between some selected information measures for graphs by performing a large scale analysis using chemical networks. Starting from several sets containing real and synthetic chemical structures represented by graphs, we study the relatedness between a classical (partition-based) complexity measure called the topological information content of a graph and some others inferred by a different paradigm leading to partition-independent measures. Moreover, we evaluate the uniqueness of network complexity measures numerically. Generally, a high uniqueness is an important and desirable property when designing novel topological descriptors having the potential to be applied to large chemical databases.
---
paper_title: Life, information theory, and topology

paper_content:

The information content of an organism determines to a large extent its ability to perform the basic vital functions: selection of food, breaking up of the food molecules into appropriate parts, selection of those parts, and their assimilation. The information content needed is very large and requires a sufficiently large complexity of the organism. The information content of an organism is largely determined by the information content of the constituent organic molecules. The information content of the latter is in its turn determined by the number of physically distinguishable atoms or radicals of which the molecule is composed. The different arrangements of atoms in a molecule are represented by the structural formula, which is basically a graph. It is shown that the topology of this graph also determines to a large extent the information content. Different points of a graph may be physically indistinguishable; in general, however, they are different in regard to their topological properties. A study of the relations between the topological properties of graphs and their information content is suggested, and several theorems are demonstrated. A relation between topology and living processes is thus found also on the molecular level.
---
paper_title: On Extremal Properties of Graph Entropies

paper_content:

We study extremal properties of graph entropies based on so-called information functionals. We obtain som ee xtre mality results for the resulting graph entropies which rely on the well-known Shannon entropy. Also by applying these results, we infer some entropy bounds for certain graph classes. Further, conjectures to determine extremal values (maximum and minimum values) of the graph entropies graphs based on numerical results are given.
---
paper_title: INFORMATION-THEORETIC CONCEPTS FOR THE ANALYSIS OF COMPLEX NETWORKS

paper_content:

In this article, we present information-theoretic concepts for analyzing complex networks. We see that the application of information-theoretic concepts to networks leads to interesting tasks and gives a possibility for understanding information processing in networks. The main contribution of this article is a method for determining the structural information content of graphs that is based on a tree decomposition. It turns out that the computational complexity of the underlying algorithm is polynomial. Finally, we present some numerical results to study the influence of the used methods on the resulting information contents.
---
paper_title: On Sphere-Regular Graphs and the Extremality of Information-Theoretic Network Measures

paper_content:

The entropy of a chemical graph can be interpreted as its structural information content. In this paper, we study extremality properties of graph entropies based on so-called information functionals. Based on dierent information functionals using metrical properties of graphs, we tackle the problem of determining classes of graphs which take maximal and minimal values. Also, we dene a novel class of graphs which maximizes the structural information content based on the functional using i-spheres. Under certain assumptions, this class fully determines the class of maximal graphs based on their structural information content. For minimal graphs and other functionals, an analytic approach to the question failed. Hence we performed simulations and provide several conjectures on classes of extremal graphs by using our numerical results.
---
paper_title: Novel inequalities for generalized graph entropies - Graph energies and topological indices

paper_content:

The entropy of a graph is an information-theoretic quantity for measuring the complexity of a graph. After Shannon introduced the entropy to information and communication, many generalizations of the entropy measure have been proposed, such as Renyi entropy and Daroczy entropy. In this article, we prove accurate connections (inequalities) between generalized graph entropies, graph energies, and topological indices. Additionally, we obtain some extremal properties of nine generalized graph entropies by employing graph energies and topological indices.
---
paper_title: Connections between generalized graph entropies and graph energy

paper_content:

Dehmer and Mowshowitz introduced a class of generalized graph entropies using known information-theoretic measures. These measures rely on assigning a probability distribution to a graph. In this article, we prove some extremal properties of such generalized graph entropies by using the graph energy and the spectral moments. Moreover, we study the relationships between the generalized graph entropies and compute the values of the generalized graph entropies for special graph classes. © 2014 Wiley Periodicals, Inc. Complexity 21: 35-41, 2015
---
paper_title: Entropy bounds for dendrimers

paper_content:

Abstract Many graph invariants have been used for the construction of entropy-based measures to characterize the structure of complex networks. When considering Shannon entropy-based graph measures, there has been very little work to find their extremal values. A reason for this might be the fact that Shannon’s entropy represents a multivariate function and all probability values are not equal to zero when considering graph entropies. Dehmer and Kraus proved some extremal results for graph entropies which are based on information functionals and express some conjectures generated by numerical simulations to find extremal values of graph entropies. Dehmer and Kraus discussed the extremal values of entropies for dendrimers. In this paper, we continue to study the extremal values of graph entropy for dendrimers, which has most interesting applications in molecular structure networks, and also in the pharmaceutical and biomedical area. Among all dendrimers with n vertices, we obtain the extremal values of graph entropy based on different well-known information functionals. Numerical experiments verifies our results.
---
paper_title: Complexity of networks I: The set-complexity of binary graphs

paper_content:

The balance between symmetry and randomness as a property of networks can be viewed as a kind of “complexity.” We use here our previously defined “set complexity” measure (Galas et al., IEEE Trans Inf Theory 2010, 56), which was used to approach the problem of defining biological information, in the mathematical analysis of networks. This information theoretic measure is used to explore the complexity of binary, undirected graphs. The complexities, Ψ, of some specific classes of graphs can be calculated in closed form. Some simple graphs have a complexity value of zero, but graphs with significant values of Ψ are rare. We find that the most complex of the simple graphs are the complete bipartite graphs (CBGs). In this simple case, the complexity, Ψ, is a strong function of the size of the two node sets in these graphs. We find the maximum Ψ binary graphs as well. These graphs are distinct from, but similar to CBGs. Finally, we explore directed and stochastic processes for growing graphs (hill-climbing and random duplication, respectively) and find that node duplication and partial node duplication conserve interesting graph properties. Partial duplication can grow extremely complex graphs, while full node duplication cannot do so. By examining the eigenvalue spectrum of the graph Laplacian we characterize the symmetry of the graphs and demonstrate that, in general, breaking specific symmetries of the binary graphs increases the set-based complexity, Ψ. The implications of these results for more complex, multiparameter graphs, and for physical and biological networks and the processes of network evolution are discussed. © 2011 Wiley Periodicals, Inc. Complexity, 17,51–64, 2011 © 2011 Wiley Periodicals, Inc.
---
paper_title: Encoding structural information uniquely with polynomial-based descriptors by employing the Randić matrix

paper_content:

In this paper we define novel graph measures based on the zeros of the characteristic polynomial by using the Randic matrix. We compute the novel graph descriptors on exhaustively generated graphs and trees and demonstrate that the measures encode their structural information uniquely. These results are compared with the same graph measures but based on the eigenvalues of the classical characteristic polynomial of a graph. Finally we interpret our findings that are evidenced by numerical results.
---
paper_title: Generalized graph entropies

paper_content:

This article deals with generalized entropies for graphs. These entropies result from applying information measures to a graph using various schemes for defining probability distributions over the elements (e.g., vertices) of the graph. We introduce a new class of generalized measures, develop their properties, compute the measures for selected graphs, and briefly discuss potential applications to classification and clustering problems. © 2011 Wiley Periodicals, Inc. Complexity, 17,45–50, 2011 © 2011 Wiley Periodicals, Inc.
---
paper_title: On Graph Entropy Measures for Knowledge Discovery from Publication Network Data

paper_content:

Many research problems are extremely complex, making interdisciplinary knowledge a necessity; consequently cooperative work in mixed teams is a common and increasing research procedure. In this paper, we evaluated information-theoretic network measures on publication networks. For the experiments described in this paper we used the network of excellence from the RWTH Aachen University, described in [1]. Those measures can be understood as graph complexity measures, which evaluate the structural complexity based on the corresponding concept. We see that it is challenging to generalize such results towards different measures as every measure captures structural information differently and, hence, leads to a different entropy value. This calls for exploring the structural interpretation of a graph measure [2] which has been a challenging problem.
---
paper_title: A history of graph entropy measures

paper_content:

This survey seeks to describe methods for measuring the entropy of graphs and to demonstrate the wide applicability of entropy measures. Setting the scene with a review of classical measures for determining the structural information content of graphs, we discuss graph entropy measures which play an important role in a variety of problem areas, including biology, chemistry, and sociology. In addition, we examine relationships between selected entropy measures, illustrating differences quantitatively with concrete examples.
---
paper_title: A note on the von Neumann entropy of random graphs

paper_content:

Abstract In this note, we consider the von Neumann entropy of a density matrix obtained by normalizing the combinatorial Laplacian of a graph by its degree sum. We prove that the von Neumann entropy of the typical Erdos–Renyi random graph saturates its upper bound. Since connected regular graphs saturate this bound as well, our result highlights a connection between randomness and regularity. A general interpretation of the von Neumann entropy of a graph is an open problem.
---
paper_title: Complexity of networks II: The set complexity of edge-colored graphs

paper_content:

We previously introduced the concept of “set-complexity,” based on a context-dependent measure of information, and used this concept to describe the complexity of gene interaction networks. In a previous paper of this series we analyzed the set-complexity of binary graphs. Here, we extend this analysis to graphs with multicolored edges that more closely match biological structures like the gene interaction networks. All highly complex graphs by this measure exhibit a modular structure. A principal result of this work is that for the most complex graphs of a given size the number of edge colors is equal to the number of “modules” of the graph. Complete multipartite graphs (CMGs) are defined and analyzed. The relation between complexity and structure of these graphs is examined in detail. We establish that the mutual information between any two nodes in a CMG can be fully expressed in terms of entropy, and present an explicit expression for the set complexity of CMGs (Theorem 3). An algorithm for generating highly complex graphs from CMGs is described. We establish several theorems relating these concepts and connecting complex graphs with a variety of practical network properties. In exploring the relation between symmetry and complexity we use the idea of a similarity matrix and its spectrum for highly complex graphs. © 2012 Wiley Periodicals, Inc. Complexity, 2012 © 2012 Wiley Periodicals, Inc.
---
paper_title: Structural information content of networks: Graph entropy based on local vertex functionals

paper_content:

In this paper we define the structural information content of graphs as their corresponding graph entropy. This definition is based on local vertex functionals obtained by calculating j-spheres via the algorithm of Dijkstra. We prove that the graph entropy and, hence, the local vertex functionals can be computed with polynomial time complexity enabling the application of our measure for large graphs. In this paper we present numerical results for the graph entropy of chemical graphs and discuss resulting properties.
---
paper_title: A Large Scale Analysis of Information-Theoretic Network Complexity Measures Using Chemical Structures

paper_content:

This paper aims to investigate information-theoretic network complexity measures which have already been intensely used in mathematical- and medicinal chemistry including drug design. Numerous such measures have been developed so far but many of them lack a meaningful interpretation, e.g., we want to examine which kind of structural information they detect. Therefore, our main contribution is to shed light on the relatedness between some selected information measures for graphs by performing a large scale analysis using chemical networks. Starting from several sets containing real and synthetic chemical structures represented by graphs, we study the relatedness between a classical (partition-based) complexity measure called the topological information content of a graph and some others inferred by a different paradigm leading to partition-independent measures. Moreover, we evaluate the uniqueness of network complexity measures numerically. Generally, a high uniqueness is an important and desirable property when designing novel topological descriptors having the potential to be applied to large chemical databases.
---
paper_title: On Entropy-based Molecular Descriptors : Statistical Analysis of Real and Synthetic Chemical Structures

paper_content:

This paper presents an analysis of entropy-based molecular descriptors. Specifically, we use real chemical structures, as well as synthetic isomeric structures, and investigate properties of and among descriptors with respect to the used data set by a statistical analysis. Our numerical results provide evidence that synthetic chemical structures are notably different to real chemical structures and, hence, should not be used to investigate molecular descriptors. Instead, an analysis based on real chemical structures is favorable. Further, we find strong hints that molecular descriptors can be partitioned into distinct classes capturing complementary information.
---
paper_title: Entropy Bounds for Hierarchical Molecular Networks

paper_content:

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.
---
paper_title: Novel topological descriptors for analyzing biological networks

paper_content:

Background ::: Topological descriptors, other graph measures, and in a broader sense, graph-theoretical methods, have been proven as powerful tools to perform biological network analysis. However, the majority of the developed descriptors and graph-theoretical methods does not have the ability to take vertex- and edge-labels into account, e.g., atom- and bond-types when considering molecular graphs. Indeed, this feature is important to characterize biological networks more meaningfully instead of only considering pure topological information.
---
paper_title: Information processing in complex networks: Graph entropy and information functionals

paper_content:

This paper introduces a general framework for defining the entropy of a graph. Our definition is based on a local information graph and on information functionals derived from the topological structure of a given graph. More precisely, an information functional quantifies structural information of a graph based on a derived probability distribution. Such a probability distribution leads directly to an entropy of a graph. Then, the structural information content of a graph will be is interpreted and defined as the derived graph entropy. Another major contribution of this paper is the investigation of relationships between graph entropies. In addition to this, we provide numerical results demonstrating not only the feasibility of our method, which has polynomial time complexity, but also its usefulness with regard to practical applications aiming to an understanding of information processing in complex networks.
---
paper_title: Inequalities for entropy-based measures of network information content

paper_content:

This paper presents a method for establishing relations between entropy-based measures applied to graphs. A special class of relations called implicit information inequalities or implicit entropy bounds is developed. A number of entropy-based measures of the structural information content of a graph have been developed over the past several decades, but little attention has been paid to relations among these measures. The research reported here aims to remedy this deficiency.
---
paper_title: Uniquely Discriminating Molecular Structures Using Novel Eigenvalue-Based Descriptors

paper_content:

In this article, we explore novel spectra-based descriptors to discriminate molecular graphs. As known, classical structure descriptors based on the eigenvalues of the underlying adjacency matrix are often insufficient since there exist a large number of isospectral graphs. Briefly recall that the spectrum is the set of eigenvalues of the characteristic polynomial. To tackle the problem, we propose five families of novel descriptors based on the eigenvalues of certain molecular matrices representing chemical structures. Note that in this paper, we only consider the underlying skeleton of a molecular graph. Because it is crucial to study the discrimination power (often called degeneracy) by not merely using synthetic (isomeric) structures, we apply the novel measures to both real and synthetic molecular graphs. Also, we use ten different types of molecular matrices to calculate the novel descriptors and determine correlations between them. It turns out that the novel descriptors possess high discrimination power when being applied to appropriate molecular matrices. Evidently, the study also reveals that special kinds of matrices capture structural information of the molecular graphs more meaningfully than others, particularly the adjacency matrix which turned out often to be insufficient to develop molecular descriptors.
---
paper_title: Exploring Statistical and Population Aspects of Network Complexity

paper_content:

The characterization and the definition of the complexity of objects is an important but very difficult problem that attracted much interest in many different fields. In this paper we introduce a new measure, called network diversity score (NDS), which allows us to quantify structural properties of networks. We demonstrate numerically that our diversity score is capable of distinguishing ordered, random and complex networks from each other and, hence, allowing us to categorize networks with respect to their structural complexity. We study 16 additional network complexity measures and find that none of these measures has similar good categorization capabilities. In contrast to many other measures suggested so far aiming for a characterization of the structural complexity of networks, our score is different for a variety of reasons. First, our score is multiplicatively composed of four individual scores, each assessing different structural properties of a network. That means our composite score reflects the structural diversity of a network. Second, our score is defined for a population of networks instead of individual networks. We will show that this removes an unwanted ambiguity, inherently present in measures that are based on single networks. In order to apply our measure practically, we provide a statistical estimator for the diversity score, which is based on a finite number of samples.
---
paper_title: Information theoretic measures of UHG graphs with low computational complexity

paper_content:

We introduce a novel graph class we call universal hierarchical graphs (UHG) whose topology can be found numerously in problems representing, e.g., temporal, spacial or general process structures of systems. For this graph class we show, that we can naturally assign two probability distributions, for nodes and for edges, which lead us directly to the definition of the entropy and joint entropy and, hence, mutual information establishing an information theory for this graph class. Furthermore, we provide some results under which conditions these constraint probability distributions maximize the corresponding entropy. Also, we demonstrate that these entropic measures can be computed efficiently which is a prerequisite for every large scale practical application and show some numerical examples.
---

Title: A Survey of Recent Results in (Generalized) Graph Entropies

Section 1: Introduction
Description 1: Introduce the concept of graph entropy and its applications in various fields. Provide a historical overview and different approaches to measure graph entropy.

Section 2: Inequalities and extremal properties on (generalized) graph entropies
Description 2: Discuss the identity and inequality relationships between distinct graph entropies and study the extremal properties of graph entropies.

Section 3: Inequalities for classical graph entropies and parametric measures
Description 3: Present the bounds for special graph classes and study interrelations among classical and parametric graph entropy measures.

Section 4: Graph entropy inequalities with information functions f_V, f_P, and f_C
Description 4: Define information functions based on metrical properties and vertex centrality measures and derive related graph entropy measures.

Section 5: Information theoretic measures of UHG graphs
Description 5: Define and study the vertex and edge entropy of Universal Hierarchical Graphs (UHG) and their extremal properties.

Section 6: Bounds for the entropies of rooted trees and generalized trees
Description 6: Introduce and derive bounds for entropies of hierarchical and generalized trees, considering special classes of rooted trees.

Section 7: Information inequalities for I_f(G) based on different information functions
Description 7: Discuss closed-form expressions, bounds, and information inequalities of graph entropies based on specific information functions.

Section 8: Extremal properties of degree-based and distance-based graph entropies
Description 8: State the extremal properties of graph entropies based on degree powers and number of vertices at specific distances.

Section 9: Extremality of I_f_lambda(G), I_f_2(G), I_f_3(G) and entropy bounds for dendrimers
Description 9: Define specific graph entropies I_f_lambda(G), I_f_2(G), and I_f_3(G), and present their extremal properties and bounds for dendrimers.

Section 10: Sphere-regular graphs and the extremality entropies I_f_2(G) and I_f_sigma(G)
Description 10: Define sphere-regular graphs and study the properties and maximal graphs for sphere-function-based entropies.

Section 11: Information inequalities for generalized graph entropies
Description 11: Establish formal relationships between Shannon and Rényi entropies, and between classical and partition-independent entropy measures. Present bounds and inequalities for special graph classes and information functions.

Section 12: Relationships between graph structures, graph energies, topological indices and generalized graph entropies
Description 12: Introduce generalized graph entropies based on graph matrices, and explore their relationships with graph energies, spectral moments, and topological indices.

Section 13: Summary and conclusion
Description 13: Summarize the survey, highlighting the extremal properties, applications, and relationships among different (generalized) graph entropy measures. Mention open problems and conjectures for further research.