![](/images/graphics-bg.png)
On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy
Joint Authors
Morzy, Mikołaj
Alhajj, Reda
Kajdanowicz, Tomasz
Source
Issue
Vol. 2017, Issue 2017 (31 Dec. 2017), pp.1-12, 12 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2017-11-01
Country of Publication
Egypt
No. of Pages
12
Main Subjects
Abstract EN
One of the most popular methods of estimating the complexity of networks is to measure the entropy of network invariants, such as adjacency matrices or degree sequences.
Unfortunately, entropy and all entropy-based information-theoretic measures have several vulnerabilities.
These measures neither are independent of a particular representation of the network nor can capture the properties of the generative process, which produces the network.
Instead, we advocate the use of the algorithmic entropy as the basis for complexity definition for networks.
Algorithmic entropy (also known as Kolmogorov complexity or K-complexity for short) evaluates the complexity of the description required for a lossless recreation of the network.
This measure is not affected by a particular choice of network features and it does not depend on the method of network representation.
We perform experiments on Shannon entropy and K-complexity for gradually evolving networks.
The results of these experiments point to K-complexity as the more robust and reliable measure of network complexity.
The original contribution of the paper includes the introduction of several new entropy-deceiving networks and the empirical comparison of entropy and K-complexity as fundamental quantities for constructing complexity measures for networks.
American Psychological Association (APA)
Morzy, Mikołaj& Kajdanowicz, Tomasz& Alhajj, Reda. 2017. On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy. Complexity،Vol. 2017, no. 2017, pp.1-12.
https://search.emarefa.net/detail/BIM-1142701
Modern Language Association (MLA)
Morzy, Mikołaj…[et al.]. On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy. Complexity No. 2017 (2017), pp.1-12.
https://search.emarefa.net/detail/BIM-1142701
American Medical Association (AMA)
Morzy, Mikołaj& Kajdanowicz, Tomasz& Alhajj, Reda. On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy. Complexity. 2017. Vol. 2017, no. 2017, pp.1-12.
https://search.emarefa.net/detail/BIM-1142701
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1142701