Kolmogorov Basic Graphs and Their Application in Network Complexity Analysis.
Kolmogorov Basic Graphs and Their Application in Network Complexity Analysis.
复制标题
DOI：
10.3390/e23121604
复制
发表时间：
2021-11-29
期刊：
影响因子：
--
通讯作者：
Badiu MA
中科院分区：
文献类型：
--
作者：
Farzaneh A;Coon JP;Badiu MA
多年来，测量网络和图的复杂性一直引起科学家的极大兴趣。Kolmogorov复杂度是度量对象复杂度的重要工具之一。我们形式化了一种方法来计算图和网络的Kolmogorov复杂性的上界。首先，确定最简单的图，即具有Kolmogorov复杂度的图。然后，这些图被用来开发一种方法来估计给定图的复杂性。所提出的方法利用图中的简单结构来捕获其非随机性。这种方法能够捕获使网络更接近频谱的非随机端的特征。由此产生的算法将一个图作为输入，并输出其柯尔莫哥洛夫复杂度的上界。这可以应用于例如评估图压缩方法的性能。
Throughout the years, measuring the complexity of networks and graphs has been of great interest to scientists. The Kolmogorov complexity is known as one of the most important tools to measure the complexity of an object. We formalized a method to calculate an upper bound for the Kolmogorov complexity of graphs and networks. Firstly, the most simple graphs possible, those with Kolmogorov complexity, were identified. These graphs were then used to develop a method to estimate the complexity of a 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 could be applicable in, for example evaluating the performances of graph compression methods.
登录
查看更多内容
影响因子：
--
作者：
SHANNON, CE
通讯作者：
SHANNON, CE
DOI：
10.3390/e22040408
发表时间：
2020-04-03
期刊：
Entropy (Basel, Switzerland)
影响因子：
--
作者：
Vitányi PMB
通讯作者：
Vitányi PMB
影响因子：
9.5
作者：
Aittokallio, Tero;Schwikowski, Benno
通讯作者：
Schwikowski, Benno
影响因子：
1.6
作者：
Buhrman, H;Li, M;Vitányi, P
通讯作者：
Vitányi, P
影响因子：
2.3
作者：
Morzy, Mikolaj;Kajdanowicz, Tomasz;Kazienko, Przemyslaw
通讯作者：
Kazienko, Przemyslaw