“Topological Stress” Concept for Quantizing Chemical Graph Similarity Scores

Abstract

Graph invariants can be used to infer molecular structural properties of graphs. In this work, a new distance metric between vertices of a graph is proposed to find the structural similarity between graphs. For this, a new distance matrix (known as IE matrix) is constructed based on the inverse Euclidean distance between graph vertices. This new representation directly depicts the skeletal structure of the vertices in the n-dimensional space. In this space, minimal distance between vertices implies high topological proximity between them. Based on IE matrix, a unique signature is generated for every graph which is used to find similarity between graphs. A new concept “Topological Stress” is introduced that reveals the topological variation of a vertex with other vertices. Using this stress concept, similar topological stressed vertices between different graphs are identified and further explains the methylalkane interconversion reactions with the help of signature and dominant Eigen value. The entirety of the matrix is represented as a singularity which may serve as a unique molecular index (IEGPr) for chemical graphs. Similarity between graphs are calculated based on their corresponding IEGPr values. The resultant quantified similarity score lies between 0 and 1, referring value 1 for exact isomorphic. From the computational study, it is observed that IEGPr value is generally very low implying a low-value nomenclature of chemical graphs. Empirical study shows that the computational time required for the similarity identification procedure is scalable. From this it can be inferred that by improvising/reframing this measure a few application oriented graph matching problems can be tackled in polynomial time/near-polynomial time.