Fifty years of graph matching, network alignment and network comparison. (English) Zbl 1398.68393
Summary: In this paper we survey methods for performing a comparative graph analysis and explain the history, foundations and differences of such techniques of the last 50 years. While surveying these methods, we introduce a novel classification scheme by distinguishing between methods for deterministic and random graphs. We believe that this scheme is useful for a better understanding of the methods, their challenges and, finally, for applying the methods efficiently in an interdisciplinary setting of data science to solve a particular problem involving comparative network analysis.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05-03 | History of combinatorics |
| 68-03 | History of computer science |
| 92-03 | History of biology |
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C80 | Random graphs (graph-theoretic aspects) |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C90 | Applications of graph theory |
| 68T10 | Pattern recognition, speech recognition |
| 92C42 | Systems biology, networks |
| 92E10 | Molecular structure (graph-theoretic methods, methods of differential topology, etc.) |
Keywords:
network comparison; network similarity; graph matching; quantitative graph theory; biological networks; computational graph theoryReferences:
| [1] | Adler, M.; Mitzenmacher, M., Towards compressing web graphs, In Proceedings of the IEEE Data Compression Conference (DCC), 203-212, (2001) |
| [2] | Aladag, A. E.; Erten, C., Spinal: scalable protein interaction network alignment, Bioinformatics, 29, 7, 917-924, (2013) |
| [3] | Albert, R.; Barabási, A. L., Statistical mechanics of complex networks, Rev. Mod. Phys., 74, 47-97, (2002) · Zbl 1205.82086 |
| [4] | Ali, W.; Rito, T.; Reinert, G.; Sun, F.; Deane, C. M., Alignment-free protein interaction network comparison, Bioinformatics, 30, 17, i430-i437, (2014) |
| [5] | Blondel, V.; Gajardo, A.; Heymans, M.; Senellart, P.; Dooren, P. V., A measure of similarity between graph vertices: applications to synonym extraction and web searching, SIAM Rev., 46, 647-666, (2004) · Zbl 1055.05099 |
| [6] | Borgwardt, M., Graph Kernels, (2007), Ludwig-Maximilians-Universität München, Fakultät für Mathematik, Informatik und Statistik, Ph.D. thesis |
| [7] | Broderick, G.; Fuite, J.; Kreitz, A.; Vernon, S. D.; Klimas, N.; Fletcher, M. A., A formal analysis of cytokine networks in chronic fatigue syndrome, Brain Behav. Immun., 24, 7, 1209-1217, (2010) |
| [8] | Bunke, H., What is the distance between graphs ?, Bull. EATCS, 20, 35-39, (1983) |
| [9] | Bunke, H., On a relation between graph edit distance and maximum common subgraph, Pattern Recognit. Lett., 18, 9, 689-694, (1997) |
| [10] | Bunke, H., A graph distance metric based on the maximum common subgraph, Pattern Recognit. Lett., 19, 3, 255-259, (1998) · Zbl 0905.68128 |
| [11] | Bunke, H., Error correcting graph matching: on the influence of the underlying cost function, IEEE Trans. Pattern Anal. Mach. Intell., 21, 9, 911-917, (1999) |
| [12] | Bunke, H., Recent developments in graph matching, 15-th International Conference on Pattern Recognition, 2, 117-124, (2000) |
| [13] | Bunke, H., Graph matching: theoretical foundations, algorithms, and applications, Proceedings of Vision Interface 2000, 82-88, (2000) |
| [14] | Bunke, H.; Allermann, G., A metric on graphs for structural pattern recognition, (EUSIPCO, Proceedings of Second European Signal Processing Conference EUSIPCO, (1983)), 257-260 · Zbl 0509.68100 |
| [15] | Bunke, H.; Neuhaus, M., Graph matching. exact and error-tolerant methods and the automatic learning of edit costs, (Cook, D.; Holder, L. B., Mining Graph Data, (2007), Wiley-Interscience), 17-32 |
| [16] | Buttler, D., A short survey of document structure similarity algorithms, International Conference on Internet Computing, 3-9, (2004) |
| [17] | Casella, G.; Berger, R., Statistical Inference, (2002), Duxbury Press · Zbl 1029.62003 |
| [18] | Chartrand, G.; Saba, F.; Zou, H.-B., Edge rotations and distance between graphs, Časopis pro p̆est. Math., 110, 87-91, (1985) · Zbl 0567.05044 |
| [19] | Chartrand, G.; Goddard, W.; Henning, M. A.; Lesniak, L.; Swart, H. C.; Wall, C. E., Which graphs are distance graphs ?, Ars Comb., 29A, 225-232, (1990) · Zbl 0716.05028 |
| [20] | Chartrand, G.; Gavlas, H.; Hevia, H., Rotation and jump distances between graphs, Disc. Math. Graph Theo., 17, 285-300, (1997) · Zbl 0902.05022 |
| [21] | Clark, C.; Kalita, J., A comparison of algorithms for the pairwise alignment of biological networks, Bioinformatics, 30, 16, 2351-2359, (2014) |
| [22] | Conte, D.; Foggia, F.; Sansone, C.; Vento, M., Thirty years of graph matching in pattern recognition, Int. J. Pattern Recognit. Artif. Intell., 18, 265-298, (2004) |
| [23] | M. Dehmer, Strukturelle Analyse Web-basierter Dokumente, Multimedia und Telekooperation, F. Lehner and F. Bodendorf (Eds.), Gabler Edition Wissenschaft - Deutscher Universitätsverlag, 2006. |
| [24] | Dehmer, M., Strukturelle Analyse web-basierter Dokumente, Multimedia und Telekooperation, (2006), Deutscher Universitäts Verlag Wiesbaden |
| [25] | Dehmer, M., Information processing in complex networks: graph entropy and information functionals, Appl. Math. Comput., 201, 82-94, (2008) · Zbl 1152.05361 |
| [26] | Dehmer, M.; Emmert-Streib, F., Mining graph patterns in web-based systems: a conceptual view, (Mehler, A.; Sharoff, S.; Rehm, G.; Santini, M., Genres on the Web: Computational Models and Empirical Studies, (2010), Springer Berlin/New York), 237-253 |
| [27] | Dehmer, M.; Mehler, A., A new method of measuring similarity for a special class of directed graphs, Tatra Mount. Math. Publ., 36, 39-59, (2007) · Zbl 1142.05069 |
| [28] | Dehmer, M.; Emmert-Streib, F.; Kilian, J., A similarity measure for graphs with low computational complexity, Appl. Math. Comput., 182, 447-459, (2006) · Zbl 1111.05019 |
| [29] | Dehmer, M.; Mehler, A.; Emmert-Streib, F., Graph-theoretical characterizations of generalized trees, Proceedings of the International Conference on Machine Learning: Models, Technologies & Applications (MLMTA’07), Las Vegas/USA, 2007, 113-117, (2007) |
| [30] | Dehmer, M.; Barbarini, N.; Varmuza, K.; Graber, A., A large scale analysis of information-theoretic network complexity measures using chemical structures, PLoS ONE, 4, 12, e8057, (2009) |
| [31] | Dehmer, M.; Emmert-Streib, F.; Tripathi, S., Large-scale evaluation of molecular descriptors by means of clustering, PLoS ONE, 8, 12, e83956, (2013) |
| [32] | Dehmer, M.; Emmert-Streib, F.; Shi, Y., Interrelations of graph distance measures based on topological indices, PLoS ONE, 9, e94985, (2014) |
| [33] | (Dehmer, M.; Emmert-Streib, F.; Pickl, S., (2015), Wiley-Blackwell Weinheim) |
| [34] | Dickinson, P. J.; Bunke, H.; Dadej, A.; Kraetzl, M., Matching graphs with unique node labels, Pattern Anal. Appl., 7, 243-266, (2004) · Zbl 1422.68187 |
| [35] | Emmert-Streib, F., The chronic fatigue syndrome: a comparative pathway analysis, J. Comput. Biol., 14, 7, 961-972, (2007) |
| [36] | Emmert-Streib, F., The chronic fatigue syndrome: a comparative pathway analysis, J. Comput. Biol., 14, 7, (2007) |
| [37] | (Emmert-Streib, F.; Dehmer, M., (2010), Wiley VCH Publishing) |
| [38] | Emmert-Streib, F.; Dehmer, M., Networks for systems biology: conceptual connection of data and function, IET Syst. Biol., 5, 185-207, (2011) |
| [39] | Emmert-Streib, F.; Dehmer, M., Exploring statistical and population aspects of network complexity, PLoS ONE, 7, e34523, (2012) |
| [40] | Emmert-Streib, F.; Dehmer, M.; Kilian, J., Classification of large graphs by a local tree decomposition, (et al., H. R.A., Proceedings of DMIN’05, International Conference on Data Mining, Las Vegas, USA, (2006)), 200-207 |
| [41] | Emmert-Streib, F.; Glynn, E. F.; Seidel, C.; Bausch, C. L.; Mushegian, A., Detecting pathological pathways of the chronic fatigue syndrome by the comparison of networks, (McConnell, P.; Lin, S.; Cuticcia, A., Methods of Microarray Data Analysis VI, (2009), CreateSpace) |
| [42] | Erdös, P.; Rényi, P., On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl, 5, 17-61, (1960) · Zbl 0103.16301 |
| [43] | Felsenstein, J., Inferring Phylogenies, (2003), Sinauer Associates |
| [44] | Friedman, J. H.; Rafsky, L. C., Multivariate generalizations of the Wald-wolfowitz and Smirnov two-sample tests, Ann. Stat., 7, 4, 697-717, (1979) · Zbl 0423.62034 |
| [45] | Fuite, J.; Vernon, S.; Broderick, G., Neuroendocrine and immune network re-modeling in chronic fatigue syndrome: an exploratory analysis, Genomics, 92, 393-399, (2008) |
| [46] | Gao, X.; Xiao, B.; Tao, D.; Li, X., A survey of graph edit distance, Pattern Anal. Appl., 13, 1, 113-129, (2010) · Zbl 1422.68211 |
| [47] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, Series of Books in the Mathematical Sciences, (1979), W. H. Freeman · Zbl 0411.68039 |
| [48] | Gärtner, T.; Flach, P. A.; Wrobel, S., On graph kernels: hardness results and efficient alternatives, COLT, 129-143, (2003) · Zbl 1274.68312 |
| [49] | Gernert, D., Measuring the similarity of complex structures by means of graph grammars, Bull. EATCS, 7, 3-9, (1979) · Zbl 0411.68057 |
| [50] | Gernert, D., Graph grammars which generate graphs with specified properties, Bull. EATCS, 13, 13-20, (1981) · Zbl 0449.68037 |
| [51] | Gill, R.; Datta, S.; Datta, S., A statistical framework for differential network analysis from microarray data, BMC Bioinformat., 11, 1, 95, (2010) |
| [52] | Gusfield, D., Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology, (1997), Cambridge University Press · Zbl 0934.68103 |
| [53] | Harary, F., Graph Theory, (1969), Addison Wesley Publishing Company Reading, MA, USA · Zbl 0182.57702 |
| [54] | Hashemifar, S.; Xu, J., Hubalign: an accurate and efficient method for global alignment of protein-protein interaction networks, Bioinformatics, 30, 17, i438-i444, (2014) |
| [55] | Hayes, W.; Sun, K.; Przulj, N., Graphlet-based measures are suitable for biological network comparison, Bioinformatics, 29, 4, 483-491, (2013) |
| [56] | Höchstmann, M.; Töller, T.; Giegerich, R.; Kurtz, S., Local similarity in RNA secondary structures, Proceedings of the IEEE Computational Systems Bioinformatics Conference (CSB’03), 159-168, (2003) |
| [57] | Horváth, T.; Gärtner, T.; Wrobel, S., Cyclic pattern kernels for predictive graph mining, Proceedings of the 2004 ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 158-167, (2004) |
| [58] | Hsieh, S. M.; Hsu, C. C., Graph-based representation for similarity retrieval of symbolic images, Data Knowl. Eng., 65, 3, 401-418, (2008) |
| [59] | Hu, J.; Reinert, K., Localali: an evolutionary-based local alignment approach to identify functionally conserved modules in multiple networks, Bioinformatics, 31, 3, 363-372, (2014) |
| [60] | Jiang, T.; Wang, L.; Zhang, K., Alignment of trees—an alternative to tree edit, CPM ’94: Proceedings of the Fifth Annual Symposium on Combinatorial Pattern Matching, 75-86, (1994), Springer-Verlag London, UK |
| [61] | Junker, B. H.; Schreiber, F., Analysis of Biological Networks, Wiley Series in Bioinformatics, (2008), Wiley-Interscience |
| [62] | Kaden, F., Graphmetriken und distanzgraphen, ZKI-Inform. Akad. Wiss. DDR, 2, 82, 1-63, (1982) · Zbl 0496.05058 |
| [63] | Kaden, F., Halbgeordnete graphmengen und graphmetriken, (Sachs, H., Graphs, Hypergraphs, and Applications, 73, (1985), Teubner Leipzig, DDR), 92-95 · Zbl 0606.05062 |
| [64] | Kaden, F., Graphmetriken und isometrieproblemezugehöriger distanzgraphen, ZKI-Inform. Akad. Wiss. DDR, 1-100, (1986) · Zbl 0599.05022 |
| [65] | Kaden, F., Graph similarity and distances, (Bodendiek; Henn, R., Topics in Combinatorics and Graph Theory, (1990), Physica-Verlag), 397-404 · Zbl 0714.05022 |
| [66] | Klau, G. W., A new graph-based method for pairwise global network alignment, BMC Bioinform., 10, 1, (2009) |
| [67] | Kleinberg, J. M., Authoritative sources in a hyperlinked environment, J. ACM, 46, 5, 604-632, (1999) · Zbl 1065.68660 |
| [68] | Koyutürk, M.; Kim, Y.; Topkara, U.; Subramaniam, S.; Szpankowski, W.; Grama, A., Pairwise alignment of protein interaction networks, J. Comput. Biol., 13, 2, 182-199, (2006) |
| [69] | Kuchaiev, O.; Milenković, T.; Memišević, V.; Hayes, W.; Pržulj, N., Topological network alignment uncovers biological function and phylogeny, J. R. Soc. Interf., 7, 50, 1341-1354, (2010) |
| [70] | Levenstein, V. I., Binary codes capable of correcting deletions, insertions, and reversals, Sov. Phys.—Doklady, 10, 8, 707-710, (1966) · Zbl 0149.15905 |
| [71] | Maggiora, G. M.; Shanmugasundaram, V., Molecular similarity measures, Chemoinformatics: Concepts, Methods, and Tools for Drug Discovery, 1-50, (2004), Humana Press Totowa, NJ, USA |
| [72] | Mehler, A.; Dehmer, M.; Gleim, R., Towards logical hypertext structure—a graph-theoretic perspective, (Böhme, T.; Heyer, G., Proceedings of the Fourth International Workshop on Innovative Internet Computing Systems (I2CS ’04), Lecture Notes in Computer Science, 3473, (2004), Springer Berlin/New York), 136-150 |
| [73] | Mehler, A.; Weiß, P.; Lücking, A., A network model of interpersonal alignment, Entropy, 12, 6, 1440-1483, (2010) |
| [74] | Melnik, S.; Garcia-Molina, H.; Rahm, A., Similarity flooding: a versatile graph matching algorithm and its application to schema matching, Proceedings of the 18th International Conference on Data Engineering, 117-128, (2002), San Jose, USA |
| [75] | Minas, C.; Montana, G., Distance-based analysis of variance: approximate inference, Stat. Anal. Data Mining, 7, 6, 450-470, (2014) · Zbl 07260417 |
| [76] | Müller, L. A.J.; Kugler, K. G.; Graber, A.; Dehmer, M., A network-based approach to classify the three domains of life, Biol. Direct, 6, 140-141, (2011) |
| [77] | Nagl, M., Graph-Grammatiken: Theorie, Anwendungen, Implementierung, (1979), Vieweg · Zbl 0517.68069 |
| [78] | Newman, M. E.J.; Barabási, A. L.; Watts, D. J., The Structure and Dynamics of Networks, Princeton Studies in Complexity, (2006), Princeton University Press · Zbl 1362.00042 |
| [79] | Neyshabur, B.; Khadem, A.; Hashemifar, S.; Arab, S. S., NETAL: a new graph-based method for global alignment of protein-protein interaction networks, Bioinformatics, (2013) |
| [80] | Patro, R.; Kingsford, C., Global network alignment using multiscale spectral signatures, Bioinformatics, 28, 23, 3105-3114, (2012) |
| [81] | Phan, H. T.T.; Sternberg, M. J.E., Pinalog: a novel approach to align protein interaction networks implications for complex detection and function prediction, Bioinformatics, 28, 9, 1239-1245, (2012) |
| [82] | Pržulj, N., Network comparison using graphlet degree distribution, Bioinformatics, 23, e177-e183, (2007) |
| [83] | Radu, A.; Charleston, M., Node fingerprinting: an efficient heuristic for aligning biological networks, J. Comput. Biol., 21, 10, 760-770, (2014) |
| [84] | Rahmatallah, Y.; Emmert-Streib, F.; Glazko, G., Gene set analysis for self-contained tests: complex null and specific alternative hypotheses, Bioinformatics, 28, 23, 3073-3080, (2012) |
| [85] | Rahmatallah, Y.; Emmert-Streib, F.; Glazko, G., Gene sets net correlations analysis (GSNCA): a multivariate differential coexpression test for gene sets, Bioinformatics, 30, 3, 360-368, (2014) |
| [86] | Randić, M., Design of molecules with desired properties. molecular similarity approach to property optimization, (Johnson, M. A.; Maggiora, G., Concepts and Applications of Molecular Similarity, (1990), Wiley), 77-145 |
| [87] | Randić, M.; Wilkins, C. L., Graph theoretical approach to recognition of structural similarity in molecules, J. Chem. Inf. Comput. Sci., 19, 31-37, (1979) |
| [88] | Rito, T.; Wang, Z.; Deane, C. M.; Reinert, G., How threshold behaviour affects the use of subgraphs for network comparison, Bioinformatics, 26, 18, i611-i617, (2010) |
| [89] | Robles-Kelly, A.; Hancock, R., Edit distance from graph spectra, Proceedings of the IEEE International Conference on Computer Vision, 234-241, (2003) |
| [90] | Robles-Kelly, A.; Hancock, R., String edit distance, random walks and graph matching, Int. J. Pattern Recognit. Artif. Intell., 18, 3, 315-327, (2004) |
| [91] | Robles-Kelly, A.; Hancock, R., Graph edit distance from spectral seriation, IEEE Trans. Pattern Anal. Mach. Intell., 27, 3, 365-378, (2005) |
| [92] | Salomaa, A., Formal Languages, (1973), Academic Press · Zbl 0262.68025 |
| [93] | Sankoff, D.; Kruskal, J. B.; Mainville, S.; Cedergren, R. J., Fast algorithms to determine RNA secondary structures containing multiple loops, (Sankoff, D.; Kruskal, J., Time Warps, String Edits and Macromolecules: The Theory and Practice of Sequence Comparison, (1983), Addison-Wesley), 93-120 |
| [94] | Santini, S.; Jain, R., Similarity measures, IEEE Trans. Pattern Anal. Mach. Intell., 21, 9, 871-883, (1999) |
| [95] | Saraph, V.; Milenkovi, T., MAGNA: maximizing accuracy in global network alignment, Bioinformatics, (2014) |
| [96] | Schädler, C.; Wysotzki, F., A connectionist approach to structural similarity determination as a basis of clustering, classification and feature detection, (Komorowski, J.; Zytkow, J., Principles of Data Mining and Knowledge Discovery. Proceedings of the First European Symposium on the Principles of Data Mining and Knowledge Discovery, (1997), Trondheim, Norway), 254-264 |
| [97] | Selkow, S. M., The tree-to-tree editing problem, Inf. Process. Lett., 6, 6, 184-186, (1977) · Zbl 0391.68022 |
| [98] | Shams, L. B.; Brady, M. J.; Schaal, S., Graph matching vs mutual information maximization for object detection, Neural Netw., 14, 3, 345-354, (2001) |
| [99] | Sharan, R.; Ideker, T., Modeling cellular machinery through biological network comparison., Nat. Biotechnol., 24, 4, 427-433, (2006) |
| [100] | Skvortsova, M. I.; Baskin, I. I.; Stankevich, I. V.; Palyulin, V. A.; Zefirov, N. S., Molecular similarity. 1. analytical description of the set of graph similarity measures, J. Chem. Inf. Comput. Sci., 38, 785-790, (1998) |
| [101] | Sobik, F., Graphmetriken und klassifikation strukturierter objekte, ZKI-Inform. Akad. Wiss. DDR, 2, 82, 63-122, (1982) · Zbl 0496.05059 |
| [102] | Sobik, F., Modellierung von vergleichsprozessen auf der grundlage von ähnlichkeitsmaßen für graphen, ZKI-Inform. Akad. Wiss. DDR, 4, 104-144, (1986) · Zbl 0637.92021 |
| [103] | Sokolsky, O.; Kannan, S.; Lee, I., Simulation-based graph similarity, TACAS, LNCS, 426-440, (2006), Springer · Zbl 1180.68198 |
| [104] | Sommerfeld, E., Systematization and formalization of cognitive structure transformations on the basis of graph transformations, (Marek, T., Action and Performance: Models and Tests. Contributions to the Quantitative Psychology and Its Methodology, (1990)), 105-120 |
| [105] | Sommerfeld, E., Kognitive Strukturen. Mathematisch-psychologische Elementaranalysen der Wissensstrukturierung und Informationsverarbeitung, (1994), Waxmann Publishing |
| [106] | Sommerfeld, E.; Sobik, F., Operations on cognitive structures—their modeling on the basis of graph theory, (Albert, D., Knowledge Structures, (1994), Springer), 146-190 |
| [107] | Stelzl, U.; Worm, U.; Lalowski, M.; Haenig, C.; Brembeck, F.; Goehler, H.; Stroedicke, M.; Zenkner, M.; Schoenherr, A.; Koeppen, S.; Timm, J.; Mintzlaff, S.; Abraham, C.; Bock, N.; Kietzmann, S.; Goedde, A.; Toksz, E.; Droege, A.; Krobitsch, S.; Korn, B.; Birchmeier, W.; Lehrach, H.; Wanker, E., A human protein-protein interaction network: a resource for annotating the proteome, Cell, 122, 6, 957-968, (2005) |
| [108] | Sussenguth, E. H., Structural Matching in Information Processing, (1964), Harvard University, USA, Ph.D. thesis · Zbl 0156.18201 |
| [109] | Tai, K. C., The tree-to-tree correction problem, J. ACM, 26, 3, 422-433, (1979) · Zbl 0409.68040 |
| [110] | Theoharatos, C.; Laskaris, N.; Economou, G.; Fotopoulos, S., A similarity measure for color image retrieval and indexing based on the multivariate two sample problem, Proceedings of EUSIPCO, Vienna, Austria, 2307-2310, (2004) |
| [111] | Theoharatos, C.; Pothos, V. K.; Laskaris, N. A.; Economou, G.; Fotopoulos, S., Multivariate image similarity in the compressed domain using statistical graph matching, Pattern Recognit., 39, 10, 1892-1904, (2006) · Zbl 1096.68734 |
| [112] | Tian, Y.; Zhang, B.; Hoffman, E. P.; Clarke, R.; Zhang, Z.; Shih, I.-M.; Xuan, J.; Herrington, D. M.; Wang, Y., Knowledge-fused differential dependency network models for detecting significant rewiring in biological networks, BMC Syst. Biol., 8, 1, 87, (2014) |
| [113] | Toda, S., Graph isomorphism: its complexity and algorithms (abstract), (Rangan, C. P.; Raman, V.; Ramanujam, R., FSTTCS, Foundations of Software Technology and Theoretical Computer Science, 19th Conference, Chennai, India, December 13-15, 1999, Proceedings, Lecture Notes in Computer Science, 1738, (1999), Springer), 341 |
| [114] | Todeschini, R.; Consonni, V., Handbook of Molecular Descriptors, (2002), Wiley-VCH Weinheim, Germany |
| [115] | Tversky, A., Features of similarity, Psychol. Rev., 84, 327-352, (1977) |
| [116] | Ullmann, J. R., An algorithm for subgraph isomorphism, J. ACM, 23, 1, 31-42, (1976) · Zbl 0323.05138 |
| [117] | Varmuza, K.; Scsibrany, H., Substructure isomorphism matrix, J. Chem. Inf. Comput. Sci., 40, 308-313, (2000) |
| [118] | Varmuza, K.; Demuth, W.; Karlovits, M.; Scsibrany, H., Binary substructure descriptors for organic compounds, Croat. Chem. Acta, 78, 141-149, (2005) |
| [119] | Varmuza, K.; Filzmoser, P.; Liebmann, B., Random projection experiments with chemometric data, J. Chemom., 24, 209-217, (2010) |
| [120] | Vizing, V. G., Some unsolved problems in graph theory, Uspehi Mat. Naukno., 23, 117-134, (1968) · Zbl 0177.52301 |
| [121] | Wang, Y.-C.; Lan, C.-Y.; Hsieh, W.-P.; Murillo, L.; Agabian, N.; Chen, B.-S., Global screening of potential candida albicansbiofilm-related transcription factors via network comparison, BMC Bioinform., 11, 1, 53, (2010) |
| [122] | Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442, (1998) · Zbl 1368.05139 |
| [123] | Willet, P., Similarity and Clustering in Chemical Information Systems, (1987), Research Studies Press Letchworth, United Kingdom |
| [124] | Zager, L. A.; Verghese, G. C., Graph similarity scoring and matching, Appl. Math. Lett., 21, 86-94, (2008) · Zbl 1131.05091 |
| [125] | Zelinka, B., On a certain distance between isomorphism classes of graphs, Časopis pro p̆est. Math., 100, 371-373, (1975) · Zbl 0312.05121 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
