×

A history of graph entropy measures. (English) Zbl 1204.94050

Summary: This survey seeks to describe methods for measuring the entropy of graphs and to demonstrate the wide applicability of entropy measures. Setting the scene with a review of classical measures for determining the structural information content of graphs, we discuss graph entropy measures which play an important role in a variety of problem areas, including biology, chemistry, and sociology. In addition, we examine relationships between selected entropy measures, illustrating differences quantitatively with concrete examples.

MSC:

94A17 Measures of information, entropy
05C90 Applications of graph theory
94-03 History of information and communication theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Allen, E. B., Measuring graph abstractions of software: an information-theory approach, (Proceedings of the Eighth International Symposium on Software Metrics table of contents (2002), IEEE Computer Society), 182
[2] Altay, G.; Emmert-Streib, F., Revealing differences in gene network inference algorithms on the network-level by ensemble methods, Bioinformatics, 26, 1738-1744 (2010)
[3] Anand, K.; Bianconi, G., Entropy measures for networks: toward an information theory of complex topologies, Physical Review E, 80, 045102(R) (2009)
[4] Antiqueira, L.; Costa, L. da F., Characterization of subgraph relationships and distribution in complex networks, New Journal of Physics, 11 (2009)
[5] Balaban, A. T.; Balaban, T. S., New vertex invariants and topological indices of chemical graphs based on information on distances, Journal of Mathematical Chemistry, 8, 383-397 (1991)
[6] Balch, T., Hierarchic social entropy: an information theoretic measure of robot group diversity, Autonomous Robots, 8, 209-237 (2001)
[7] Barabási, A. L.; Albert, R., Emergence of scaling in random networks, Science, 286, 509-512 (1999) · Zbl 1226.05223
[8] Bertz, S. H., The first general index of molecular complexity, Journal of the American Chemical Society, 103, 3241-3243 (1981)
[9] Bertz, S. H., On the complexity of graphs and molecules, Bulletin of Mathematical Biology, 45, 849-855 (1983) · Zbl 0517.92028
[10] Boccaletti, S.; Latora, V.; Moreno, Y.; Chavez, M.; Hwang, D.-U., Complex networks: structure and dynamics, Physics Reports, 424, 4-5, 175-308 (2006) · Zbl 1371.82002
[11] Bonchev, D., Information Theoretic Indices for Characterization of Chemical Structures (1983), Research Studies Press: Research Studies Press Chichester
[12] Bonchev, D., Overall connectivities and topological complexities: a new powerful tool for QSPR/QSAR, Journal of Chemical Information and Computer Science, 40, 4, 934-941 (2000)
[13] Bonchev, D., Complexity in Chemistry. Complexity in Chemistry, Introduction and Fundamentals, Taylor and Francis (2003), Boca Raton: Boca Raton FL, USA · Zbl 1126.92308
[14] Bonchev, D.; Rouvray, D. H., Complexity in Chemistry, Biology and Ecology. Complexity in Chemistry, Biology and Ecology, Mathematical and Computational Chemistry (2005), Springer: Springer New York, NY, USA · Zbl 1109.92300
[15] Bonchev, D.; Trinajstić, N., Information theory distance matrix and molecular branching, Journal of Chemical Physics, 67, 4517-4533 (1977)
[16] S. Borgert, M. Dehmer, E. Aitenbichler, On quantitative network complexity measures for business process models, Acta Universitates Apulensis, 18, in press.; S. Borgert, M. Dehmer, E. Aitenbichler, On quantitative network complexity measures for business process models, Acta Universitates Apulensis, 18, in press.
[17] Bornholdt, S.; Schuster, H. G., Handbook of Graphs and Networks: From the Genome to the Internet (2003), John Wiley & Sons Inc.: John Wiley & Sons Inc. New York, NY, USA · Zbl 1044.90002
[18] Brandes, U., A faster algorithm for betweenness centrality, Journal of Mathematical Sociology, 25, 2, 163-177 (2001) · Zbl 1051.91088
[19] Butts, C. T., The complexity of social networks: theoretical and empirical findings, Social Networks, 23, 31-71 (2001)
[20] Chanda, P.; Sucheston, L.; Liu, S.; Zhang, A.; Ramanathan, M., Information-theoretic gene-gene and gene-environment interaction analysis of quantitative traits, BMC Genomics, 10, 1, 509 (2009)
[21] Claussen, J. C., Characterization of networks by the offdiagonal complexity, Physica A, 375, 365-373 (2007)
[22] Cook, W. J.; Cunningham, W. H.; Pullyblank, W. R.; Schrijver, A., Combinatorial Optimization (1998), Wiley
[23] Cover, T. M.; Thomas, J. A., Elements of Information Theory. Elements of Information Theory, Wiley Series in Telecommunications and Signal Processing (2006), Wiley & Sons · Zbl 1140.94001
[24] Csiszár, I.; Körner, J.; Lovász, L.; Marto, K.; Simonyi, G., Entropy splitting for antiblocking corners and perfect graphs, Combinatorica, 10, 1, 27-40 (1990) · Zbl 0734.05061
[25] Costa, L. da F.; Rodrigues, F.; Travieso, G., Characterization of complex networks: a survey of measurements, Advances in Physics, 56, 167-242 (2007)
[26] Costa, L. da F.; Rodrigues, F. A., Seeking for simplicity in complex networks, Europhysics Letters, 85, 48001(1)-48001(6) (2009)
[27] Costa, L. da F.; Rodrigues, F. A.; Hilgetag, C. C.; Kaiser, M., Beyond the average: detecting global singular nodes from local features in complex networks, Europhysics Letters, 87, 18008(1)-18008(6) (2009)
[28] Dehmer, M., Information-theoretic concepts for the analysis of complex networks, Applied Artificial Intelligence, 22, 7 & 8, 684-706 (2008)
[29] Dehmer, M., A novel method for measuring the structural information content of networks, Cybernetics and Systems, 39, 825-843 (2008) · Zbl 1290.94022
[30] Dehmer, M.; Borgert, S.; Emmert-Streib, F., Entropy bounds for molecular hierarchical networks, PLoS ONE, 3, 8, e3079 (2008)
[31] Dehmer, M.; Emmert-Streib, F., Structural information content of networks: graph entropy based on local vertex functionals, Computational Biology and Chemistry, 32, 131-138 (2008) · Zbl 1141.92043
[32] Dehmer, M.; Emmert-Streib, F., Towards network complexity, (Zhou, J., Complex Sciences. Complex Sciences, Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol. 4 (2009), Springer: Springer Berlin/Heidelberg, Germany), 707-714
[33] M. Dehmer, A. Mehler, F. Emmert-Streib, Graph-theoretical characterizations of generalized trees, in: Proceedings of the International Conference on Machine Learning: Models, Technologies & Applications (MLMTA’07), Las Vegas/USA, 2007, pp. 113-117, 2007.; M. Dehmer, A. Mehler, F. Emmert-Streib, Graph-theoretical characterizations of generalized trees, in: Proceedings of the International Conference on Machine Learning: Models, Technologies & Applications (MLMTA’07), Las Vegas/USA, 2007, pp. 113-117, 2007.
[34] Dehmer, M.; Mowshowitz, A., Inequalities for entropy-based measures of network information content, Applied Mathematics and Computation, 215, 4263-4271 (2010) · Zbl 1220.05125
[35] Dehmer, M.; Varmuza, K.; Borgert, S.; Emmert-Streib, F., On entropy-based molecular descriptors: statistical analysis of real and synthetic chemical structures, Journal of Chemical Information and Modelling, 49, 1655-1663 (2009)
[36] Dijkstra, E. W., A note on two problems in connection with graphs, Numerische Math., 1, 269-271 (1959) · Zbl 0092.16002
[37] Dorogovtsev, S. N.; Mendes, J. F.F., Evolution of Networks. Evolution of Networks, From Biological Networks to the Internet and WWW (2003), Oxford University Press · Zbl 1010.05073
[38] Dragomir, S. S.; Goh, C. J., Some bounds on entropy measures in information theory, Applied Mathematics Letters, 10, 23-28 (1997) · Zbl 0906.94004
[39] Emmert-Streib, F.; Dehmer, M., Information theoretic measures of UHG graphs with low computational complexity, Applied Mathematics and Computation, 190, 1783-1794 (2007) · Zbl 1123.68088
[40] Emmert-Streib, F.; Dehmer, M., Topological mappings between graphs trees and generalized trees, Applied Mathematics and Computation, 186, 2, 1326-1333 (2007) · Zbl 1117.05027
[41] Emmert-Streib, F.; Dehmer, M., Fault tolerance of information processing in gene networks, Physica A, 338, 4, 541-548 (2009)
[42] F. Emmert-Streib, M. Dehmer, J. Kilian, Classification of large graphs by a local tree decomposition, in: H.R. Arabnia, A. Scime (Eds.), Proceedings of DMIN’05, International Conference on Data Mining, Las Vegas, USA, 2005, pp. 200-207.; F. Emmert-Streib, M. Dehmer, J. Kilian, Classification of large graphs by a local tree decomposition, in: H.R. Arabnia, A. Scime (Eds.), Proceedings of DMIN’05, International Conference on Data Mining, Las Vegas, USA, 2005, pp. 200-207.
[43] Everett, M. G., Role similarity and complexity in social networks, Social Networks, 7, 353-359 (1985)
[44] Freeman, L. C., Spheres cubes and boxes: graph dimensionality and network structure, Social Networks, 5, 139-156 (1983)
[45] Halin, R., Graphentheorie (1989), Akademie Verlag: Akademie Verlag Berlin, Germany · Zbl 0684.05015
[46] Harary, F., Graph Theory (1969), Addison Wesley Publishing Company: Addison Wesley Publishing Company Reading, MA, USA · Zbl 0797.05064
[47] Hirata, H.; Ulanowicz, R. E., Information theoretical analysis of ecological networks, International Journal of Systems Science, 15, 261-270 (1984) · Zbl 0545.92017
[48] Hosoya, H., Topological index. A newly proposed quantity characterizing the topological nature of structural isomers of saturated hydrocarbons, Bulletin of the Chemistry Society of Japan, 44, 2332-2339 (1971)
[49] Jain, A. K.; Dubes, R. C., Algorithms for Clustering Data (1988), Prentice-Hall Inc.: Prentice-Hall Inc. Upper Saddle River, NJ, USA · Zbl 0665.62061
[50] Jiang, B.; Claramunt, C., A structural approach to the model generalization of an urban street network, Geoinformatica, 8, 2, 157-171 (2004)
[51] Kim, D. C.; Wang, X.; Yang, C. R.; Gao, J., Learning biological network using mutual information and conditional independence, BMC Bioinformatics, 11, 3, S9 (2010)
[52] Kim, J.; Wilhelm, T., What is a complex graph?, Physica A, 387, 2637-2652 (2008)
[53] Konstantinova, E. V.; Paleev, A. A., Sensitivity of topological indices of polycyclic graphs, Vychisl. Sistemy., 136, 38-48 (1990), (in Russian) · Zbl 0769.05068
[54] Konstantinova, E. V.; Skorobogatov, V. A.; Vidyuk, M. V., Applications of information theory in chemical graph theory, Indian Journal of Chemistry, 42, 1227-1240 (2002)
[55] J. Körner, Coding of an information source having ambiguous alphabet and the entropy of graphs, in: Transactions of the Sixth Prague Conference on Information Theory, 1973, pp. 411-425,.; J. Körner, Coding of an information source having ambiguous alphabet and the entropy of graphs, in: Transactions of the Sixth Prague Conference on Information Theory, 1973, pp. 411-425,.
[56] Kullback, S.; Leibler, R. A., On information and sufficiency, Annals of Mathematical Statistics, 22, 1, 79-86 (1951) · Zbl 0042.38403
[57] A.M. Latva-Koivisto. Finding a complexity measure for business process models, Technical report, Helsinki University of Technology, 2001.; A.M. Latva-Koivisto. Finding a complexity measure for business process models, Technical report, Helsinki University of Technology, 2001.
[58] Li, M.; Vitányi, P. M.B., Combinatorics and kolmogorov complexity, (Proceedings of the Sixth Annual IEEE Conference on Structure in Complexity Theory (1991), Springer: Springer Berlin, New York)
[59] Lu, J.-L.; Valois, F.; Dohler, M.; Barthel, D., Quantifying organization by means of entropy, Communications Letters IEEE, 12, 3, 185-187 (2008)
[60] Luce, R. D.; Bush, R. R.; Galanter, E., Handbook of Mathematical Psychology (1967), John Wiley and Sons · Zbl 0128.39901
[61] Maruyama, M.; Fenwick, P.; Ioannides, A., Interocular yoking in human saccades examined by mutual information analysis, Nonlinear Biomedical Physics, 4, 1, S10 (2010)
[62] (Dehmer, M.; Emmert-Streib, F.; Mehler, A., Towards an Information Theory of Complex Networks: Statistical Methods and Applications (2009), Birkhäuser: Birkhäuser Boston/Basel), A. Mehler. A quantitative graph model of social ontologies by example of Wikipedia. in
[63] 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). Proceedings of the Fourth International Workshop on Innovative Internet Computing Systems (I2CS ’04), Lecture Notes in Computer Science, vol. 3473 (2004), Springer: Springer Berlin/New York), 136-150
[64] Minoli, D., Combinatorial graph complexity, Atti. Accad. Naz. Lincei, VIII. Ser., Rend., Cl. Sci. Fis. Mat. Nat., 59, 651-661 (1975) · Zbl 0361.05046
[65] Morowitz, H., Some order-disorder considerations in living systems, Bulletin of Mathematical Biophysics, 17, 81-86 (1953)
[66] Mowshowitz, A., Entropy and the complexity of graphs II: the information content of digraphs and infinite graphs, Bulletin of Mathematical Biophysics, 30, 225-240 (1968) · Zbl 0165.57602
[67] Mowshowitz, A., Entropy and the complexity of graphs III: graphs with prescribed information content, Bulletin of Mathematical Biophysics, 30, 387-414 (1968) · Zbl 0165.57603
[68] Mowshowitz, A., Entropy and the complexity of graphs IV: entropy measures and graphical structure, Bulletin of Mathematical Biophysics, 30, 533-546 (1968) · Zbl 0204.24603
[69] Mowshowitz, A., Entropy and the complexity of the graphs I: an index of the relative complexity of a graph, Bulletin of Mathematical Biophysics, 30, 175-204 (1968) · Zbl 0165.57601
[70] Newman, M. E.J.; Barabási, A. L.; Watts, D. J., The Structure and Dynamics of Networks. The Structure and Dynamics of Networks, Princeton Studies in Complexity (2006), Princeton University Press · Zbl 1362.00042
[71] Nikolić, S.; Trinajstić, N., Complexity of molecules, J. Chem. Inf. Comput. Sci., 40, 920-926 (2000)
[72] Passerini, F.; Severini, S., The von neumann entropy of networks, International Journal of Agent Technologies and Systems, 1, 58-67 (2009)
[73] Quastler, H., Information theory in biology, Bulletin of Mathematical Biology, 183-185 (1954)
[74] Randić, M., On characterization of molecular branching, Journal of the American Chemical Society, 97, 6609-6615 (1975)
[75] Randić, M.; Plavšić, D., Characterization of molecular complexity, International Journal of Quantum Chemistry, 91, 20-31 (2002)
[76] Randić, M.; Plavšić, D., On the concept of molecular complexity, Croatica Chemica Acta, 75, 107-116 (2002)
[77] Rashevsky, N., Life information theory and topology, Bulletin of Mathematical Biophysics, 17, 229-235 (1955)
[78] Raychaudhury, C.; Ray, S. K.; Ghosh, J. J.; Roy, A. B.; Basak, S. C., Discrimination of isomeric structures using information theoretic topological indices, Journal of Computational Chemistry, 5, 581-588 (1984)
[79] Shannon, C. E.; Weaver, W., The Mathematical Theory of Communication (1949), University of Illinois Press · Zbl 0041.25804
[80] G. Simonyi, Graph entropy: a survey, in: W. Cook, L. Lovász, P. Seymour (Eds.), Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 20, 1995, pp. 399-441.; G. Simonyi, Graph entropy: a survey, in: W. Cook, L. Lovász, P. Seymour (Eds.), Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 20, 1995, pp. 399-441. · Zbl 0828.05001
[81] Simonyi, G., Perfect graphs and graph entropy. An updated survey, (Ramirez-Alfonsin, J.; Reed, B., Perfect Graphs (2001), John Wiley & Sons), 293-328 · Zbl 0990.05054
[82] Skorobogatov, V. A.; Dobrynin, A. A., Metrical analysis of graphs, Communications in Mathematical and in Computer Chemistry, 23, 105-155 (1988) · Zbl 0666.05065
[83] R.V. Solé, S. Valverde, Information theory of complex networks: on evolution and architectural constraints, in: Lecture Notes in Physics, vol. 650, 2004, pp. 189-207.; R.V. Solé, S. Valverde, Information theory of complex networks: on evolution and architectural constraints, in: Lecture Notes in Physics, vol. 650, 2004, pp. 189-207. · Zbl 1109.90068
[84] Thurner, S., Statistical mechanics of complex networks, (Dehmer, M.; Emmert-Streib, F., Analysis of Complex Networks: From Biology to Linguistics (2009), Wiley-VCH), 23-45 · Zbl 1260.82008
[85] Todeschini, R.; Consonni, V.; Mannhold, R., Handbook of Molecular Descriptors (2002), Wiley-VCH: Wiley-VCH Germany,Weinheim
[86] Trucco, E., A note on the information content of graphs, Bulletin of Mathematical Biology, 18, 2, 129-135 (1956)
[87] Türker, L., Contemplation on the hosoya indices, Journal of Molecular Structure (Theochem), 623, 75-77 (2003)
[88] Tutzauer, F., Entropy as a measure of centrality in networks characterized by path-transfer flow, Social Networks, 29, 249-265 (2007)
[89] Ulanowicz, R. E., Information theory in ecology, Computers and Chemistry, 25, 393-399 (2001)
[90] Ulanowicz, R. E., Quantitative methods for ecological network analysis, Computational Biology and Chemistry, 28, 321-339 (2004) · Zbl 1088.92061
[91] Wasserman, S.; Faust, K., Social Network Analysis: Methods and Applications. Social Network Analysis: Methods and Applications, Structural Analysis in the Social Sciences (1994), Cambridge University Press
[92] Wiener, H., Structural determination of paraffin boiling points, Journal of the American Chemical Society, 69, 17, 17-20 (1947)
[93] Wilhelm, T.; Brueggemann, R., Information theoretic measures for the maturity of ecosystems, (Matthies, M.; Malchow, H.; Kriz, J., Integrative Systems Approaches to Natural and Social Sciences Systems Science2000 (2001), Springer: Springer Berlin,Germany), 263-273
[94] Xie, F.; Levinson, D., Measuring the structure of road networks, Geographical Analysis, 39, 3, 336-356 (2007)
[95] Yockey, H. P., Information Theory and Molecular Biology (1992), Cambridge University Press: Cambridge University Press Cambridge,UK · Zbl 0759.92004
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.