|Home | About | Journals | Submit | Contact Us | Français|
Conceived and designed the experiments: MD LAJM AG. Performed the experiments: MD LAJM AG. Analyzed the data: MD LAJM AG. Contributed reagents/materials/analysis tools: MD LAJM AG. Wrote the paper: MD LAJM AG.
In this paper, we introduce a novel graph polynomial called the ‘information polynomial’ of a graph. This graph polynomial can be derived by using a probability distribution of the vertex set. By using the zeros of the obtained polynomial, we additionally define some novel spectral descriptors. Compared with those based on computing the ordinary characteristic polynomial of a graph, we perform a numerical study using real chemical databases. We obtain that the novel descriptors do have a high discrimination power.
The study of specific structural properties of graphs by using algebraic polynomial representations has been a well-known and fruitful concept for several decades –. In particular, graph polynomials have been either used for describing combinatorial graph invariants or to characterize chemical structures by using the coefficients or the zeros of a graph polynomial , , . As outlined by Gutman  and Ivanciuc et al. , various topics in mathematical chemistry like Hückel-molecular orbital theory, the theory of aromaticity, and the development of topological indices (e.g., Hosoya index etc.) rely on graph polynomials. Indeed, a very important graph polynomial is the characteristic polynomial of a graph which has been intensely studied by Cvetkovic  when exploring structural properties of a graph related to its eigenvalues. Several methods to compute the characteristic polynomial explicitly were also developed . Afterwards, various other graph polynomials , ,  such as the Laplacian polynomial, Matching polynomial, Mühlheim polynomial, Distance polynomial and the Wiener Polynomial etc. have been developed for investigating multifaceted aspects of chemical structures.
In this paper, we use the zeros of a novel graph polynomial to derive molecular descriptors. Before outlining the contribution of our paper, we briefly sketch some approaches surveyed by Randić et al.  who gave a thorough overview on existing eigenvalue-based descriptors and various applications thereof. An early starting point in this area was initiated by Lovász and Pelikán : They employed the leading positive eigenvalue of the characteristic polynomial as a measure for detecting branching of trees. More advanced concepts to quantify branching of chemical graphs and DNA structures relying on graph-eigenvalues can be also found in Randić's survey . Particularly, the largest and second largest eigenvalues of other graph-theoretical matrices , the sum of their positive eigenvalues, the multiplicity of the zero eigenvalue and other spectral indices were also studied ,  to check their ability for serving as molecular descriptors. Importantly, numerical results were reported  when applying such descriptors to explore correlations of several physico-chemical properties of chemicals. As a final remark, other eigenvalue-based measures and graph polynomials have been used in various scientific disciplines as well. For instance, graph spectra were employed to derive indices for measuring the structural similarity of networks . In social network analysis and biology, such indices turned out to be useful for defining centrality measures , . Estrada  derived an eigenvalue-based measure (called the Estrada index) for examining the degree of folding of proteins. More generally, polynomial-based approaches have also been employed to study structural aspects of networks, e.g., see , .
The main contribution of our paper is as follows: Firstly, we define a novel graph polynomial which we call the information polynomial of a graph . In our sense, we infer this polynomial by using a probability distribution of length for deriving a graph-theoretical matrix (see Equation (8) in the section ‘Methods’). Secondly, we use the zeros of this polynomial to derive some novel molecular descriptors. Then, we investigate their uniqueness and compare our results with other descriptors. An illustration of our workflow is shown in Figure 1.
In this section, we define a novel graph polynomial as well as some spectral molecular descriptors by combining information-theoretic and algebraic methods , . To provide measures (descriptors) for quantifying structural information of a graph meaningfully, we develop the notation of the ‘information polynomial’ of a graph. Then, the main idea is to derive a polynomial representation whose coefficients or other characteristics, e.g., its zeros capture structural information of the underlying graph. We want to remark that the expression ‘information polynomial’ has already been used ,  in another context by determining the relative information defined as the combinatorial entropy of an oriented graph .
In particular, it was shown  that can be expressed by
The kind of information polynomial we want to introduce here is notably different from the just mentioned one. The reason why we keep this notation is that the underlying probability distribution as well as the resulting polynomial captures structural information of a graph. In our case, we use an information functional – leading to vertex probability values that can be used to define a graph-theoretical matrix.
We now start with a probability distribution
associated to a graph that has already been used to obtain information measures for determining the structural information content of a graph –. The general procedure is as follows: One assigns a probability value to each vertex of a given graph by using a certain information functional – where represents a function that maps vertices, or more generally graph elements (when using other invariants), to the non-negative reals. Then, by using Shannon's entropy , the structural information content will be defined and interpreted as the entropy of the underlying graph topology , .
Let's introduce this framework formally. The quantities serving as vertex probabilities are defined by 
Further, a family of graph entropy measures could be obtained by 
Starting from a graph and the probability distribution (see Equation (5)), we now define a matrix for computing an algebraic polynomial which we also call the information polynomial of . In contrast to the briefly sketched polynomial , , our main goal is to investigate the information polynomial (see Definition (2)) for deriving molecular descriptors from the underlying zero distribution. Further, we remark that our polynomial (see Equation (2)) does not serve as an input for determining a kind of information value. Instead, the structural information of a graph will be captured by the polynomial.
Let be a graph and let be the probability distribution assigned to vertex set of . We define the matrix
We set and
We define . is called the information polynomial of .
We remark that starting from Equation (8), (9), we see immediately that is symmetric, i.e., . Then, it is clear that all eigenvalues of are real . Also, we point out that to comprise the connection between and , we use a function (see Equation (9)) depending on the shortest distance between the corresponding vertices. To calculate for some simple graphs exemplarily, we consider Figure 2 and set
and and for determining the probability distribution . is the diameter of . We yield
and the corresponding sets of zeros are
In particular, we always get
The positive eigenvalue is .
In the following, we define some novel descriptors derived from the just introduced polynomial. The idea is to use the underlying zero distribution of .
Let be the information polynomial of and let be its real zeros.
The aim of this section is to evaluate the just defined descriptors (see previous section) in terms of their uniqueness (degeneracy) , . This property of a molecular descriptor relates to the ability to distinguish graphs as uniquely as possible by calculating the underlying graph measure. In general, a descriptor is called degenerated if there are at least two non-isomorphic graphs possessing the same value. For instance, concrete studies ,  to explore this problem by using isomeric and lattice structures were performed. Particularly, Bonchev et al.  investigated the degeneracy of information-theoretic indices relying on Shannon's entropy. Further, Todeschini et al.  evaluated several known non-information-theoretic and information-theoretic topological indices based on a large set of real chemical compounds. Another important problem is to quantify the degree of degeneracy of a given index. For this, a sensitivity measure as well as an information-theoretic measure have been developed by Konstantinova ,  and Todeschini et al. , respectively.
We implemented the novel descriptors and performed all involved calculations by using the programming language R  and the freely available library ‘graph’. In order to generate the underlying graph structures representing chemical compounds, we used Molfile format . We remark that the graphs originating from AG 3982 were originally available in Smiles format. Thus, we converted them to Molfile format (SDF) using a Python procedure. The graphs from MS 2265 were originally available as Molfiles. In both cases, a R procedure was developed to create the adjacency matrices as well as the matrices for calculating the novel descriptors from the available Molfiles. To determine their degree of degeneracy (sensitivity measure) in the next section, we use Equation (10) and exponentially decreasing parameters chosen as
We now interpret the results we have obtained from calculating the sensitivity index 
of a descriptor as follows. Here, is the cardinality of a given set of graphs and denotes the number of graphs which can not be distinguished by an index . In Table 1, we see the results when using the novel descriptors based on the underlying information polynomial . In Table 2, we summarize the results when using the same descriptors (these are ) based on the ordinary characteristic polynomial is the adjacency matrix of . For both polynomials and , we observe that the sums of the square roots of the moduli of their real zeros ( and ) have a high discrimination power. But by evaluating the characteristic polynomial instead of the information polynomial, one can see that the sensitivity values are a little less. Further, , and also do have a high discrimination power based on their sensitivity values shown in Table 1. As expected and known , the Wiener Index  and Randić Index  do possess a relatively high degree of degeneracy leading to low sensitivities. However, it is known that, for instance, information-theoretic measures ,  do often have a high discrimination power. For comparing such measures with ours, we also calculated the sensitivities of the two entropic measures
which were developed by Bonchev . Here, stands for the occurrence of the distance value in the distance matrix . We see in Table 1 that the resulting sensitivities are much better than the ones obtained by calculating and .
Now, we evaluate the discrimination power of the polynomial-based descriptors. Corresponding to the fact that the characteristic polynomial of a graph is degenerated  (i.e., many non-isomorphic graphs have the same spectra), it is not surprising that the sensitivity values for , and are much less (for both MS 2265 and AG 3982) than in case of considering the information polynomial. In fact, the discrimination power of when taking the characteristic polynomial into account (i.e., they become to ) is very little. Finally, we also remark that are less degenerated than and .
Also, Table 3 shows some characteristics of the spectra concerning MS 2265 and AG 3982. For instance, stands for the number of zeros (eigenvalues) of the information polynomial less than zero. stands for the minimal eigenvalue and for the maximal one. The table gives information about the distribution of the zeros with respect to the used databases. For both MS 2265 and AG 3982, we get the result that approximately 70% of the eigenvalues are positive, 25% are negative.
As conclusive remarks, the obtained results (in particular, see Table 1) show that the spectrum of the information polynomial seems to contain useful information for defining special molecular descriptors. In particular, we infer that the information polynomials of our chemical graphs are less degenerated than the corresponding characteristic polynomials. From this, we also conclude that some of the novel measures () are suitable for characterizing (large) graphs structurally because they encode structural information uniquely.
In this paper, we introduced a novel graph polynomial and derived some descriptors by using the underlying zero distribution. We summarize the main findings of our paper and some future ideas as follows:
We thank Danail Bonchev, Thomas Stoll and Abbe Mowshowitz for fruitful discussions.
Also, we are grateful to Katja Hansen and Kurt Varmuza for calling our attention to the Ames mutagenicity database and providing the database MS 2265.
Competing Interests: The authors have declared that no competing interests exist.
Funding: This work was supported by the COMET Center ONCOTYROL and funded by the Federal Ministry for Transport Innovation and Technology (BMVIT) and the Federal Ministry of Economics and Labour/Federal Ministry of Economy, Family and Youth (BMWA/BMWFJ), the Tiroler Zukunftsstiftung (TZS), and the State of Styria represented by the Styrian Business Promotion Agency (SFG) (and supported by the University for Health Sciences, Medical Informatics and Technology and BIOCRATES Life Sciences AG). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.