On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy
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 a...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2017-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2017/3250301 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832553394955354112 |
|---|---|
| author | Mikołaj Morzy Tomasz Kajdanowicz Przemysław Kazienko |
| author_facet | Mikołaj Morzy Tomasz Kajdanowicz Przemysław Kazienko |
| author_sort | Mikołaj Morzy |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-59c2e58d4dd5443c80a89abffdad27fd |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2017-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-59c2e58d4dd5443c80a89abffdad27fd2025-02-03T05:53:59ZengWileyComplexity1076-27871099-05262017-01-01201710.1155/2017/32503013250301On Measuring the Complexity of Networks: Kolmogorov Complexity versus EntropyMikołaj Morzy0Tomasz Kajdanowicz1Przemysław Kazienko2Institute of Computing Science, Poznan University of Technology, Piotrowo 2, 60-965 Poznań, PolandDepartment of Computational Intelligence, ENGINE-The European Centre for Data Science, Wrocław University of Science and Technology, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, PolandDepartment of Computational Intelligence, ENGINE-The European Centre for Data Science, Wrocław University of Science and Technology, Wybrzeże Wyspiańskiego 27, 50-370 Wrocław, PolandOne 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.http://dx.doi.org/10.1155/2017/3250301 |
| spellingShingle | Mikołaj Morzy Tomasz Kajdanowicz Przemysław Kazienko On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy Complexity |
| title | On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy |
| title_full | On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy |
| title_fullStr | On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy |
| title_full_unstemmed | On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy |
| title_short | On Measuring the Complexity of Networks: Kolmogorov Complexity versus Entropy |
| title_sort | on measuring the complexity of networks kolmogorov complexity versus entropy |
| url | http://dx.doi.org/10.1155/2017/3250301 |
| work_keys_str_mv | AT mikołajmorzy onmeasuringthecomplexityofnetworkskolmogorovcomplexityversusentropy AT tomaszkajdanowicz onmeasuringthecomplexityofnetworkskolmogorovcomplexityversusentropy AT przemysławkazienko onmeasuringthecomplexityofnetworkskolmogorovcomplexityversusentropy |