Offdiagonal complexity: A computationally quick complexity measure for graphs and networks
Offdiagonal complexity: A computationally quick complexity measure for graphs and networks
复制标题
DOI：
10.1016/j.physa.2006.08.067
复制
发表时间：
2007-02-15
影响因子：
3.3
通讯作者：
Claussen, Jens Christian
中科院分区：
文献类型：
--
作者：
Claussen, Jens Christian
各种各样的生物、社会和经济网络的拓扑结构与随机图有很大不同。然而，从概念的角度来看，定量表征仍然不能令人满意。受小规模无标度网络讨论的启发，定义了有偏链路分布熵，它采用幂律分布的极值。该方法扩展到节点到节点链接交叉分布，其非对角元素表征了链接分布、聚类系数和平均路径长度之外的图结构。从这里可以定义一个简单（且计算成本低）的复杂性度量。这种非对角复杂性（OdC）被提出作为一种新颖的度量来表征无向图或网络的复杂性。虽然对于规则格子和完全连接的网络，OdC 都为零，但对于随机图，它的值相当低，而对于无标度网络和分层树等明显复杂的结构，它显示出较高的值。 OdC 方法应用于幽门螺杆菌蛋白质相互作用网络和随机重新连接的替代物。 (c) 2006 年，Elsevier B.V. 出版
A vast variety of biological, social, and economical networks shows topologies drastically differing from random graphs; yet the quantitative characterization remains unsatisfactory from a conceptual point of view. Motivated from the discussion of small scale-free networks, a biased link distribution entropy is defined, which takes an extremum for a power-law distribution. This approach is extended to the node-node link cross-distribution, whose nondiagonal elements characterize the graph structure beyond link distribution, cluster coefficient and average path length. From here a simple (and computationally cheap) complexity measure can be defined. This offdiagonal complexity (OdC) is proposed as a novel measure to characterize the complexity of an undirected graph, or network. While both for regular lattices and fully connected networks OdC is zero, it takes a moderately low value for a random graph and shows high values for apparently complex structures as scale-free networks and hierarchical trees. The OdC approach is applied to the Helicobacter pylori protein interaction network and randomly rewired surrogates. (c) 2006 Published by Elsevier B.V.