×

Entropy and the complexity of graphs revisited. (English) Zbl 1331.94041

Summary: This paper presents a taxonomy and overview of approaches to the measurement of graph and network complexity. The taxonomy distinguishes between deterministic (e.g., Kolmogorov complexity) and probabilistic approaches with a view to placing entropy-based probabilistic measurement in context. Entropy-based measurement is the main focus of the paper. Relationships between the different entropy functions used to measure complexity are examined; and intrinsic (e.g., classical measures) and extrinsic (e.g., Körner entropy) variants of entropy-based models are discussed in some detail.

MSC:

94A15 Information theory (general)
68P30 Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1007/BF02477860 · doi:10.1007/BF02477860
[2] Albert, Diameter of the world wide web, Nature 401 pp 130– (1999) · doi:10.1038/43601
[3] DOI: 10.1103/RevModPhys.74.47 · Zbl 1205.82086 · doi:10.1103/RevModPhys.74.47
[4] DOI: 10.1063/1.434593 · doi:10.1063/1.434593
[5] Bonchev, Information Theoretic Indices for Characterization of Chemical Structures (1983)
[6] DOI: 10.1016/S0378-8733(01)00030-2 · doi:10.1016/S0378-8733(01)00030-2
[7] DOI: 10.3390/e12061440 · Zbl 05995880 · doi:10.3390/e12061440
[8] DOI: 10.1098/rspb.2001.1767 · doi:10.1098/rspb.2001.1767
[9] DOI: 10.1016/j.compbiolchem.2004.09.001 · Zbl 1088.92061 · doi:10.1016/j.compbiolchem.2004.09.001
[10] DOI: 10.1186/1472-6807-10-18 · doi:10.1186/1472-6807-10-18
[11] DOI: 10.1021/ci990114y · doi:10.1021/ci990114y
[12] Complexity in Chemistry, Biology, and Ecology (2005) · Zbl 1109.92300
[13] DOI: 10.1016/j.amc.2007.02.095 · Zbl 1123.68088 · doi:10.1016/j.amc.2007.02.095
[14] DOI: 10.1016/j.ins.2010.08.041 · Zbl 1204.94050 · doi:10.1016/j.ins.2010.08.041
[15] DOI: 10.1007/BF02476948 · Zbl 0165.57601 · doi:10.1007/BF02476948
[16] DOI: 10.1103/PhysRevE.80.045102 · doi:10.1103/PhysRevE.80.045102
[17] Solé, Information theory of complex networks: On evolution and architectural constraints, Lect. Notes Phys. 650 pp 189– (2004) · doi:10.1007/978-3-540-44485-5_9
[18] Thurner, Statistical mechanics of complex networks, Analysis of Complex Networks: From Biology to Linguistics pp 23– (2009)
[19] DOI: 10.1016/j.physa.2007.06.029 · doi:10.1016/j.physa.2007.06.029
[20] DOI: 10.1080/03081089008818029 · Zbl 0714.05040 · doi:10.1080/03081089008818029
[21] Bonchev, Kolmogorov’s information, Shannon’s entropy, and topological complexity of molecules, Bulg. Chem. Commun. 28 pp 567– (1995)
[22] DOI: 10.1016/j.amc.2007.12.010 · Zbl 1152.05361 · doi:10.1016/j.amc.2007.12.010
[23] DOI: 10.1002/cplx.20379 · doi:10.1002/cplx.20379
[24] Kolmogorov, Three approaches to the definition of information (in Russian), Probl. Peredaci Inform. 1 pp 3– (1965)
[25] Li, An Introduction to Kolmogorov Complexity and Its Applications (1997) · Zbl 0866.68051
[26] DOI: 10.1039/a706192g · doi:10.1039/a706192g
[27] DOI: 10.1002/cbdv.200490028 · doi:10.1002/cbdv.200490028
[28] DOI: 10.1063/1.1746554 · doi:10.1063/1.1746554
[29] DOI: 10.1021/ci990120u · doi:10.1021/ci990120u
[30] DOI: 10.1021/ci000104t · doi:10.1021/ci000104t
[31] Bonchev, The overall topological complexity indices, Advances in Computational Methods in Science and Engineering Volume 4B pp 1554– (2005)
[32] Pudlák, Graph complexity, Acta Informatica 25 pp 515– (1988)
[33] Shannon, The Mathematical Theory of Communication (1949) · Zbl 0041.25804
[34] Cover, Elements of Information Theory (2006)
[35] DOI: 10.1080/0022250X.2000.9990239 · Zbl 0989.91095 · doi:10.1080/0022250X.2000.9990239
[36] DOI: 10.1007/BF02476692 · Zbl 0165.57602 · doi:10.1007/BF02476692
[37] Bonchev, Information theoretic measures of complexity, Encyclopedia of Complexity and System Science Volume 5 pp 4820– (2009)
[38] Todeschini, Handbook of Molecular Descriptors (2002)
[39] Bang-Jensen, Digraphs, Theory, Algorithms and Applications (2002) · Zbl 1001.05002
[41] Simonyi, Graph entropy: A survey, Combinatorial Optimization Volume 20 pp 399– (1995) · Zbl 0828.05001
[43] DOI: 10.1021/ci900060x · doi:10.1021/ci900060x
[44] DOI: 10.1371/journal.pone.0015733 · doi:10.1371/journal.pone.0015733
[45] Dehmer, Uniquely discriminating molecular structures using novel eigenvalue-based descriptors, MATCH Commun. Math. Comput. Chem. 67 pp 147– (2012)
[46] Polansky, The Wiener number of graphs. I. General theory and changes due to graph operations, MATCH MATCH Commun. Math. Comput. Chem. 21 pp 133– (1986) · Zbl 0603.05045
[47] DOI: 10.1016/0166-218X(88)90017-0 · Zbl 0633.05006 · doi:10.1016/0166-218X(88)90017-0
[48] DOI: 10.1021/c160043a020 · doi:10.1021/c160043a020
[49] Randić, Eigenvalues as molecular descriptors, QSPR/QSAR Studies by Molecular Descriptors pp 93– (2001)
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.