{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T10:18:03Z","timestamp":1777630683091,"version":"3.51.4"},"reference-count":49,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2012,3,14]],"date-time":"2012-03-14T00:00:00Z","timestamp":1331683200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>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\u00f6rner entropy) variants of entropy-based models are discussed in some detail.<\/jats:p>","DOI":"10.3390\/e14030559","type":"journal-article","created":{"date-parts":[[2012,3,14]],"date-time":"2012-03-14T14:17:19Z","timestamp":1331734639000},"page":"559-570","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":195,"title":["Entropy and the Complexity of Graphs Revisited"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8254-505X","authenticated-orcid":false,"given":"Abbe","family":"Mowshowitz","sequence":"first","affiliation":[{"name":"Department of Computer Science, The City College of New York (CUNY), 138th Street at ConventAvenue, New York, NY 10031, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Dehmer","sequence":"additional","affiliation":[{"name":"Institute for Bioinformatics and Translational Research, UMIT, Eduard Wallnoefer Zentrum 1, 6060, Hall in Tyrol, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2012,3,14]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF02477860","article-title":"Life, information theory, and topology","volume":"17","author":"Rashevsky","year":"1955","journal-title":"Bull. Math. Biophys."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1038\/43601","article-title":"Diameter of the world wide web","volume":"401","author":"Albert","year":"1999","journal-title":"Nature"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1103\/RevModPhys.74.47","article-title":"Statistical mechanics of complex networks","volume":"74","author":"Albert","year":"2002","journal-title":"Rev. Mod. Phys."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"4517","DOI":"10.1063\/1.434593","article-title":"Information theory, distance matrix and molecular branching","volume":"67","author":"Bonchev","year":"1977","journal-title":"J. Chem. Phys."},{"key":"ref_5","unstructured":"Bonchev, D. (1983). Information Theoretic Indices for Characterization of Chemical Structures, Research Studies Press."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/S0378-8733(01)00030-2","article-title":"The complexity of social networks: Theoretical and empirical findings","volume":"23","author":"Butts","year":"2001","journal-title":"Soc. Network."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"1440","DOI":"10.3390\/e12061440","article-title":"A network model of interpersonal alignment","volume":"12","author":"Mehler","year":"2010","journal-title":"Entropy"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2039","DOI":"10.1098\/rspb.2001.1767","article-title":"Complexity and fragility in ecological networks","volume":"268","author":"Montoya","year":"2001","journal-title":"Proc. Roy. Soc. Lond. B Biol. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/j.compbiolchem.2004.09.001","article-title":"Quantitative methods for ecological network analysis","volume":"28","author":"Ulanowicz","year":"2004","journal-title":"Comput. Biol. Chem."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Dehmer, M., Barbarini, N., Varmuza, K., and Graber, A. (2010). Novel topological descriptors for analyzing biological networks. BMC Struct. Biol., 10.","DOI":"10.1186\/1472-6807-10-18"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1021\/ci990114y","article-title":"Topological indices: Their nature and mutual relatedness","volume":"40","author":"Basak","year":"2000","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bonchev, D., and Rouvray, D.H. (2005). Complexity in Chemistry, Biology, and Ecology, Springer. Mathematical and Computational Chemistry.","DOI":"10.1007\/b136300"},{"key":"ref_13","first-page":"1783","article-title":"Information theoretic measures of UHG graphs with low computational complexity","volume":"190","author":"Dehmer","year":"2007","journal-title":"Appl. Math. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.ins.2010.08.041","article-title":"A history of graph entropy measures","volume":"1","author":"Dehmer","year":"2011","journal-title":"Inform. Sci."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1007\/BF02476948","article-title":"Entropy and the complexity of the graphs: I. An index of the relative complexity of a graph","volume":"30","author":"Mowshowitz","year":"1968","journal-title":"Bull. Math. Biophys."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"045102(R)","DOI":"10.1103\/PhysRevE.80.045102","article-title":"Entropy measures for networks: Toward an information theory of complex topologies","volume":"80","author":"Anand","year":"2009","journal-title":"Phys. Rev. E"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/978-3-540-44485-5_9","article-title":"Information theory of complex networks: On evolution and architectural constraints","volume":"650","author":"Valverde","year":"2004","journal-title":"Lect. Notes Phys."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Dehmer, M., and Emmert-Streib, F. (2009). Analysis of Complex Networks: From Biology to Linguistics, Wiley-VCH.","DOI":"10.1002\/9783527627981"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/j.physa.2007.06.029","article-title":"Information theoretic description of networks","volume":"388","author":"Wilhelm","year":"2007","journal-title":"Physica A"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1080\/03081089008818029","article-title":"Graph complexity and the Laplacian matrix in blocked experiments","volume":"28","author":"Constantine","year":"1990","journal-title":"Linear and Multilinear Algebra"},{"key":"ref_21","first-page":"567","article-title":"Kolmogorov\u2019s information, Shannon\u2019s entropy, and topological complexity of molecules","volume":"28","author":"Bonchev","year":"1995","journal-title":"Bulg. Chem. Commun."},{"key":"ref_22","first-page":"82","article-title":"Information processing in complex networks: Graph entropy and information functionals","volume":"201","author":"Dehmer","year":"2008","journal-title":"Appl. Math. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/cplx.20379","article-title":"Generalized graph entropies","volume":"17","author":"Dehmer","year":"2011","journal-title":"Complexity"},{"key":"ref_24","first-page":"3","article-title":"Three approaches to the definition of information (in Russian)","volume":"1","author":"Kolmogorov","year":"1965","journal-title":"Probl. Peredaci Inform."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Li, M., and Vit\u00e1nyi, P. (1997). An Introduction to Kolmogorov Complexity and Its Applications, Springer.","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Bertz, S.H., and Sommmer, T.J. (1997). Rigorous mathematical approaches to strategic bonds and synthetic analysis based on conceptually simple new complexity indices. Chem. Commun.","DOI":"10.1039\/a706192g"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"312","DOI":"10.1002\/cbdv.200490028","article-title":"Complexity analysis of yeast proteome network","volume":"1","author":"Bonchev","year":"2004","journal-title":"Chem. Biodivers."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1063\/1.1746554","article-title":"Influence of neighbor bonds on additive bond properties in paraffins","volume":"15","author":"Platt","year":"1947","journal-title":"J. Chem. Phys."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"934","DOI":"10.1021\/ci990120u","article-title":"Overall connectivities and topological complexities: A new powerful tool for QSPR\/QSAR","volume":"40","author":"Bonchev","year":"2000","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"582","DOI":"10.1021\/ci000104t","article-title":"The overall Wiener index\u2014A new tool for characterization of molecular topology","volume":"41","author":"Bonchev","year":"2001","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"ref_31","first-page":"1554","article-title":"The overall topological complexity indices","volume":"Volume 4B","author":"Simos","year":"2005","journal-title":"Advances in Computational Methods in Science and Engineering"},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"515","DOI":"10.1007\/BF00279952","article-title":"Graph complexity","volume":"25","year":"1988","journal-title":"Acta Informatica"},{"key":"ref_33","unstructured":"Shannon, C.E., and Weaver, W. (1949). The Mathematical Theory of Communication, University of Illinois Press."},{"key":"ref_34","unstructured":"Cover, T.M., and Thomas, J.A. (2006). Elements of Information Theory, Wiley & Sons. Wiley Series in Telecommunications and Signal Processing."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1080\/0022250X.2000.9990239","article-title":"An axiomatic approach to network complexity","volume":"24","author":"Butts","year":"2000","journal-title":"J. Math. Sociol."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1007\/BF02476692","article-title":"Entropy and the complexity of graphs II: The information content of digraphs and infinite graphs","volume":"30","author":"Mowshowitz","year":"1968","journal-title":"Bull. Math. Biophys."},{"key":"ref_37","first-page":"4820","article-title":"Information theoretic measures of complexity","volume":"Volume 5","author":"Meyers","year":"2009","journal-title":"Encyclopedia of Complexity and System Science"},{"key":"ref_38","unstructured":"Todeschini, R., Consonni, V., and Mannhold, R. (2002). Handbook of Molecular Descriptors, Wiley-VCH."},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Bang-Jensen, J., and Gutin, G. (2002). Digraphs, Theory, Algorithms and Applications, Springer.","DOI":"10.1007\/978-1-4471-3886-0"},{"key":"ref_40","unstructured":"K\u00f6rner, J. (,  1973). Coding of an information source having ambiguous alphabet and the entropy of graphs. Proceedings of the 6th Prague Conference on Information Theory, Prague, Czech Republic."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1090\/dimacs\/020\/08","article-title":"Graph entropy: A survey","volume":"Volume 20","author":"Cook","year":"1995","journal-title":"Combinatorial Optimization"},{"key":"ref_42","unstructured":"Cardinal, L., Fiorini, S., and Assche, G.V. (,  2004). On minimum entropy graph colorings. Proceedings of the 2004 IEEE International Symposium on Information Theory, Piscataway, NJ, USA."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"1655","DOI":"10.1021\/ci900060x","article-title":"On entropy-based molecular descriptors: Statistical analysis of real and synthetic chemical structures","volume":"49","author":"Dehmer","year":"2009","journal-title":"J. Chem. Inf. Model."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"e15733","DOI":"10.1371\/journal.pone.0015733","article-title":"Connections between classical and parametric network entropies","volume":"6","author":"Dehmer","year":"2011","journal-title":"PLoS One"},{"key":"ref_45","first-page":"147","article-title":"Uniquely discriminating molecular structures using novel eigenvalue-based descriptors","volume":"67","author":"Dehmer","year":"2012","journal-title":"MATCH Commun. Math. Comput. Chem."},{"key":"ref_46","first-page":"133","article-title":"The Wiener number of graphs. I. General theory and changes due to graph operations","volume":"21","author":"Polansky","year":"1986","journal-title":"MATCH MATCH Commun. Math. Comput. Chem."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"239","DOI":"10.1016\/0166-218X(88)90017-0","article-title":"On some counting polynomials","volume":"19","author":"Hosoya","year":"1988","journal-title":"Discrete Appl. Math."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1021\/c160043a020","article-title":"The characteristic polynomial does not uniquely determined the topology of a molecule","volume":"11","author":"Balaban","year":"1971","journal-title":"J. Chem. Doc."},{"key":"ref_49","unstructured":"Diudea, M.V. (2001). QSPR\/QSAR Studies by Molecular Descriptors, Nova Publishing."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/14\/3\/559\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:49:23Z","timestamp":1760219363000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/14\/3\/559"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,3,14]]},"references-count":49,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2012,3]]}},"alternative-id":["e14030559"],"URL":"https:\/\/doi.org\/10.3390\/e14030559","relation":{},"ISSN":["1099-4300"],"issn-type":[{"value":"1099-4300","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,3,14]]}}}