Tee Philip, Parisis George, Berthouze Luc, Wakeman Ian
Moogsoft Inc, San Francisco, CA 94111, USA.
School of Engineering and Informatics, University of Sussex, BN1 9RH Brighton, UK.
Entropy (Basel). 2018 Jun 21;20(7):481. doi: 10.3390/e20070481.
Combinatoric measures of entropy capture the complexity of a graph but rely upon the calculation of its independent sets, or collections of non-adjacent vertices. This decomposition of the vertex set is a known NP-Complete problem and for most real world graphs is an inaccessible calculation. Recent work by Dehmer et al. and Tee et al. identified a number of vertex level measures that do not suffer from this pathological computational complexity, but that can be shown to be effective at quantifying graph complexity. In this paper, we consider whether these local measures are fundamentally equivalent to global entropy measures. Specifically, we investigate the existence of a correlation between vertex level and global measures of entropy for a narrow subset of random graphs. We use the greedy algorithm approximation for calculating the chromatic information and therefore Körner entropy. We are able to demonstrate strong correlation for this subset of graphs and outline how this may arise theoretically.
熵的组合度量捕捉了图的复杂性，但依赖于其独立集或非相邻顶点集合的计算。顶点集的这种分解是一个已知的NP完全问题，对于大多数实际世界的图来说是难以进行的计算。德默尔等人和蒂等人最近的工作确定了一些顶点级度量，这些度量不会受到这种病态计算复杂性的影响，但可以证明在量化图的复杂性方面是有效的。在本文中，我们考虑这些局部度量是否从根本上等同于全局熵度量。具体来说，我们研究了随机图的一个窄子集的顶点级熵度量和全局熵度量之间相关性的存在情况。我们使用贪心算法近似来计算色信息，从而计算科纳熵。我们能够证明该图子集的强相关性，并概述这种相关性在理论上可能是如何产生的。
