Measures based on Graph Automorphism

Quantitative network analysis (or Quantitative Graph Theory) is a new branch of graph theory. Instead of only describing graphs by using structural features, this theory puts the emphasis on quantifying structural information. Methods for the quantitative analysis of graphs can be divided into two categories: Graph comparison (similarity/distance) and graph characterization by using graph measures/indices/descriptors. In fact, the question of quantifying structural information of graphs arises in various scientific disciplines, such as chemoinformatics, chemometrics, bioinformatics, systems biology, finance and so forth. Following this idea, quantitative graph measures to characterize graphs structurally have been investigated extensively. For example, measures based on Shannons entropy, distances, vertex degrees and so forth have been explored and used in various disciplines. However, measures based on the complete automorphism group of a graph have only been little investigated. The main reason is possibly related to the high computational complexity of the corresponding algorithms. In this project, we define and examine quantitative network measures based on the complete automorphism group of (chemical) networks. To calculate the measures, we use the fast software SubMat. Also we deal with establishing bounds for estimating the size of vertex orbits and automorphism groups for labeled chemical graphs. The goal of this research project is twofold: First, we explore mathematical properties of automorphism-based graph measures. Second, by making use of the established results, we would like to improve the usage of these measures for problems in QSPR (Quantitative Structure-Property Relationships) that is a sub-area of mathematical chemistry and chemoinformatics. But we again emphasize that the major part of the project deals with analyzing mathematical properties of the automorphism-based graph measures. As application we put the emphasis on applying (existing and novel) automorphism-based measures to data sets containing chemical structure data represented by labeled graphs. Also a concrete problem to start with will be clustering molecular structures by using the mentioned automorphism-based graph measures. Novel applications in chemoinformatics is the ideal case. But first and foremost, we aim to get a better and more fundamental understanding of these methods in the sense of performing basic research.

Quantitative network analysis has been a new branch of graph theory. Instead of only describing graphs by using structural features, this theory puts the emphasis on quantifying structural information. Methods for the quantitative analysis (graph measures) of graphs can be divided into two categories: Graph comparison (similarity/distance) and graph characterization by using graph measures/indices/descriptors. In fact, the question of quantifying structural information of graphs arises in various scientific disciplines, such as chemoinformatics, chemometrics, bioinformatics, systems biology, finance and so forth. The mentioned measures have been explored extensively in science and in this project. For example, measures based on Shannon's entropy, distances, vertex degrees and so forth have been explored and used in various disciplines. However, measures based on the complete automorphism group of a graph have only been little investigated. The main reason is possibly related to the high computational complexity of the corresponding algorithms. In this project, we explored quantitative network measures based on the complete automorphism group of graphs. We obtained many analytical and computational results in this project. The goal of this research project was twofold: First, we explored mathematical properties of automorphism-based graph measures. Second, by making use of the established results, improved the usage of these measures for problems in QSPR (Quantitative Structure-Property Relationships) that is a sub-area of mathematical chemistry and chemoinformatics. Also, we pushed using these measures in chemoinformatics in the sense of basic research.