Entropy and the Complexity of Graphs Revisited

Entropy

Abbe Mowshowitz¹ 

[1] Department of Computer Science, The City College of New York (CUNY), 138th Street at Convent Avenue, New York, NY 10031, USA

关键词: complex networks;    Shannon entropy;    graph entropy;   

DOI  :  10.3390/e14030559

来源: mdpi

【 摘 要 】

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.

【 授权许可】

CC BY   
© 2012 by the authors; licensee MDPI, Basel, Switzerland.