Interrelations of graph distance measures based on topological indices

Matthias Dehmer; Frank Emmert-Streib; Yongtang Shi

doi:10.1371/journal.pone.0094985

Interrelations of graph distance measures based on topological indices

PLoS One. 2014 Apr 23;9(4):e94985. doi: 10.1371/journal.pone.0094985. eCollection 2014.

Authors

Matthias Dehmer¹, Frank Emmert-Streib², Yongtang Shi³

Affiliations

¹ Department of Computer Science, Universität der Bundeswehr München, Neubiberg, Germany; Division for Bioinformatics and Translational Research, UMIT, Hall in Tyrol, Austria.
² Computational Biology and Machine Learning Laboratory, Center for Cancer Research and Cell Biology, School of Medicine, Dentistry and Biomedical Sciences, Faculty of Medicine, Health and Life Sciences, Queen's University Belfast, Belfast, United Kingdom.
³ Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin, China; College of Computer and Control Engineering, Nankai University, Tianjin, China.

Abstract

In this paper, we derive interrelations of graph distance measures by means of inequalities. For this investigation we are using graph distance measures based on topological indices that have not been studied in this context. Specifically, we are using the well-known Wiener index, Randić index, eigenvalue-based quantities and graph entropies. In addition to this analysis, we present results from numerical studies exploring various properties of the measures and aspects of their quality. Our results could find application in chemoinformatics and computational biology where the structural investigation of chemical components and gene networks is currently of great interest.

Publication types

Research Support, Non-U.S. Gov't

MeSH terms

Computational Biology / methods*
Computer Graphics
Models, Theoretical

Grants and funding

Matthias Dehmer and Yongtang Shi thank the Austrian Science Funds for supporting this work (project P26142). Yongtang Shi has also been supported by the National Science Foundation of China. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.