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.

No additional funding sources recorded.