Quantitative Graph Theory: A new branch of graph theory and network science

Quantitative Graph Theory: A new branch of graph theory and network science

Information Sciences 418–419 (2017) 575–580 Contents lists available at ScienceDirect Information Sciences journal homepage: www.elsevier.com/locate...

422KB Sizes 0 Downloads 15 Views

Information Sciences 418–419 (2017) 575–580

Contents lists available at ScienceDirect

Information Sciences journal homepage: www.elsevier.com/locate/ins

Quantitative Graph Theory: A new branch of graph theory and network science Matthias Dehmer a,b,∗, Frank Emmert-Streib c,d, Yongtang Shi e a

Department of Mechatronics and Biomedical Computer Science, UMIT, Hall in Tyrol, Austria College of Computer and Control Engineering, Nankai University, Tianjin 300350, P.R. China c Computational Medicine and Statistical Learning Laboratory, Department of Signal Processing,Tampere University of Technology, Finland d Institute of Biosciences and Medical Technology, 33520 Tampere, Finland e Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, China b

a r t i c l e

i n f o

Article history: Received 6 January 2016 Revised 15 January 2017 Accepted 2 August 2017 Available online 12 August 2017 MSC: 62D99 05C75 68R10 90B10

a b s t r a c t In this paper, we describe some highlights of the new branch quantitative graph theory and explain its significant different features compared to classical graph theory. The main goal of quantitative graph theory is the structural quantification of information contained in complex networks by employing a measurement approach based on numerical invariants and comparisons. Furthermore, the methods as well as the networks do not need to be deterministic but can be statistic. As such this complements the field of classical graph theory, which is descriptive and deterministic in nature. We provide examples of how quantitative graph theory can be used for novel applications in the context of the overarching concept network science. © 2017 Elsevier Inc. All rights reserved.

Keywords: Quantitative Graph Theory Networks Statistics Graphs Data Science

1. Introduction The research in graph theory has started in the thirties by König [46]. Afterwards many deep research problems like planarity [47], graph minors [66] and other fundamental problems [39] have been explored. Seminal work was done by Harary [38,39] who investigated numerous problems in graph theory. For example, Harary [38] defined graph measures for analyzing social networks as one of the first. In the nineteens, many other emerging areas in graph theory such as Extremal Graph Theory [9], Random Graph Theory [10] and Algebraic Graph Theory [36] have been established. There is no doubt that graph-theoretical approaches and methods have been applied extensively in many areas. A small subset thereof is pattern recognition [19], computational biology [31,44], chemoinformatics [63,64,78], cognitive modeling [72], computational linguistics [55] and web mining [25]. Other problems in network analysis can be found in [32].



Corresponding author. E-mail addresses: [email protected], [email protected] (M. Dehmer), [email protected] (F. Emmert-Streib), [email protected] (Y. Shi). http://dx.doi.org/10.1016/j.ins.2017.08.009 0020-0255/© 2017 Elsevier Inc. All rights reserved.

576

M. Dehmer et al. / Information Sciences 418–419 (2017) 575–580

Fig. 1. Quantitative graph theory as a branch of graph theory and network science.

In [21,24], we explained that most of the results which have been achieved in Graph Theory so far are descriptive approaches for describing graphs structurally. In contrast, Dehmer and Emmert-Streib [21,24] defined Quantitative Graph Theory as the quantification of structural information of graphs instead of characterizing graphs only descriptively. As pointed out in [21,24], the aspect of measurement is crucial for this theory. The quantification of structural information has been mainly performed by using graph-theoretical measures (local and global). In this paper, we highlight important issues of Quantitative Graph Theory and classify this graph-theoretical branch. Quite generally speaking, it could be understood as a subarea of Data Science as seen in Fig. 1. In particular, we demonstrate why it is useful to distinguish between classical Graph Theory and Statistical Network Analysis. Understanding these differences is crucial for an efficient analysis of the underlying mathematical apparatus [21,24] as well as novel applications. As in Network Science one starts thinking from data, it is important to know and understand what kind of methods are available to analyze a particular data set. Hence, we believe that this contribution can be valuable to perform and classify Quantitative Graph Theory in the context of Data Science efficiently. 2. Quantitative graph theory In [24], Quantitative Graph Theory has been defined as a measurement approach to quantify structural information of networks. In general, local, global or comparative graph measures can be employed for measuring structural information. See also Section 3. We emphasize that this definition complements (classical) graph theory which mainly deals with the description of structural properties of graphs, see [39]. Examples for pure descriptive graph theory methods are graph colorings, graph embeddings and decompositions, and characterizations of graphs like the Theorem of Kuratowski [47]. In contrast, pure quantitative methods are quantitative graph measures that are based on estimating structural features of networks [20]. The latter class of methods can be interpreted as graph complexity measures. Seminal work in this area was done by Mowshowitz [56] and Bonchev [11]. Note that the ambiguity of some methods belonging to both Descriptive and Quantitative Graph Theory has been explained in [24]. In Fig. 1, we present a conceptual overview that shows the connection of Quantitative Graph Theory within some other related fields. First, we note that Network Science comprises both, Graph Theory and Statistical Network Analysis because it is the most generic field. The major difference between Graph Theory and Statistical Network Analysis is that the graphs as well as the methods of Graph Theory are purely deterministic, whereas in statistical network analysis the networks and the methods may be non-deterministic. A cause for the structural non-deterministicness may be given by, e.g., measurement errors or signal variability used to infer such networks [31]. Hence, the methods applied are based on probabilistic and statistical principles. Furthermore, Quantitative Graph Theory is also a branch of Graph Theory which relates to quantify structural information of networks. This is in contrast to classical Graph Theory which mainly deals with descriptive graph analysis, as discussed above. Interestingly, one can see that random graph theory is on one hand deterministic, when describing properties of random graphs. On the other hand, the methods and the random graphs themselves are often probabilistic and, hence, this subfield is also non-deterministic in nature. As known, quantitative graph theory has many important applications in various scientific areas. Using web algorithms like PageRank and analyzing properties of social network analysis are two well-known examples, see [16,60,79]. For instance, the famous PageRank algorithm [60] operates on web graphs and it’s based on employing quantitative techniques and graph invariants such as eigenvalues. Social network analysis already emerged in the forties and fifties. Classical contributions thereof deal with developing graph-theoretical measures based on shortest paths and vertex degrees. Those were firstly

M. Dehmer et al. / Information Sciences 418–419 (2017) 575–580

577

utilized by Bavelas [5,6]. More recent developments put the emphasis on developing centrality measures like betweenness, closeness, eigenvector-based measures and others detecting communities and clans, see [65,79]. Modern contributions in social network analysis also involve using network visualization, link classification and data science methods to analyze social networks meaningfully [16]. 3. Methods used in quantitative graph theory According to Dehmer et al. [24], Quantitative graph theory can be divided into two major categories, namely, comparative graph analysis [24] and graph characterization by using numerical graph invariants is another category which relates to determine the structural complexity of networks. In the following, we give some prominent examples of methods for these two categories. For more details see [24]. 3.1. Comparative graph analysis Comparative graph analysis means determining the structural similarity or distance between two or more networks. A problem has been choosing the right concept for this task meaningfully as a graph similarity measure depends on an underlying concept. When doing so, two main classes thereof namely (exact graph matching) [82] and inexact matching [14] to compare networks structurally have been developed. In particular, methods from exact graph matching have been demanding to use for large networks as the measures rely on graph isomorphism. As known, the complexity of the graph isomorphism has not yet determined for arbitrary networks. Comparative techniques for networks have been widely applied in many scientific disciplines [34]. Examples are artificial intelligence and pattern recognition [19], computational biology [31,44], chemoinformatics [63,78], image recognition [41, [73], and applied mathematics [22,25]. A subset thereof is: • • • • •

Isomorphism-based Measures [45,71,82]. Graph Edit Distance [4,13,18] Iterative Graph Similarity Methods [7,81] String-based Measures [25,33,67] Graph Kernels [12,40]

3.1.1. Applications As many tasks in machine learning rely on similarity concepts, it has been straightforward to use graph similarity (comparative network analysis) for applications. For instance, graph similarity measures can be used to compare and to classify structures representing real objects which can be visualized as relational structures. When doing so, it has been also important to use graph similarity concepts in machine learning as the underlying algorithms are often rely on similarity between objects to be processed. For instance, the following application areas turned out to be useful and important: • • • •

Similarity of Document Structures [15,26]. Tree Similarity [43,68] Molecular Similarity [22,53,64]. Statistical Graph Matching [69,74].

It is obvious that for some specific problems, one needs special measures which are not require to operate on the entire network. An example for this are tree similarity measures [43,68] that operate on trees only representing connected and acyclic networks. Using such special comparative measures may be beneficial to cluster document or RNA structures that are represented by trees only. This gives us an idea about the complexity of the network similarity problem as various graph classes exist when it comes to realize a particular application. 3.2. Graph characterization In quantitative graph theory [24], graph characterization relates to determine the complexity of a given network by using numerical graph invariants. Graph invariants are graph measures to characterize graphs structurally which are invariant under isomorphism [75]. Examples for local graph invariants are vertex degrees or vertex eccentricities [39,70]; global graph invariants are, for instance, graph entropy measures or measures which are based on distances in networks like the wellknown Wiener index [75]. All those measures have in common that they are functions which map networks to the reals [75]. A special kind of graph measures are so-called topological indices [75]. Note that they have been used in mathematical and structural chemistry extensively to characterize molecular structures based on their size, shape, branching and cyclicity [75]. Importantly, an undesired aspect of all structural graph measures is their degeneracy [23,75]; that means, many of these graphs measures fail to discriminate the structure of non-isomorphic graphs by their values uniquely. This property often has a negative effect when determining the complexity of networks numerically. Therefore it has been important to investigate the problem on a large scale to finally obtain a classification of graph measures according to their properties such as degeneracy, structural interpretation and so forth, see [23,75]. Based on graph invariants to be used, graph measures can be roughly divided into the following classes:

578

M. Dehmer et al. / Information Sciences 418–419 (2017) 575–580

• Distance-based graph measures. Examples: various kinds of Wiener indices, the Balaban index and eccentricity [52,70,80]. • Degree-based measures. Examples: Randic´ index and Zagreb index [49,59,62]. • Eigenvalue-based measures. Examples: Various kinds of graph energies, the spectral radius and the HOMO-LUMO index, see [48,50,51]. • Information-theoretic measures. Examples: Vertex-orbit entropy due to Mowshowitz and partition-independent graph entropies [17,28]. As to applications, these graph measures have been used in chemoinformatics (e.g., QSAR and QSPR) [75] for predicting biological or physico-chemical properties of molecular structures [30,75]. Also, structural graph measures have been employed to analyze phylogenetic properties of metabolic networks [54]. Moreover, graph measures got attention from areas outside chemistry and biology as structural systems representing networks occur in many other disciplines too. Examples are computational linguistics [3] and web structure mining [16] where web-based units have been explored by using structural indices. For applications, it turned out to be important understanding the properties of graph measures properly. Otherwise, the use of those measure might be misleading. We here summarize some important properties as follows: • • • • •

Uniqueness of graph measures (i.e., degeneracy) [23,75]. Information inequalities describing interrelations of information-theoretic network measures [27]. Structural interpretation [24]. Usefulness and quality of graph measures [24,35]. Correlation of graph measures [24].

3.3. Software for quantitative graph analysis In this section, we briefly discuss free and commercial software to analyze complex networks. 3.3.1. Programs developed for the statistical programming language R The multiparadigm language R [2] turned out to be useful for analyzing networks from various disciplines. An example is the R-package NetBioV [77] for visualizing large biological networks. Other standard R-libraries for structural network analysis are igraph and graph. They contain many methods like the calculation of shortest paths in networks. However they only offer a very few quantitative methods for characterizing networks. For this purpose, the R-package QuACN [58] has been developed which contains over 150 structural network measures. Further R-package for performing network analysis can be found in [24,57]. 3.3.2. Commercial software A well-known example of commercial software for calculating structural and molecular indices (measures) is Dragon [76]. Actually it contains more than 40 0 0 molecular descriptors [75] for characterizing molecular networks. This software has been proven useful for QSAR and QSPR [30]. Other commercial pieces of software are, e.g., the Sentinel Visualizer [37] and Sonamine [1]. Sentinel Visualizer [37] is a software for analyzing and visualizing social networks. Sonamine [1] has been developed for performing data mining and simulation techniques for massive social networks. 3.3.3. Conjecture engines Conjecture engines [29,61] are tools that have been used to generate conjectures when proving statements on topological graph measures. They can be used to test the validity of inequalities involving topological graph measures. The tool Graffiti [29] is a prominent example and has been famous for generating conjectures involving the general and simple Randic´ index. A successor thereof is GrInvIn [61] which is a freely available as Java-Application A shortcoming of GrInvIn is the quite weak conjecture engines which does not allow to use this tool to explore complex conjectures. 3.4. Complexity results In this section, we briefly elaborate on the complexity of the main tasks of quantitative graph theory. In this context, we mention that most of the measures used in quantitative graph theory can be derived from utilizing graph-theoretical matrices [42]. Hence, the computation of those measures/methods can be achieved in polynomial time. For instance, the calculation of the shortest path between two vertices of a connected network is O(N2 ); N stands for the number of vertices. Yet, computing all shortest path between the vertices of a given network leads to O(N3 ). We emphasize that problems like graph traversal and computing k-hops have strong links to the just mentioned ones and can be also performed with polynomial time complexity. We also mention the matching problem which is not purely quantitative. Crucial algorithms in this framework have been the Ford-Fulkerson algorithm or the Hopcroft-Karp algorithm, see, e.g., [8].

M. Dehmer et al. / Information Sciences 418–419 (2017) 575–580

579

4. Summary and conclusion In this paper, we explained some highlights of Quantitative Graph Theory. Importantly, we pointed our that most of the contributions in classical Graph Theory dealt with descriptive approaches for describing structural features of networks, see Section 1. Mainly, we classified Quantitative Graph Theory correctly in the context of Data Science. From a very general point of view, this area can be considered as a subarea of Data Science but with special properties. We have elaborated on these properties in this work. As quantitative approaches have been applied in many scientific disciplines, we believe that this particular branch in Graph Theory is of interest for those who deal with structural data. We hope that many other areas will be found where Quantitative Graph Theory turns out to be applicable. Acknowledgments Matthias Dehmer thanks the Austrian Science Funds for supporting this work (project P26142). Yongtang Shi was partially supported by the Natural Science Foundation of Tianjin (No. 17JCQNJC0 030 0) and National Natural Science Foundation of China. References [1] Sonamine. http://www.sonamine.com/home/; 2009. [2] R, software, a language and environment for statistical computing. www.r-project.org; 2011. R Development Core Team, Foundation for Statistical Computing, Vienna, Austria. [3] O. Abramov, T. Lokot, Typology by means of language networks. applying information theoretic measures to morphological derivation networks, in: M. Dehmer, F. Emmert-Streib, A. Mehler (Eds.), Towards an Information Theory of Complex Networks: Statistical Methods and Applications, Birkhäuser, Boston/Basel, 2011, pp. 321–346. [4] N. Alon, U. Stav, The maximum edit distance from hereditary graph properties, J. Combin. Theory Ser-B 98 (2008) 672–697. [5] A. Bavelas, A mathematical model for group structure, Human Organizations 7 (1948) 16–30. [6] A. Bavelas, Communication patterns in task-oriented groups, J. Acoust. Soc. Amer. 22 (1950) 725–730. [7] V. Blondel, A. Gajardo, M. Heymans, P. Senellart, P.V. Dooren, A measure of similarity between graph vertices: applications to synonym extraction and web searching, SIAM Rev. 46 (2004) 647–666. [8] B. Bollabás, Modern Graph Theory, Graduate Texts in Mathematics, Springer, New York, 1998. [9] B. Bollobás (Ed.), Extremal Graph Theory, Academic Press, London, 1978. [10] B. Bollobás (Ed.), Random Graphs, Cambridge Univ. Press, Cambridge, 2001. [11] D. Bonchev, Information theoretic measures of complexity, in: R. Meyers (Ed.), Encyclopedia of Complexity and System Science, 5, Springer, 2009, pp. 4820–4838. [12] M. Borgwardt, Graph kernels, Ph.D. thesis, Ludwig-Maximilians-Universität München, Fakultät für Mathematik, Informatik und Statistik, 2007. [13] H. Bunke, What is the distance between graphs ? Bulletin of the EATCS 20 (1983) 35–39. [14] H. Bunke, Recent developments in graph matching, in: 15-th International Conference on Pattern Recognition, 2, 20 0 0, pp. 117–124. [15] D. Buttler, A short survey of document structure similarity algorithms, in: International Conference on Internet Computing, 2004, pp. 3–9. [16] S. Chakrabarti, Mining the Web: Discovering Knowledge from Hypertext Data, Morgan Kaufmann, San Francisco, 2002. [17] Z. Chen, M. Dehmer, F. Emmert-Streib, Y. Shi, Entropy of weighted graphs with Randic´ weights, Entropy 17 (2015) 3710–3723. [18] F. Chung, P. Erdös, J. Spencer, Extremal subgraphs for two graphs, J. Combin. Theory Ser-B 38 (1985) 248–260. [19] D. Conte, F. Foggia, C. Sansone, M. Vento, Thirty years of graph matching in pattern regocnition, Int. J. Pattern Recognit Artif Intell. 18 (2004) 265–298. [20] M. Dehmer (Ed.), Structural Analysis of Complex Networks, Birkhäuser Publishing, 2010. [21] M. Dehmer, F. Emmert-Streib, Quantitative Graph Theory. Theory and Applications, CRC Press, 2014. [22] M. Dehmer, F. Emmert-Streib, Y. Shi, Interrelations of graph distance measures based on topological indices, PLoS ONE 9 (2014) e94985. [23] M. Dehmer, M. Grabner, K. Varmuza, Information indices with high discriminative power for graphs, PLoS ONE 7 (2) (2012). doi:10.1371/journal.pone. 0031214. [24] M. Dehmer, V. Kraus, F. Emmert-Streib, S. Pickl, What is Quantitative Graph Theory ?, CRC Press, 2014, pp. 1–33. [25] M. Dehmer, A. Mehler, A new method of measuring similarity for a special class of directed graphs, Tatra Mountains Mathematical Publications 36 (2007) 39–59. [26] M. Dehmer, A. Mehler, F. Emmert-Streib, Graph-theoretical characterizations of generalized trees, in: Proceedings of the International Conference on Machine Learning: Models, Technologies & Applications (MLMTA’07), Las Vegas/USA, 2007, 2007, pp. 113–117. [27] M. Dehmer, A. Mowshowitz, Inequalities for entropy-based measures of network information content, Appl. Math. Comput. 215 (2010) 4263–4271. [28] M. Dehmer, A. Mowshowitz, A History of Graph Entropy Measures, Inf. Sci. 1 (2011) 57–78. [29] E. DeLaVina, Some history of the development of graffiti, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 69: Graphs and Discovery (2005) 81–118. [30] J. Devillers, A.T. Balaban, Topological Indices and Related Descriptors in QSAR and QSPR, Gordon and Breach Science Publishers, Amsterdam, The Netherlands, 20 0 0. [31] F. Emmert-Streib, The chronic fatigue syndrome: A comparative pathway analysis, J. Comput. Biol. 14 (7) (2007). [32] F. Emmert-Streib, M. Dehmer (Eds.), Analysis of Microarray Data: A Network-based Approach, Wiley VCH Publishing, 2010. [33] F. Emmert-Streib, M. Dehmer, J. Kilian, Classification of large graphs by a local tree decomposition, in: H.R.A. et al. (Ed.), Proceedings of DMIN’05, International Conference on Data Mining, Las Vegas, USA, 2006, pp. 200–207. [34] F. Emmert-Streib, M. Dehmer, Y. Shi, Fifty years of graph matching, network alignment and comparison, Inform. Sci. 346–347 (2016) 180–197. [35] B. Furtula, I. Gutman, M. Dehmer, On structure-sensitivity of degree-based topological indices, Appl. Math. Comput. 219 (2013) 8973–8978. [36] C. Godsil, G. Royle, Algebraic Graph Theory, Springer–Verlag, New York, 2001. [37] Group F.A.S.. Sentinel visualizer. www.fmsasg.com; 2015. [38] F. Harary, Status and contrastatus, Sociometry 22 (1959) 23–43. [39] F. Harary, Graph Theory, Addison Wesley Publishing Company, Reading, MA, USA, 1969. [40] T. Horváth, T. Gärtner, S. Wrobel, Cyclic pattern kernels for predictive graph mining, in: Proceedings of the 2004 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2004, pp. 158–167. [41] S.M. Hsieh, C.C. Hsu, Graph-based representation for similarity retrieval of symbolic images, Data Knowl. Eng. 65 (3) (2008) 401–418. [42] D. Janežic´ , A. Mileževic´ , S. Nikolic´ , N. Trinajstic´ , Graph-Theoretical Matrices in Chemistry Mathematical Chemistry Monographs, University of Kragujevac and Faculty of Science Kragujevac, 2007.

580

M. Dehmer et al. / Information Sciences 418–419 (2017) 575–580

[43] T. Jiang, L. Wang, K. Zhang, Alignment of trees - an alternative to tree edit, in: CPM ’94: Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, Springer-Verlag, London, UK, 1994, pp. 75–86. [44] B.H. Junker, F. Schreiber, Analysis of Biological Networks Wiley Series in Bioinformatics;, Wiley-Interscience, 2008. [45] F. Kaden, Graphmetriken und Distanzgraphen, ZKI-Informationen, Akad Wiss DDR 2 (82) (1982) 1–63. [46] D. König, Theorie der endlichen und unendlichen Graphen, Chelsea Publishing, 1935. [47] K. Kuratowski, Sur le problème des courbes gauches en topologie, Fund. Math. Vol. 15 (1930) 271–283. [48] X. Li, Y. Li, Y. Shi, I. Gutman, Note on the HOMO-LUMO index of graphs, MATCH Commun. Math. Comput. Chem. 70 (2013) 85–96. [49] X. Li, Y. Shi, A survey on the Randic´ index, MATCH Commun. Math Comput. Chem. 59 (1) (2008) 127–156. [50] X. Li, Y. Shi, I. Gutman, Graph Energy, Springer, New York, 2012. [51] L. Lovász, J. Pelikán, On the eigenvalues of trees, Periodica Mathematica Hungarica 3 (1–2) (1973) 175–182. [52] J. Ma, Y. Shi, Z. Wang, J. Yue, On the eigenvalues of trees, On wiener polarity index of bicyclic networks 6 (2016). 19066. [53] G.M. Maggiora, V. Shanmugasundaram, Molecular Similarity Measures, in: Chemoinformatics: Concepts, Methods, and Tools for Drug Discovery, Humana Press, Totowa, NJ, USA, 2004, pp. 1–50. [54] A. Mazurie, D. Bonchev, B. Schwikowski, G.A. Buck, Phylogenetic distances are encoded in networks of interacting pathways, Bioinformatics 24 (22) (2008) 2579–2585. [55] A. Mehler, P. Weiß, A. Lücking, A network model of interpersonal alignment, Entropy 12 (6) (2010) 1440–1483, doi:10.3390/e12061440. [56] A. Mowshowitz, Entropy and the complexity of the graphs I: An index of the relative complexity of a graph, Bull. Math. Biophys. 30 (1968) 175–204. [57] L.A.J. Müller, M. Dehmer, F. Emmert-Streib, Computational Medicine, chap. Network-based Methods for Computational Diagnostics by Means of R, Springer, 2012, pp. 185–197. [58] L.A.J. Müller, M. Schutte, K.G. Kugler, M. Dehmer, QuACN: Quantitative Analyze of Complex Networks, 2012. R Package Version 1.6. URL http://cran. r-project.org/web/packages/QuACN/index.html. [59] S. Nikolic´ , G. Kovacˇ evic´ , A. Milicˇ evic´ , N. Trinajstic´ , The Zagreb Index 30 Years After, Croat. Chem. Acta 76 (2003) 113–124. [60] L. Page, S. Brin, R. Motwani, T. Winograd, The Pagerank citation ranking: Bringing order to the web, Technical Report, Stanford InfoLab, 1999. [61] A. Peeters, K. Coolsaet, G. Brinkmann, N. Cleemput, V. Fack, Grinvin in a nutshell, J. Math. Chem. 45 (2009) 471–477. [62] M. Randic´ , On characterization of molecular branching, J. Amer. Chem. Soc. 97 (1975) 6609–6615. [63] M. Randic´ , Design of molecules with desired properties. molecular similarity approach to property optimization, in: M.A. Johnson, G. Maggiora (Eds.), Concepts and Applications of Molecular Similarity, Wiley, 1990, pp. 77–145. [64] M. Randic´ , C.L. Wilkins, Graph theoretical approach to recognition of structural similarity in molecules, J. Chem. Inf. Comput. Sci. 19 (1979) 31–37. [65] F. Roberts, Applications of Combinatorics and Graph Theory to the Biological and Social Sciences Series, Springer, 1989. [66] N. Robertson, P.D. Seymour, Graph minors. part 2. algorithmic aspects of tree-width, J. Algorithms 7 (1986) 309–322. [67] A. Robles-Kelly, R. Hancock, Edit distance from graph spectra, in: Proceedings of the IEEE International Conference on Computer Vision, 2003, pp. 234–241. [68] S.M. Selkow, The tree-to-tree editing problem, Inf. Process Lett. 6 (6) (1977) 184–186. [69] L.B. Shams, M.J. Brady, S. Schaal, Graph matching vs mutual information maximization for object detection, Neural Networks 14 (3) (2001) 345–354. [70] V.A. Skorobogatov, A.A. Dobrynin, Metrical Analysis of Graphs, MATCH Commun. Math. Comp. Chem. 23 (1988) 105–155. [71] F. Sobik, Graphmetriken und klassifikation strukturierter objekte, ZKI-Informationen, Akad Wiss DDR 2 (82) (1982) 63–122. [72] E. Sommerfeld, Systematization and Formalization of Cognitive Structure Transformations on the Basis of Graph Transformations, in: T. Marek (Ed.), Action and performance: Models and tests. Contributions to the quantitative psychology and its methodology, 1990, pp. 105–120. [73] C. Theoharatos, N. Laskaris, G. Economou, S. Fotopoulos, A similarity measure for color image retrieval and indexing based on the multivariate two sample problem, in: Proceedings of EUSIPCO, Vienna, Austria, 2004. [74] C. Theoharatos, V.K. Pothos, N.A. Laskaris, G. Economou, S. Fotopoulos, Multivariate image similarity in the compressed domain using statistical graph matching, Pattern Recognit. 39 (10) (2006) 1892–1904. [75] R. Todeschini, V. Consonni, R. Mannhold, Handbook of Molecular Descriptors, Wiley-VCH, Weinheim, Germany, 2002. [76] Todeschini R., Consonni V., Mauri A., Pavan M.. Dragon, software for calculation of molecular descriptors. www.talete.mi.it; 2004. Talete srl, Milano, Italy. [77] S. Tripathi, M. Dehmer, F. Emmert-Streib, Netbiov: an r package for visualizing large network data in biology and medicine, Bioinformatics 19 (2014) 2834–2836. [78] K. Varmuza, H. Scsibrany, Substructure isomorphism matrix, J. Chem. Inf. Comput. Sci. 40 (20 0 0) 308–313. [79] S. Wasserman, K. Faust, Social Network Analysis: Methods and Applications, Cambridge University Press, 1994. [80] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69 (17) (1947) 17–20. [81] L.A. Zager, G.C. Verghese, Graph similarity scoring and matching, Appl. Math. Lett. 21 (2008) 86–94. ˇ pro pe˘ st Mathematiky 100 (1975) 371–373. [82] B. Zelinka, On a certain distance between isomorphism classes of graphs, Casopis