×

Large-scale analysis of structural branching measures. (English) Zbl 1296.92246

Summary: Structural branching of graphs has been investigated extensively. Yet, no method/model has yet been developed which captures all aspects of branching meaningfully. Another shortcoming of nearly all related work in this area is the fact that only small sets of example graphs have been used to perform those studies. Instead, we investigate structural branching of graphs statistically by using large sets of exhaustively generated graphs. Our findings explain some of the limits of existing branching measures as well as the search for novel branching measures by using correlation analysis.

MSC:

92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)

Software:

QuACN; Python; NetworkX
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Balaban, Highly discriminating distance-based topological index. Chem. Phys. Lett. 89, 399-404 (1982) · doi:10.1016/0009-2614(82)80009-2
[2] S. Bertz, Branching in graphs and molecules. Discret. Appl. Math. 19, 65-83 (1988) · Zbl 0633.05063 · doi:10.1016/0166-218X(88)90006-6
[3] T. Beyer, S. Hedetniemi, Constant time generation of rooted trees. SIAM J. Comput. 9, 706-712 (1980) · Zbl 0453.05020 · doi:10.1137/0209055
[4] D. Bonchev, Information Theoretic Indices for Characterization of Chemical Structures (Research Studies Press, Chichester, 1983)
[5] D. Bonchev, D.H. Rouvray, Complexity in Chemistry, Biology, and Ecology. Mathematical and Computational Chemistry (Springer, New York, 2005) · Zbl 1109.92300 · doi:10.1007/b136300
[6] D. Bonchev, Topological order in molecules 1. Molecular branching revisited. J. Mol. Struct. (Theochem) 336, 137-156 (1995) · doi:10.1016/0166-1280(94)04081-3
[7] D. Bonchev, E. Markel, A. Dekmezian, Topological analysis of long-chain branching patterns in polyolefins. J. Chem. Inf. Comput. Sci. 51(5), 1274-1285 (2001) · doi:10.1021/ci010021s
[8] D. Bonchev, N. Trinajstic, Information theory, distance matrix, and molecular branching. J. Chem. Phys. 67(10), 4517-4533 (1977) · doi:10.1063/1.434593
[9] D. Bonchev, N. Trinajstic, On topological characterization of molecular branching. Int. J. Quant. Chem. 12, 293-303 (1978)
[10] G. Chartrand, Introductory Graph Theory (Dover, New York, NY, 1985)
[11] J. Claussen, Offdiagonal complexity: a computationally quick complexity measure for graphs and networks. Phys. Stat. Mech. Appl. 375(1), 365-373 (2007) · doi:10.1016/j.physa.2006.08.067
[12] M. Dehmer, Information processing in complex networks: graph entropy and information functionals. J. Appl. Math. Comput. 201, 82-94 (2008) · Zbl 1152.05361 · doi:10.1016/j.amc.2007.12.010
[13] M. Dehmer (ed.), Structural Analysis of Complex Networks (Birkhäuser, Cambridge, 2010)
[14] M. Dehmer, Information theory of networks. Symmetry 3, 767-779 (2012) · Zbl 1360.94150 · doi:10.3390/sym3040767
[15] M. Dehmer, F. Emmert-Streib, T. Gesell, A comparative analysis of multidimensional features of objects resembling sets of graphs. Appl. Math. Comput. 196, 221-235 (2008) · Zbl 1245.05093 · doi:10.1016/j.amc.2007.05.058
[16] Dehmer, M.; Emmert-Streib, F.; Tsoy, Y.; Varmuza, K.; Putz, M. (ed.), Quantifying structural complexity of graphs: information measures in mathematical chemistry, 479-498 (2011), New York, NY
[17] M. Dehmer, L. Sivakumar, K. Varmuza, Uniquely discriminating molecular structures using eigenvalue-based descriptors. Match Commun. Math. Comput. Chem. 67(1), 147-172 (2012)
[18] F. Emmert-Streib, M. Dehmer, Networks for systems biology: conceptual connection of data and function. IET Syst. Biol. 5, 185-207 (2011) · doi:10.1049/iet-syb.2010.0025
[19] M. Fischermann, I. Gutman, A. Hoffmann, D. Rautenbach, D. Vidovic, L. Volkmann, Extremal chemical trees. Z. Naturforsch. 57a, 49-52 (2002)
[20] B. Furtula, A. Graovac, D. Vukicevic, Augmented Zagreb index. J. Math. Chem. 48(2), 370-380 (2010) · Zbl 1196.92050 · doi:10.1007/s10910-010-9677-3
[21] I. Gutman, The energy of a graph. Ber. Math. Statist. Sekt. Forsch. Graz 103, 1-22 (1978)
[22] I. Gutman, B. Furtula, M. Ivanovic, Notes on trees with minimal atom-bond connectivity index. Match Commun. Math. Comput. Chem. 67, 467-482 (2012) · Zbl 1289.05063
[23] I. Gutman, M. Randic, Algebraic characterization of skeletal branching. Chem. Phys. Lett. 47(1), 15-19 (1977) · doi:10.1016/0009-2614(77)85296-2
[24] I. Gutman, B. Ruščić, T. Trinajstic, C. Wilcox Jr, Graph theory and molecular orbitals. XII. Acyclic polyenes. J. Chem. Phys. 62(9), 3399-3405 (1975) · doi:10.1063/1.430994
[25] I. Gutman, N. Trinajstic, Graph theory and molecular orbitals. total \[\varphi\] φ-electron energy of alternant hydrocarbons. Chem. Phys. Lett. 17(4), 535-538 (1972) · doi:10.1016/0009-2614(72)85099-1
[26] A. Hagberg, D. Schult, P. Swart, Exploring network structure, dynamics and function using NetworkX. In: G. Varoquaux, T. Vaught, J. Millman (eds.) Proceedings of the 7th python in science conference (SciPy2008) (Pasadena, CA, 2008), pp. 11-15 · Zbl 0165.57601
[27] G. Hall, Eigenvalues of molecular graphs. Bull. Inst. Math. Appl. 17, 70-72 (1981)
[28] F. Harary, Graph Theory (Addison-Wesley Publishing Company, Reading, MA, 1969) · Zbl 0182.57702
[29] H. Hosoya, Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons. Bull. Chem. Soc. Jpn. 44, 2332-2339 (1971) · doi:10.1246/bcsj.44.2332
[30] E. Kirby, Sensitivity of topological indices to methyl group branching in octanes and azulenes, or what does a topological index index? J. Chem. Inf. Comput. Sci. 34, 1030-1035 (1994) · doi:10.1021/ci00021a001
[31] V. Kraus, M. Dehmer, F. Emmert-Streib, Probabilistic inequalities for evaluating structural network measures (2013). Submitted for publication · Zbl 1355.05240
[32] V. Kraus, M. Dehmer, M. Schutte, On sphere-regular graphs and the extremality of information-theoretic network measures (2013). Accepted for publication · Zbl 1299.05301
[33] J. Lozán, H. Kausch, Angewandte Statistik für Naturwissenschaftler, 4th edn. (Wissenschaftliche Auswertungen, Hamburg, 2007)
[34] Mehler, A.; Dehmer, M. (ed.); Emmert-Streib, F. (ed.); Mehler, A. (ed.), Social ontologies as generalized nearly acyclic directed graphs: a quantitative graph model of social tagging, 259-319 (2011), Boston/Basel · Zbl 1258.68151 · doi:10.1007/978-0-8176-4904-3_10
[35] L. Müller, K. Kugler, A. Dander, A. Graber, M. Dehmer, QuACN: an R package for analyzing complex biological networks quantitatively. Bioinformatics 27(1), 140-141 (2011). http://cran.r-project.org/web/packages/QuACN/
[36] A. Mowshowitz, Entropy and the complexity of graphs: I. An index of the relative complexity of a graph. Bull. Math. Biophys. 30(1), 175-204 (1968) · Zbl 0165.57601 · doi:10.1007/BF02476948
[37] S. Nikolic, G. Kovacevic, A. Milicevic, N. Trinajstic, The Zagreb indices 30 years after. Croat. Chem. Acta 76(2), 113-124 (2003)
[38] T. Oliphant, Python for scientific computing. Comput. Sci. Eng. 90, 9 (2007)
[39] A. Perdih, M. Perdih, On topological indices indicating branching Part I. The principal component analysis of alkane properties and indices. Acta Chim. Slov. 47, 231-259 (2000)
[40] M. Randic, On characterization of molecular branching. J. Am. Chem. Soc. 97(23), 6609-6615 (1975) · Zbl 0770.60091 · doi:10.1021/ja00856a001
[41] H. Schultz, E. Schultz, T. Schultz, Topological organic chemistry. 4. Graph theory, matrix permanents, and topological indices of alkanes. J. Chem. Inf. Comput. Sci. 32(1), 69-72 (1992) · doi:10.1021/ci00005a011
[42] R. Taylor, Interpretation of the correlation coefficient: a basic review. J. Diagn. Med. Sonogr. 1, 35-39 (1990) · doi:10.1177/875647939000600106
[43] R. Todeschini, V. Consonni, Molecular Descriptors for Chemoinformatics, Second, Revised and Enlarged edn. Methods and Principles in Medicinal Chemistry (Wiley, Weinheim, 2009)
[44] H. Wiener, Structural determination of paraffin boiling points. J. Am. Chem. Soc. 1(69), 17-20 (1947) · doi:10.1021/ja01193a005
[45] R. Wright, B. Richmond, A. Odlyzko, B. McKay, Constant time generation of free trees. SIAM J. Comput. 15, 540-548 (1986) · Zbl 0616.68063 · doi:10.1137/0215039
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.