A computational approach to construct a multivariate complete graph invariant. (English) Zbl 1329.05279
Summary: In this paper, we present a computational approach for finding complete graph invariants. Specifically, we generate exhaustive sets of connected, non-isomorphic graphs with 9 and 10 vertices and demonstrate that a 97-dimensional multivariate graph invariant is capable to distinguish each of the non-isomorphic graphs. Furthermore, in order to tame the computational complexity of the problem caused by the vast number of graphs, e.g., involving over 10 million networks with 10 vertices, we suggest a low-dimensional, iterative procedure that is based on highly discriminative individual graph invariants. We show that also this computational approach leads to a perfect discrimination. Overall, our numerical results prove the existence of such graph invariants for networks with 9 and 10 vertices. Furthermore, we show that our iterative approach has a polynomial time complexity.
MSC:
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Abdulrahim, M.; Misra, M., A graph isomorphism algorithm for object recognition, Pattern Anal. Appl., 1, 189-201 (1998) · Zbl 0911.68182 |
| [2] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley · Zbl 0326.68005 |
| [3] | Arvind, V.; Das, B.; Köbler, J., The space complexity of k-tree isomorphism, (Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC). Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC), LNCS, 4835 (2007), Springer), 822-833 · Zbl 1193.68124 |
| [4] | Arvind, V.; Das, B.; Köbler, J., A logspace algorithm for partial 2-tree canonization, (Proceedings of the 3rd International Computer Science Symposium in Russia (CSR). Proceedings of the 3rd International Computer Science Symposium in Russia (CSR), LNCS, 5010 (2008), Springer), 40-51 · Zbl 1142.68368 |
| [5] | Babai, L.; Luks, E. M., Canonical labeling of graphs. Canonical labeling of graphs, In STOC’83: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (1983), ACM Press: ACM Press NY, USA |
| [6] | Balaban, A. T., Highly discriminating distance-based topological index, Chem. Phys. Lett., 89, 399-404 (1982) |
| [7] | Balaban, A. T.; Balaban, T. S., New vertex invariants and topological indices of chemical graphs based on information on distances, J. Math. Chem., 8, 383-397 (1991) |
| [8] | Balaban, A. T.; Harary, F., The characteristic polynomial does not uniquely determine the topology of a molecule, J. Chem. Document., 11, 258-259 (1971) |
| [9] | Basak, S. C., Information-theoretic indices of neighborhood complexity and their applications, (Devillers, J.; Balaban, A. T., Topological Indices and Related Descriptors in QSAR and QSPAR (1999), Gordon and Breach Science Publishers: Gordon and Breach Science Publishers Amsterdam, The Netherlands), 563-595 |
| [10] | Basak, S. C.; Magnuson, V. R., Molecular topology and narcosis, Arzeim.-Forsch./Drug Des., 33, I, 501-503 (1983) |
| [11] | Bonchev, D., Information Theoretic Indices for Characterization of Chemical Structures (1983), Research Studies Press: Research Studies Press Chichester |
| [12] | Bonchev, D.; Mekenyan, O.; Trinajstić, N., Isomer discrimination by topological information approach, J. Comput. Chem., 2, 2, 127-148 (1981) |
| [14] | Conte, D.; Foggia, F.; Sansone, C.; Vento, M., Thirty years of graph matching in pattern recognition, Int. J. Pattern Recog. Artif. Intell., 18, 265-298 (2004) |
| [15] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), MIT Press · Zbl 1158.68538 |
| [16] | Corneil, D. G.; Gotlieb, C. C., An efficient algorithm for graph isomorphism, J. ACM, 17, 51-64 (1970) · Zbl 0199.27801 |
| [17] | Costa, L.daF.; Rodrigues, F.; Travieso, G., Characterization of complex networks: a survey of measurements, Adv. Phys., 56, 167-242 (2007) |
| [18] | (Dehmer, M., Structural Analysis of Complex Networks (2010), Birkhäuser Publishing) · Zbl 1201.05002 |
| [19] | Dehmer, M.; Emmert-Streib, F.; Tsoy, Y.; Varmuza, K., Quantifying structural complexity of graphs: information measures in mathematical chemistry, (Putz, M., Quantum Frontiers of Atoms and Molecules (2011), Nova Publishing), 479-498 |
| [20] | Dehmer, M.; Grabner, M.; Furtula, B., Structural discrimination of networks by using distance, degree and eigenvalue-based measures, PLoS ONE, 7, e38564 (2012) |
| [21] | Dehmer, M.; Grabner, M.; Varmuza, K., Information indices with high discriminative power for graphs, PLoS ONE, 7, e31214 (2012) |
| [22] | Dehmer, M.; Kraus, V., On extremal properties of graph entropies, MATCH Commun. Math. Comput. Chem., 68, 889-912 (2012) · Zbl 1289.05228 |
| [23] | Dehmer, M.; Mowshowitz, A., A history of graph entropy measures, Inform. Sci., 1, 57-78 (2011) · Zbl 1204.94050 |
| [24] | Devillers, J.; Balaban, A. T., Topological Indices and Related Descriptors in QSAR and QSPR (1999), Gordon and Breach Science Publishers: Gordon and Breach Science Publishers Amsterdam, The Netherlands |
| [25] | Diudea, M. V.; Gutman, I.; Jäntschi, L., Molecular Topology (2001), Nova Publishing: Nova Publishing New York, NY, USA |
| [26] | Faulon, J. L., Isomorphism, automorphism partitioning, and canonical labeling can be solved in polynomial-time for molecular graphs, J. Chem. Inform. Comput. Sci., 38, 3, 432-444 (1998) |
| [27] | Gutman, I.; Li, X.; Zhang, J., Graph energy, (Dehmer, M.; Emmert-Streib, F., Analysis of Complex Networks: From Biology to Linguistics (2009), Wiley-VCH), 145-174 · Zbl 1256.05140 |
| [28] | Halin, R., Graphentheorie (1989), Akademie Verlag: Akademie Verlag Berlin, Germany · Zbl 0684.05015 |
| [29] | Hall, N. R.; Preiser, S., Combined network complexity measures, IBM J. Res. Develop., 28, 15-27 (1984) |
| [30] | Harary, F., Graph Theory (1969), Addison Wesley Publishing Company: Addison Wesley Publishing Company Reading, MA, USA · Zbl 0182.57702 |
| [31] | Ihlenfeldt, W.-D.; Gasteiger, J., Hash codes for the indentification and classification of molecular structure elements, J. Comput. Chem., 15, 8, 793-813 (1994) |
| [33] | Junttila, T.; Kaski, P., Engineering an efficient canonical labeling tool for large and sparse graphs, (Applegate, D.; Stolting Brodat, G.; Panario, D.; Sedgewick, R., Proceedings of the Ninth Workshop on Algorithm Engineering and Experiments and the Fourth Workshop on Analytic Algorithms and Combinatorics (2007), SIAM) · Zbl 1428.68222 |
| [34] | Konstantinova, E. V., The discrimination ability of some topological and information distance indices for graphs of unbranched hexagonal systems, J. Chem. Inform. Comput. Sci., 36, 54-57 (1996) |
| [35] | Konstantinova, E. V., On some applications of information indices in chemical graph theory, (Ahlswede, R.; Bäumer, L.; Cai, N.; Aydinian, H.; Blinovsky, V.; Deppe, C.; Mashurian, H., General Theory of Information Transfer and Combinatorics. General Theory of Information Transfer and Combinatorics, Lecture Notes of Computer Science (2006), Springer), 831-852 · Zbl 1158.94337 |
| [36] | Konstantinova, E. V.; Paleev, A. A., Sensitivity of topological indices of polycyclic graphs, Vychisl. Sistemy, 136, 38-48 (1990), (in Russian) · Zbl 0769.05068 |
| [37] | Li, F.; Shang, H.; Woo, P. Y., Determination of isomorphism and its applications for arbitrary graphs based on circuit simulation, Circuits Syst. Signal Process., 27, 5, 749-761 (2008) · Zbl 1173.94472 |
| [38] | Liu, J.; Liu, B., A laplacian-energy-like invariant of a graph, MATCH Commun. Math. Comput. Chem., 2, 355-372 (2008) · Zbl 1164.05044 |
| [39] | Liu, X.; Klein, D. J., The graph isomorphism problem, J. Comput. Chem., 12, 10, 1243-1251 (1991) |
| [40] | Luks, E. M., Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comput. Syst. Sci., 25, 42-49 (1982) · Zbl 0493.68064 |
| [41] | McKay, B. D., Graph isomorphisms, Congr. Numer., 730, 45-87 (1981) |
| [43] | Mehler, A.; Weiß, P.; Lücking, A., A network model of interpersonal alignment, Entropy, 12, 6, 1440-1483 (2010) |
| [44] | Mowshowitz, A., Entropy and the complexity of the graphs I: an index of the relative complexity of a graph, Bull. Math. Biophys., 30, 175-204 (1968) · Zbl 0165.57601 |
| [46] | Noy, M., Graphs determined by polynomial invariants, Theor. Comput. Sci., 307, 2, 365-384 (2003) · Zbl 1048.05072 |
| [48] | Raychaudhury, C.; Ray, S. K.; Ghosh, J. J.; Roy, A. B.; Basak, S. C., Discrimination of isomeric structures using information theoretic topological indices, J. Comput. Chem., 5, 581-588 (1984) |
| [49] | Read, R.; Corneil, D., The graph isomorphism disease, J. Graph Theory, 1, 339-363 (1977) · Zbl 0381.05026 |
| [50] | Sagan, H., Boundary and Eigenvalue Problems in Mathematical Physics (1989), Dover Publications · Zbl 1227.35003 |
| [51] | Skiena, S., Graph isomorphism, (Pemmaraju, S.; Skiena, S., Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica (1990), Reading, Addison-Wesley: Reading, Addison-Wesley MA, USA), 181-187 · Zbl 0786.05004 |
| [52] | Spialter, L., The atom connectivity matrix (ACM) and its characteristic polynomial (ACMCP): a new computer-oriented chemical nomenclature, J. Am. Chem. Soc., 85, 2012-2013 (1963) |
| [53] | 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, vol. 1738 (1999), Springer), 341 |
| [54] | Todeschini, R.; Consonni, V.; Mannhold, R., Handbook of Molecular Descriptors (2002), Wiley-VCH: Wiley-VCH Weinheim, Germany |
| [55] | Ulanowicz, R. E., Information theory in ecology, Comput. Chem., 25, 393-399 (2001) |
| [56] | Ulanowicz, R. E., Quantitative methods for ecological network analysis, Comput. Biol. Chem., 28, 321-339 (2004) · Zbl 1088.92061 |
| [57] | Wang, W.; Luo, Y., On laplacian-energy-like invariant of a graph, Linear Algebra Appl., 437, 713-721 (2012) · Zbl 1243.05156 |
| [58] | Wilhelm, T.; Hollunder, J., Information theoretic description of networks, Physica A, 388, 385-396 (2007) |
| [59] | Wu, C. W., On graphs whose laplacian matrix’s multipartite separability is invariant under graph isomorphism, Discr. Mathem., 310, 2811-2814 (2010) · Zbl 1208.05088 |
| [60] | Zemlyachenko, V. N.; Korneenko, N. M.; Tyshkevich, R. I., Graph isomorphism problem, J. Math. Sci., 29, 1426-1481 (1985) · Zbl 0564.05049 |
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.
