Kolmogorov basic graphs and their application in network complexity analysis
Throughout the years, measuring the complexity of networks and graphs has been of great interest to scientists in different fields. Kolmogorov complexity has been known as one of the most important tools of measuring the complexity of an object. As a result, we have formalized a method to calculate...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
MDPI
2021
|
| _version_ | 1826305536927203328 |
|---|---|
| author | Farzaneh, A Coon, JP Badiu, M-A |
| author_facet | Farzaneh, A Coon, JP Badiu, M-A |
| author_sort | Farzaneh, A |
| collection | OXFORD |
| description | Throughout the years, measuring the complexity of networks and graphs has been of great interest to scientists in different fields. Kolmogorov complexity has been known as one of the most important tools of measuring the complexity of an object. As a result, we have formalized a method to calculate an upper bound for the Kolmogorov complexity of graphs and networks. Firstly, the most simple graphs possible, those with O(1) Kolmogorov complexity, are identified. These graphs are then used to develop a method for estimating the complexity of any given graph. The proposed method utilizes the simple structures within a graph to capture its non-randomness. This method is able to capture features that make a network closer to the more non-random end of the spectrum. The resulting algorithm takes a graph as an input and outputs an upper bound to its Kolmogorov complexity. This has applications in areas such as evaluating the performance of graph compression methods. |
| first_indexed | 2024-03-07T06:34:20Z |
| format | Journal article |
| id | oxford-uuid:f7152661-d4f5-469f-b326-ce22e4f0ed4d |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T06:34:20Z |
| publishDate | 2021 |
| publisher | MDPI |
| record_format | dspace |
| spelling | oxford-uuid:f7152661-d4f5-469f-b326-ce22e4f0ed4d2022-03-27T12:40:04ZKolmogorov basic graphs and their application in network complexity analysisJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:f7152661-d4f5-469f-b326-ce22e4f0ed4dEnglishSymplectic ElementsMDPI2021Farzaneh, ACoon, JPBadiu, M-AThroughout the years, measuring the complexity of networks and graphs has been of great interest to scientists in different fields. Kolmogorov complexity has been known as one of the most important tools of measuring the complexity of an object. As a result, we have formalized a method to calculate an upper bound for the Kolmogorov complexity of graphs and networks. Firstly, the most simple graphs possible, those with O(1) Kolmogorov complexity, are identified. These graphs are then used to develop a method for estimating the complexity of any given graph. The proposed method utilizes the simple structures within a graph to capture its non-randomness. This method is able to capture features that make a network closer to the more non-random end of the spectrum. The resulting algorithm takes a graph as an input and outputs an upper bound to its Kolmogorov complexity. This has applications in areas such as evaluating the performance of graph compression methods. |
| spellingShingle | Farzaneh, A Coon, JP Badiu, M-A Kolmogorov basic graphs and their application in network complexity analysis |
| title | Kolmogorov basic graphs and their application in network complexity analysis |
| title_full | Kolmogorov basic graphs and their application in network complexity analysis |
| title_fullStr | Kolmogorov basic graphs and their application in network complexity analysis |
| title_full_unstemmed | Kolmogorov basic graphs and their application in network complexity analysis |
| title_short | Kolmogorov basic graphs and their application in network complexity analysis |
| title_sort | kolmogorov basic graphs and their application in network complexity analysis |
| work_keys_str_mv | AT farzaneha kolmogorovbasicgraphsandtheirapplicationinnetworkcomplexityanalysis AT coonjp kolmogorovbasicgraphsandtheirapplicationinnetworkcomplexityanalysis AT badiuma kolmogorovbasicgraphsandtheirapplicationinnetworkcomplexityanalysis |