Characteristics and Interrelations between Methods for Comparing Relational Structures

To develop methods for analyzing graphs is a multidisciplinary problem because the underlying research problems have been widely spread over scientific disciplines. Particularly after the hype dealing with examining global properties of complex networks, it turned out that quantitative methods for exploring graphs such as graph similarity and other graph measures are crucial. In this project, we put the emphasis on investigating methods to measure the structural similarity of graphs generally referred to as graph matching. Particularly we explore mathematical properties of such methods in depth. Early contributions deal with exploring isomorphic and subgraph isomorphic relations between graphs. But the resulting graph similarity measures or metrics are, for general graphs, computationally inefficient because the isomorphism and subgraph isomorphism problems are known for their non-feasible time complexity. Consequently, other approaches based on error-tolerant graph comparison have also been developed and investigated. Importantly, all these techniques have been spread across a range of disciplines but a thorough analysis of their mathematical properties has not been performed so far. The goal of this research project to investigate mathematical properties of graph comparison methods as there is a lack of rather deep results in this field. For instance, this relates to prove interrelations between the graph comparison methods and examining their structural interpretation.

The goal of this research project was to investigate mathematical properties of graph comparison methods. Our results comprise developing new graph similarity techniques as well as investigating their relationships. For instance, this relates to prove inequalities between the graph comparison methods representing graph similarity or distance measures and examining their structural interpretation. Developing comparative graph methods is a multidisciplinary problem because the underlying research problems have been widely spread over scientific disciplines. Particularly after the hype dealing with examining global properties of complex networks, it turned out that quantitative methods for exploring graphs such as graph similarity and other graph measures are crucial. In this project, we have investigated methods to measure the structural similarity of graphs generally referred to as graph matching. Also, we explored mathematical properties of such methods in depth. Also, we have investigated topological indices which often serve as an important component to define graph similarity or distance. Given the fact that early contributions dealt with exploring isomorphic and subgraph isomorphic relations between graphs, we here put the emphasis on methods without computing graph isomorphism. Hence, other approaches based on error-tolerant graph comparison have also been developed and investigated. So, all these techniques have been spread across a range of disciplines and we performed a thorough analysis of mathematical properties of selected comparative methods.