Quantitative graph theory: a new branch of graph theory and network science. (English) Zbl 1443.05176
Summary: 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.
MSC:
| 05C99 | Graph theory |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 90B10 | Deterministic network models in operations research |
References:
| [1] | Sonamine. http://www.sonamine.com/home/; Sonamine. http://www.sonamine.com/home/ |
| [2] | R, software, a language and environment for statistical computing. www.r-project.org; R, software, a language and environment for statistical computing. www.r-project.org |
| [3] | Abramov, O.; Lokot, T., Typology by means of language networks. applying information theoretic measures to morphological derivation networks, (Dehmer, M.; Emmert-Streib, F.; Mehler, A., Towards an Information Theory of Complex Networks: Statistical Methods and Applications (2011), Birkhäuser: Birkhäuser Boston/Basel), 321-346 · Zbl 1260.91224 |
| [4] | Alon, N.; Stav, U., The maximum edit distance from hereditary graph properties, J. Combin. Theory Ser-B, 98, 672-697 (2008) · Zbl 1156.05026 |
| [5] | Bavelas, A., A mathematical model for group structure, Human Organizations, 7, 16-30 (1948) |
| [6] | Bavelas, A., Communication patterns in task-oriented groups, J. Acoust. Soc. Amer., 22, 725-730 (1950) |
| [7] | 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 |
| [8] | Bollabás, B., Modern Graph Theory, Graduate Texts in Mathematics (1998), Springer: Springer New York · Zbl 0902.05016 |
| [9] | (Bollobás, B. (1978), Academic Press: Academic Press London) |
| [10] | (Bollobás, B. (2001), Cambridge Univ. Press: Cambridge Univ. Press Cambridge) · Zbl 0979.05003 |
| [11] | Bonchev, D., Information theoretic measures of complexity, (Meyers, R., Encyclopedia of Complexity and System Science, 5 (2009), Springer), 4820-4838 |
| [12] | Borgwardt, M., Graph kernels, Ph.D. thesis (2007), Ludwig-Maximilians-Universität München, Fakultät für Mathematik, Informatik und Statistik |
| [13] | Bunke, H., What is the distance between graphs ?, Bulletin of the EATCS, 20, 35-39 (1983) |
| [14] | Bunke, H., Recent developments in graph matching, 15-th International Conference on Pattern Recognition, 2, 117-124 (2000) |
| [15] | Buttler, D., A short survey of document structure similarity algorithms, International Conference on Internet Computing, 3-9 (2004) |
| [16] | Chakrabarti, S., Mining the Web: Discovering Knowledge from Hypertext Data (2002), Morgan Kaufmann: Morgan Kaufmann San Francisco |
| [17] | Chen, Z.; Dehmer, M.; Emmert-Streib, F.; Shi, Y., Entropy of weighted graphs with Randić weights, Entropy, 17, 3710-3723 (2015) · Zbl 1338.05266 |
| [18] | Chung, F.; Erdös, P.; Spencer, J., Extremal subgraphs for two graphs, J. Combin. Theory Ser-B, 38, 248-260 (1985) · Zbl 0554.05037 |
| [19] | Conte, D.; Foggia, F.; Sansone, C.; Vento, M., Thirty years of graph matching in pattern regocnition, Int. J. Pattern Recognit Artif Intell., 18, 265-298 (2004) |
| [20] | (Dehmer, M., Structural Analysis of Complex Networks (2010), Birkhäuser Publishing) · Zbl 1201.05002 |
| [21] | Dehmer, M.; Emmert-Streib, F., Quantitative Graph Theory. Theory and Applications (2014), CRC Press |
| [22] | Dehmer, M.; Emmert-Streib, F.; Shi, Y., Interrelations of graph distance measures based on topological indices, PLoS ONE, 9, e94985 (2014) |
| [23] | Dehmer, M.; Grabner, M.; Varmuza, K., Information indices with high discriminative power for graphs, PLoS ONE, 7, 2 (2012), . doi:10.1371/journal.pone.0031214 |
| [24] | Dehmer, M.; Kraus, V.; Emmert-Streib, F.; Pickl, S., What is Quantitative Graph Theory ?, 1-33 (2014), CRC Press |
| [25] | Dehmer, M.; Mehler, A., A new method of measuring similarity for a special class of directed graphs, Tatra Mountains Mathematical Publications, 36, 39-59 (2007) · Zbl 1142.05069 |
| [26] | 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) |
| [27] | Dehmer, M.; Mowshowitz, A., Inequalities for entropy-based measures of network information content, Appl. Math. Comput., 215, 4263-4271 (2010) · Zbl 1220.05125 |
| [28] | Dehmer, M.; Mowshowitz, A., A History of Graph Entropy Measures, Inf. Sci., 1, 57-78 (2011) · Zbl 1204.94050 |
| [29] | DeLaVina, E., Some history of the development of graffiti, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 69: Graphs and Discovery, 81-118 (2005) · Zbl 1096.05049 |
| [30] | Devillers, J.; Balaban, A. T., Topological Indices and Related Descriptors in QSAR and QSPR (2000), Gordon and Breach Science Publishers: Gordon and Breach Science Publishers Amsterdam, The Netherlands |
| [31] | Emmert-Streib, F., The chronic fatigue syndrome: A comparative pathway analysis, J. Comput. Biol., 14, 7 (2007) |
| [32] | (Emmert-Streib, F.; Dehmer, M., Analysis of Microarray Data: A Network-based Approach (2010), Wiley VCH Publishing) · Zbl 1193.68188 |
| [33] | 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 |
| [34] | Emmert-Streib, F.; Dehmer, M.; Shi, Y., Fifty years of graph matching, network alignment and comparison, Inform. Sci., 346-347, 180-197 (2016) · Zbl 1398.68393 |
| [35] | Furtula, B.; Gutman, I.; Dehmer, M., On structure-sensitivity of degree-based topological indices, Appl. Math. Comput., 219, 8973-8978 (2013) · Zbl 1308.92029 |
| [36] | Godsil, C.; Royle, G., Algebraic Graph Theory (2001), Springer-Verlag: Springer-Verlag New York · Zbl 0968.05002 |
| [37] | Group F.A.S.. Sentinel visualizer. www.fmsasg.com; Group F.A.S.. Sentinel visualizer. www.fmsasg.com |
| [38] | Harary, F., Status and contrastatus, Sociometry, 22, 23-43 (1959) |
| [39] | Harary, F., Graph Theory (1969), Addison Wesley Publishing Company: Addison Wesley Publishing Company Reading, MA, USA · Zbl 0797.05064 |
| [40] | 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) |
| [41] | Hsieh, S. M.; Hsu, C. C., Graph-based representation for similarity retrieval of symbolic images, Data Knowl. Eng., 65, 3, 401-418 (2008) |
| [42] | Janežić, D.; Miležević, A.; Nikolić, S.; Trinajstić, N., Graph-Theoretical Matrices in Chemistry Mathematical Chemistry Monographs (2007), University of Kragujevac and Faculty of Science Kragujevac · Zbl 1293.92001 |
| [43] | Jiang, T.; Wang, L.; Zhang, K., Alignment of trees - an alternative to tree edit, CPM ’94: Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, 75-86 (1994), Springer-Verlag: Springer-Verlag London, UK |
| [44] | Junker, B. H.; Schreiber, F., Analysis of Biological Networks Wiley Series in Bioinformatics; (2008), Wiley-Interscience |
| [45] | Kaden, F., Graphmetriken und Distanzgraphen, ZKI-Informationen, Akad Wiss DDR, 2, 82, 1-63 (1982) · Zbl 0496.05058 |
| [46] | König, D., Theorie der endlichen und unendlichen Graphen (1935), Chelsea Publishing · JFM 62.0654.05 |
| [47] | Kuratowski, K., Sur le problème des courbes gauches en topologie, Fund. Math. Vol., 15, 271-283 (1930) · JFM 56.1141.03 |
| [48] | Li, X.; Li, Y.; Shi, Y.; Gutman, I., Note on the HOMO-LUMO index of graphs, MATCH Commun. Math. Comput. Chem., 70, 85-96 (2013) · Zbl 1299.05225 |
| [49] | Li, X.; Shi, Y., A survey on the Randić index, MATCH Commun. Math Comput. Chem., 59, 1, 127-156 (2008) · Zbl 1249.05198 |
| [50] | Li, X.; Shi, Y.; Gutman, I., Graph Energy (2012), Springer: Springer New York · Zbl 1262.05100 |
| [51] | Lovász, L.; Pelikán, J., On the eigenvalues of trees, Periodica Mathematica Hungarica, 3, 1-2, 175-182 (1973) · Zbl 0247.05108 |
| [52] | Ma, J.; Shi, Y.; Wang, Z.; Yue, J., On the eigenvalues of trees, On wiener polarity index of bicyclic networks, 6 (2016) |
| [53] | Maggiora, G. M.; Shanmugasundaram, V., Molecular Similarity Measures, Chemoinformatics: Concepts, Methods, and Tools for Drug Discovery, 1-50 (2004), Humana Press: Humana Press Totowa, NJ, USA |
| [54] | Mazurie, A.; Bonchev, D.; Schwikowski, B.; Buck, G. A., Phylogenetic distances are encoded in networks of interacting pathways, Bioinformatics, 24, 22, 2579-2585 (2008) |
| [55] | Mehler, A.; Weiß, P.; Lücking, A., A network model of interpersonal alignment, Entropy, 12, 6, 1440-1483 (2010) |
| [56] | 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 |
| [57] | Müller, L. A.J.; Dehmer, M.; Emmert-Streib, F., Computational Medicine, chap. Network-based Methods for Computational Diagnostics by Means of R, 185-197 (2012), Springer |
| [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; 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] | Nikolić, S.; Kovačević, G.; Miličević, A.; Trinajstić, N., The Zagreb Index 30 Years After, Croat. Chem. Acta, 76, 113-124 (2003) |
| [60] | Page, L.; Brin, S.; Motwani, R.; Winograd, T., The Pagerank citation ranking: Bringing order to the web, Technical Report (1999), Stanford InfoLab |
| [61] | Peeters, A.; Coolsaet, K.; Brinkmann, G.; Cleemput, N.; Fack, V., Grinvin in a nutshell, J. Math. Chem., 45, 471-477 (2009) · Zbl 1194.92095 |
| [62] | Randić, M., On characterization of molecular branching, J. Amer. Chem. Soc., 97, 6609-6615 (1975) |
| [63] | 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 |
| [64] | Randić, M.; Wilkins, C. L., Graph theoretical approach to recognition of structural similarity in molecules, J. Chem. Inf. Comput. Sci., 19, 31-37 (1979) |
| [65] | Roberts, F., Applications of Combinatorics and Graph Theory to the Biological and Social Sciences Series (1989), Springer |
| [66] | Robertson, N.; Seymour, P. D., Graph minors. part 2. algorithmic aspects of tree-width, J. Algorithms, 7, 309-322 (1986) · Zbl 0611.05017 |
| [67] | Robles-Kelly, A.; Hancock, R., Edit distance from graph spectra, Proceedings of the IEEE International Conference on Computer Vision, 234-241 (2003) |
| [68] | Selkow, S. M., The tree-to-tree editing problem, Inf. Process Lett., 6, 6, 184-186 (1977) · Zbl 0391.68022 |
| [69] | Shams, L. B.; Brady, M. J.; Schaal, S., Graph matching vs mutual information maximization for object detection, Neural Networks, 14, 3, 345-354 (2001) |
| [70] | Skorobogatov, V. A.; Dobrynin, A. A., Metrical Analysis of Graphs, MATCH Commun. Math. Comp. Chem., 23, 105-155 (1988) · Zbl 0666.05065 |
| [71] | Sobik, F., Graphmetriken und klassifikation strukturierter objekte, ZKI-Informationen, Akad Wiss DDR, 2, 82, 63-122 (1982) · Zbl 0496.05059 |
| [72] | 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 |
| [73] | 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 (2004) |
| [74] | 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 |
| [75] | Todeschini, R.; Consonni, V.; Mannhold, R., Handbook of Molecular Descriptors (2002), Wiley-VCH: Wiley-VCH Weinheim, Germany |
| [76] | Todeschini R., Consonni V., Mauri A., Pavan M.. Dragon, software for calculation of molecular descriptors. www.talete.mi.it; Todeschini R., Consonni V., Mauri A., Pavan M.. Dragon, software for calculation of molecular descriptors. www.talete.mi.it |
| [77] | Tripathi, S.; Dehmer, M.; Emmert-Streib, F., Netbiov: an r package for visualizing large network data in biology and medicine, Bioinformatics, 19, 2834-2836 (2014) |
| [78] | Varmuza, K.; Scsibrany, H., Substructure isomorphism matrix, J. Chem. Inf. Comput. Sci., 40, 308-313 (2000) |
| [79] | Wasserman, S.; Faust, K., Social Network Analysis: Methods and Applications (1994), Cambridge University Press |
| [80] | Wiener, H., Structural determination of paraffin boiling points, J. Am. Chem. Soc., 69, 17, 17-20 (1947) |
| [81] | Zager, L. A.; Verghese, G. C., Graph similarity scoring and matching, Appl. Math. Lett., 21, 86-94 (2008) · Zbl 1131.05091 |
| [82] | Zelinka, B., On a certain distance between isomorphism classes of graphs, Časopis pro p̆est Mathematiky, 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.
