Graph measures with high discrimination power revisited: a random polynomial approach. (English) Zbl 1450.62060
Summary: Finding graph measures with high discrimination power has been triggered by searching for so-called complete graph invariants. In a series of papers, we have already investigated highly discriminating measures to distinguish graphs (networks) based on their topology. In this paper, we propose an approach where the graph measures are based on the roots of random graph polynomials. The polynomial coefficients have been defined by utilizing information functionals which capture structural information of the underlying networks. Our numerical results obtained by employing exhaustively generated graphs reveal that the new approach outperforms earlier results in the literature.
MSC:
| 62H22 | Probabilistic graphical models |
| 62R07 | Statistical aspects of big data and data science |
| 05C75 | Structural characterization of families of graphs |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 90B10 | Deterministic network models in operations research |
References:
| [1] | Balaban, A. T., Highly discriminating distance-based topological index, Chem. Phys. Lett., 89, 399-404 (1982) |
| [2] | 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) |
| [3] | Balaban, A. T.; Harary, F., The characteristic polynomial does not uniquely determine the topology of a molecule, J. Chem. Doc., 11, 258-259 (1971) |
| [4] | Bonchev, D.; Mekenyan, O.; Trinajstić, N., Isomer discrimination by topological information approach, J. Comp. Chem., 2, 2, 127-148 (1981) |
| [5] | Brešar, B.; Klavžar, S.; Škrekovski, R., Roots of cube polynomials of median graphs, J. Graph Theory, 52, 37-50 (2006) · Zbl 1117.05105 |
| [6] | Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs. Theory and Application (1980), Deutscher Verlag der Wissenschaften · Zbl 0458.05042 |
| [7] | Dehmer, M., Information processing in complex networks: graph entropy and information functionals, Appl. Math. Comput., 201, 82-94 (2008) · Zbl 1152.05361 |
| [8] | Dehmer, M.; Emmert-Streib, F.; Grabner, M., A computational approach to construct a multivariate complete graph invariant, Inf. Sci., 260, 200-208 (2014) · Zbl 1329.05279 |
| [9] | Dehmer, M.; Emmert-Streib, F.; Hu, B.; Shi, Y.; Stefu, M.; Tripathi, S., Highly unique network descriptors based on the roots of the permanental polynomial, Inf. Sci., 408, 176-181 (2017) · Zbl 1429.68186 |
| [10] | 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 |
| [11] | Dehmer, M.; Grabner, M.; Mowshowitz, A.; Emmert-Streib, F., An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants, Adv. Comput. Math., 39, 311-325 (2012) · Zbl 1270.05071 |
| [12] | Dehmer, M.; Grabner, M.; Varmuza, K., Information indices with high discriminative power for graphs, PLoS ONE, 7, e31214 (2012) |
| [13] | Dehmer, M.; Ilić, A., Location of zeros of wiener and distance polynomials, PLoS ONE, 7, e28328 (2012) |
| [14] | Dehmer, M.; Moosbrugger, M.; Shi, Y., Encoding structural information uniquely with polynomial-based descriptors by employing the randić matrix, Appl. Math. Comput. accepted, 268, 164-168 (2015) · Zbl 1410.05093 |
| [15] | Dehmer, M.; Mowshowitz, A., A history of graph entropy measures, Inf. Sci., 1, 57-78 (2011) · Zbl 1204.94050 |
| [16] | Dehmer, M.; Müller, L.; Graber, A., New polynomial-based molecular descriptors with low degeneracy, PLoS ONE, 5, 7 (2010) |
| [17] | Dehmer, M.; Shi, Y.; Emmert-Streib, F., Structural differentiation of graphs using hosoya-based indices, PLoS ONE, 9, e102459 (2014) |
| [18] | Dehmer, M.; Shi, Y.; Mowshowitz, A., Discrimination power of graph measures based on complex zeros of the partial hosoya polynomial, Appl. Math. Comput., 250, 352-355 (2015) · Zbl 1328.05095 |
| [19] | Dong, F. M.; Koh, K. M.; Teo, K. L., Chromatic Polynomials and Chromaticity of Graphs (2005), World Scientific Publishing Company: World Scientific Publishing Company New Jersey, NJ, USA · Zbl 1070.05038 |
| [20] | Ellis-Monaghan, J. A.; Merino, C., Graph polynomials and their applications i: The tutte polynomial, (Dehmer, M., Structural Analysis of Complex Networks (2010), Birkhäuser: Birkhäuser Boston/Basel), 219-255 · Zbl 1221.05002 |
| [21] | Erdös, P.; Offord, A. C., On the number of real roots of a random algebraic equation, Proc. London Math. Soc., s3-6, 1, 139-160 (1956) · Zbl 0070.01702 |
| [22] | Erdös, P.; Turan, P., On the distribution of roots of polynomials, Ann. Math., 51, 1, 105-119 (1950) · Zbl 0036.01501 |
| [23] | Gutman, I., Polynomials in graph theory, (Bonchev, D.; Rouvray, D. H., Chemical Graph Theory. Introduction and Fundamentals (1991), Abacus Press: Abacus Press New York, NY, USA), 133-176 · Zbl 0746.05063 |
| [24] | Hosoya, H., On some counting polynomials, Discrete Appl. Math., 19, 239-257 (1988) · Zbl 0633.05006 |
| [25] | Householder, A. S., The Numerical Treatment of a single Nonlinear Equation (1970), McGraw-Hill: McGraw-Hill New York, NY, USA · Zbl 0242.65047 |
| [26] | Hu, C. Y.; Xu, L., On highly discriminating molecular topological index, J. Chem. Inf. Comput. Sci., 36, 82-90 (1996) |
| [27] | Jackson, B., Zeros of chromatic and flow polynomials of graphs, J. Geometry, 76, 95-109 (2003) · Zbl 1021.05033 |
| [28] | Janežić, D.; Miležević, A.; Nikolić, S.; Trinajstić, N., Graph-theoretical matrices in chemistry, Mathematical Chemistry Monographs. University of Kragujevac and Faculty of Science Kragujevac (2007) · Zbl 1293.92001 |
| [29] | Jenkins, M. A.; Traub, J. F., Algorithm 419: Zeros of a complex polynomial [c2], Commun. ACM, 15, 2, 97-99 (1972) |
| [30] | Konstantinova, E. V., The discrimination ability of some topological and information distance indices for graphs of unbranched hexagonal systems, J. Chem. Inf. Comput. Sci., 36, 54-57 (1996) |
| [31] | 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, Lecture Notes of Computer Science (2006), Springer), 831-852 · Zbl 1158.94337 |
| [32] | Konstantinova, E. V.; Paleev, A. A., Sensitivity of topological indices of polycyclic graphs, Vychisl. Sistemy, 136, 38-48 (1990) · Zbl 0769.05068 |
| [33] | Křivka, P.; Trinajstić, N., On the distance polynomial of a graph, Appl. Math., 28, 357-363 (1983) · Zbl 0529.05037 |
| [34] | Li, X.; Shi, Y.; Gutman, I., Graph Energy (2012), Springer: Springer New York · Zbl 1262.05100 |
| [35] | Littlewood, J.; Offord, A., On the number of real roots of a random algebraic equation, J. London Math. Soc., 13, 288-295 (1938) · JFM 64.0952.04 |
| [36] | Liu, X.; Klein, D. J., The graph isomorphism problem, J. Comput. Chem., 12, 10, 1243-1251 (1991) |
| [37] | B.D. McKay, Nauty, 2010, http://cs.anu.edu.au/ bdm/nauty/; B.D. McKay, Nauty, 2010, http://cs.anu.edu.au/ bdm/nauty/ |
| [38] | Mignotte, M.; Stefanescu, D., Polynomials: An algorithmic approach, Discrete Mathematics and Theoretical Computer Science (1999), Springer: Springer Singapore · Zbl 0927.12004 |
| [39] | Müller, L. A.J.; Kugler, K. G.; Dander, A.; Graber, A.; Dehmer, M., QuACN - an r package for analyzing complex biological networks quantitatively, Bioinformatics, 27, 1, 140-141 (2011) |
| [40] | L.A.J. Müller, M. Schutte, K.G. Kugler, M. Dehmer, QuACN: Quantitative analyze of complex networks, 2012, R Package Version 1.6.; L.A.J. Müller, M. Schutte, K.G. Kugler, M. Dehmer, QuACN: Quantitative analyze of complex networks, 2012, R Package Version 1.6. |
| [41] | Pritsker, I. E.; Yeager, A. M., Zeros of polynomials with random coefficients, J. Approx. Theory, 189, C, 88-100 (2015) · Zbl 1309.26016 |
| [42] | Team, R. C., R: A language and environment for statistical computing, R Found. Stat. Comput. (2016) |
| [43] | Randić, M., On molecular identification numbers, J. Chem. Inf. Comput. Sci., 24, 3, 164-175 (1984) |
| [44] | Randić, M.; Vracko, M.; Novic, M., Eigenvalues as molecular descriptors, (Diudea, M. V., QSPR/QSAR Studies by Molecular Descriptors (2001), Nova Publishing: Nova Publishing Huntington, NY, USA), 93-120 |
| [45] | Shi, Y.; Dehmer, M.; Li, X.; Gutman, I., Graph Polynomials (2017), Wiley-VCH · Zbl 1362.05003 |
| [46] | Skiena, S., Graph isomorphism, (Pemmaraju, S.; Skiena, S., Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica (1990), Addison-Wesley: Addison-Wesley Reading, MA, USA), 181-187 · Zbl 0786.05004 |
| [47] | 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) |
| [48] | Talanova, E. A., The global graph as a complete topological invariant in the class of diffeomorphisms on \(M^3\), Trudy Srednevolzhskogo Matematicheskogo Obshchestva, 11, 199-208 (2009) · Zbl 1240.37020 |
| [49] | Todeschini, R.; Consonni, V., Handbook of Molecular Descriptors (2002), Wiley-VCH: Wiley-VCH Weinheim, Germany |
| [50] | Wu, T.; Zhang, H.; Li, W.; Liu, S., On the permanental polynomials of graphs, (Gutmann, I.; Li, X.; Shi, Y.; Dehmer, M., Graph Polynomials (2017), CRC) |
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.
