熵是系统能量分布均匀性的度量，表示物体所处状态是否稳定

是系统能量分布均匀性的一种度量，可以表示物体所处状态是否稳定及系统变化的方向。
2
能量分布越均匀，熵越大；反之，则熵越小



信息理论及网络优化方法在复杂网络研究中的一个应用
王 冰1,2 唐焕文1,2 修志龙3
1大连理工大学应用数学系 2大连理工大学计算生物学和生物信息学研究所
3 大连理工大学环境与生命学院生物工程系 辽宁 大连 116024
摘要 信息理论在复杂网络的研究中已经得到了广泛的应用，运用信息熵能够按照网络的度分布是否均匀来描述不同的网络类型。本文在此基础上引入多信息源比较的信息熵方法从网络度分布的均匀性角度定量地描述多个网络之间的结构差异程度，计算出现实网络与最优网络之间的离散程度，研究网络的设计是否优化、合理。本文以代谢网络为例，通过计算代谢网络和同等条件下的最优网络之间的信息熵，得到了二者之间的离散程度。我们发现代谢网络是在偏重节点之间平均最短路径长度最小的目标下的最优网络。这一结果解释了代谢网络的“小世界”特性和生物代谢网络设计的最优性原理。
关键词 复杂网络;无尺度网络;网络优化;信息熵
中图分类号：N94 文献标识码：A
One Application of Information Theory and network optimization in Complex Network Research
Wang Bing1,2 Tang Huanwen1,2 Xiu Zhilong3
1Department of Applied Mathematics, Dalian University of Technology
2 Computational Biology and Bioinformatics Institute, Dalian University of Technology
3 School of Environmental and Biological Science and Technology, Dalian University of Technology，Dalian 116024
Abstract: Information theory has been applied in the complex network recently. The definition of information entropy can be used to describe different kinds of networks according to their degree distributions. In this paper the method of information discrepancy among multiple sequences is proposed to describe the discrepancy among different networks，especially to the network that will be checked whether it is an optimal network. To apply with this definition one can compare the discrepancy between real network and optimal network. Taking metabolic network as an example, by comparing the discrepancy between metabolic network and the optimal network, the authors conclude that metabolic network is an optimal network under the object of emphasizing the average shortest path length between nodes, which also shows why metabolic network is a small world network and the optimal design principle in metabolic network.
Key words: complex network; scale-free network; network optimization; information entropy
作者简介:王冰（1978－）,女, e-mail: [e-mail].研究方向：生物信息学。唐焕文（1936－），男，教授，博士生导师，研究方向：优化理论、方法及应用，生物信息学，计算神经科学。修志龙（1965－）,男, 教授，博士生导师，研究方向：微生物发酵非线性动力
1
1引言
现实世界的许多系统可以描述为复杂网络，以系统的元素为顶点，元素之间的相互作用为边就构成了一个网络。如社会网络中的科学家合作网络，信息网络中的，生物网络中的代谢网络等[1,2,3]。近几年，人们经过大量的实证研究发现，这些来自不同领域的大规模网络呈现出共同的规律：网络的度分布服从幂律分布，由于其缺乏一个描述问题的特征尺度而被称为无尺度网络。
无尺度网络的广泛存在促使人们对其展开了深入的研究，并提出了一些新的理论方法。众多学者认为无尺度网络的产生，需要具备两个基本机制：网络的增长和节点之间的择优连接。近来一些学者运用网络优化的方法同样得到了无尺度网络[4,5,6,7]。如Ferrer R等学者通过最小化网络的边数和顶点之间的平均最短路径长度获得了无尺度网络[4]。
信息论中的一些概念方法也逐渐被许多学者引入到复杂网络的研究中。熵最初是作为一个热力学概念而引入的，作为系统无序的度量，熵由于其独特的内涵和渗透力被广泛应用。近来，熵作为描述复杂系统结构的物理量，在复杂系统理论中受到越来越多的关注，成为研究复杂系统的一个重要工具。Ferrer R等学者运用网络优化方法得到了最优网络，通过计算网络度分布的熵值，发现不同类型的网络其熵值呈现明显的不同[4]。文[8]中引入网络结构熵的概念来研究复杂网络的非标度性。
度分布的特征是描述网络的重要几何性质，利用熵的概念可以描述一个网络的度分布所带来信息的不确定程度。那么如何度量不同类型的多个网络之间的离散程度呢？本文在文[4]和文[8]的基础上，引入多信息源比较的信息熵方法。多信息源比较的信息离散度量方法——FDOD（Function Degree of Discrepancy）方法是中科院方伟武教授在改进其它度量多信息源之间离散程度的方法基础上提出的一个新的函数[9,10]。与传统的信息离散度量方法相比，该函数具有一些很好的数学性质，已经成功地应用于DNA多序列的比较分析，蛋白质结构预测[11]，生物进化等领域[12]。
生物网络是后基因组时代研究的一个重要内容，研究表明生物功能的完成不是某个基因与蛋白质的单独作用，而是成组地通过网状的交互作用影响生物系统的功能。因此，需要以系统的观点研究生物网络的结构组成对生物功能的影响。本文先回顾信息熵的概念，然后引入多信息源信息熵的概念，最后给出一个应用实例，计算生物代谢网络和相同顶点总数条件下的最优网络之间的信息熵，研究代谢网络和最优网络之间的离散程度。
2信息熵和FDOD函数
熵是系统能量分布均匀性的一种度量，可以表示物体所处状态是否稳定及系统变化的方向。
2
能量分布越均匀，熵越大；反之，则熵越小[13]。最早的香农熵定义为： 1
1
( )log ( )
N
k
H pk pk
−
=
= −Σ
（1） ()pk
其中，表示度为k的顶点个数占所有顶点总数的比例，即网络的度分布, N为网络的顶点总数，熵H就表示网络度分布信息所带来的不确定程度。
对于网络来说，表示网络的度分布，则信息熵就能依据网络的度分布是否均匀来区分不同的网络，如无尺度网络、星型网络和完备连接网络等，见图1。从图1中可以看出，网络的度分布越均匀，网络的熵值越大；相反，度分布不均匀的网络如星型网络、无尺度网络，其熵值很小。度分布是区分网络类型的一个重要几何量，因此结合度分布的信息利用信息熵的概念能够很好地区分不同的网络类型。那么，给定一个网络，如何描述该网络和其它类型网络之间的关系呢？多信息源比较的信息熵方法为解决这一问题提供了有力工具。方伟武教授提出的改进的信息离散度量方法——FDOD方法是一种新的度量多个信息源之间离散程度的方法，详见文[9,10]。s个分布的信息熵定义如下： p(k)
1
1 1
1
( )
( )log
( )/
s N
j
j s
j k j j
p k
H p k
p k s
−
= =
=
= −ΣΣ
Σ
H slogs
（2）
其中，代表第j条序列度为k的概率。同时，s个分布存在最大信息熵值，定义如下：
)(kpj
max=
（3）
为便于计算，通常把信息熵单位化，得到如下结果： max
B
H
=
B ∈[0,1
H
（4） ]
。一般地，用B值来描述不同信息源之间的离散程度。
图1 随着权重λ 的增加，信息熵及网络类型的变化，A是指数型网络；B无尺度网络；B’是介于B和C之间的网络；C星型网络。网络的度分布越不均匀，信息熵值 H(λ ) 越小。本图取自文[4]。
3
3应用实例——代谢网络
3.1代谢网络图的表示
代谢网络是包含大量底物以及底物之间在酶的催化下相互作用的复杂网络。研究表明代谢网络具有“小世界”特性，即平均最短路径长度很小，集聚系数较大[14]。代谢网络中的糖酵解途径是大多数生物中普遍存在的基本代谢途径，具有一定的代表意义。因此这里我们以糖酵解途径为例讨论代谢网络的结构是否是一个最优结构。
代谢网络中把底物或产物看成是图的顶点，催化反应的酶看成是图的边，就构成了一个数学意义上的图。为了方便计算，我们把代谢网络图看成是无向图。其中代谢网络的数据取自E.coli在无氧条件下的代谢反应网络[15]，包含了在该条件下发生的化学反应方程式。底物A在酶E催化下生成产物B，则图中顶点A，B之间有连接。对于参加多个反应的代谢物ATP、ADP、NAD，去除这些顶点以及相关的边。图中顶点总数N＝37。
3.2优化目标
代谢网络中从任意底物A到底物B所经过的平均反应步数就对应着图中任意一对顶点之间的平均最短路径长度。因此，我们利用文[4]中提出的以顶点之间的平均最短路径长度和网络中的边数为目标函数，研究N个顶点的初始图在该目标函数下的最优图的性质。这两个目标描述了网络的两个方面：顶点之间物理连接的费用和顶点之间信息传递的效率，在现实网络研究中具有普遍的意义。对于该多目标优化问题，采用线性加权法把该问题转化为包含权重λ 的单目标优化问题。目标函数定义如下[2]：
e d f ) 1 ( λ λ − + =
∈[0,1]
（5）
其中λ 为权重。d为单位化的网络的平均最短路径长度，定义为： max D
d = D
2N
i j
ij
C
D
D
Σ = ij D
其中,是指顶点i和顶点j之间的最短路径长度，则D为网络中节点之间的平均最短路径长度， max
1
3
D N
+
= ，N为网络的节点总数。
2N
i j
ij
C
e ⎩ ⎨ ⎧
=
否则
如果 ， 有边
0
1 i j
ij a
( ) ij N N A a ×
aΣ,
e为网络中实际存在的边数占所有可能边数的比例，网络的邻接矩阵 = 。约束条件为
4
图G是连通图。
对于不同权重
λ，形成了不同的目标函数。特别地， 1 λ = 时，目标函数是忽略网络中边的数量而使网络中顶点之间的平均最短路径长度最小，此时 d＝1，网络的连接边数最多，是一个完备图。当
0λ=时，目标函数是不计网络中节点之间的平均最短路径长度的大小而使网络中的边数最少。这里，由于我们要求图是一个连通图以保证任意一对节点之间的最短路径长度都是一个有限数。因此，当 λ = 0 N −1 时，对于N个顶点的连通图所需的最少边数是，形成树形结构。
3.3优化算法
对于上述组合优化问题，我们利用进化规划方法研究N个顶点的初始图分别在不同权重λ 的目标函数下演化形成的最优图，并利用信息离散度量方法研究代谢网络和最优网络之间的离散程度。λ 分别取为[0区间的十等分点。
,1]
图的存储结构采用链表存储，这种存储形式避免了邻接矩阵存储占用内存空间大的缺点。具体算法如下：
步1 初始化 给定m个具有N个顶点，E条边的初始随机图G { , } 1 2 m g …
,,gg = ，约束条件：图是连通的，计算每个图的目标函数值，记为：{。令t。 ( ), ( ), , ( )} 1 2 f t f t f t … m = 0
g (t) i N N A × ij
g (t) i+m 1,2,…,m
步2 变异 对图变异，邻接矩阵中的元素a由1变为0，或者相反。得到m个新图，（i
=）。
步3 计算新个体，（）的目标函数值{。 g (t) i+m i = 1,2,…,m ( ), ( ), , ( )} 1 2 2 f t f t f t m+ m+ … m
1 2 m m+1 2m g g ,…,g ,g ,…,g }
( 1) +
步4 选择 从2m个个体{,中选择m个函数值较小的图，构成下一次迭代的初始图，记为
)}1(,),1(),1({21++ t + = t … m
*
1
=arg m t+1)}
≺
g*
t = t +1,
gtgtgG，令.
in{(jjmgf≤
步5 终止准则 判别是否满足终止准则。若满足，则计算结束，输出最优图；否则，令返回步2。
)1(+tG
3.4结果讨论
对于每个权重λ ，分别计算50次得到了相应的最优网络。通常，描述网络的特征指标包括网络的度分布、平均最短路径长度、平均集聚系数等。由于本例中顶点总数较少，网络的度分布不具有明显的统计特征，因此没有统计度的分布规律。图2中给出了最优图的平均最短路径长度、
5
λ
平均集聚系数随变化的曲线图。由图2可以看到，平均最短路径长度d随着权重λ 的增加而减小。图的平均集聚系数c随着λ 的增加，有略递增的趋势。这可以解释为随着λ 的增加，目标函数偏重顶点之间的平均最短路径长度而忽略边的数量，因此边的数量是增加的，使得顶点的邻接点之间出现边的可能性增加。但当 λ = 0.5时，形成了星形网络。星形网络的特点是每个结点都和一个中心结点连接，此时c。 ≈ 0
图2 平均最短路径长度、集聚系数随λ 变化图 λ = 0.4 ~ 0.6
计算不同λ 得到的最优图的信息熵，结果见图3。在之间，网络结构是星形网络，此时网络中除中心节点度达到N－1，其它节点度为1，网络不均匀，网络的自信息熵很小。图3与文[4]中的结果（本文中的图1）比较一致。
图3 自信息熵随λ 变化图 λ = 0.8
计算代谢网络和最优网络之间的信息熵，结果见图4。由图4可以看出，代谢网络和对应的最优图之间的信息熵值最小。观察网络的演化，可以看到随着λ 的不断增加，目标函数逐渐偏重顶点之间的平均最短路径长度最小，因此图的结构由边数最少的树形结构（ λ = 0 ）逐渐添加边数，逐渐形成星形网络（
0.4λ=）。当λ 继续增加时，除中心节点外的其它节点之间形成连接以减少顶点之间的最短路径长度（ λ = 0.7 λ = 0.8 ），当时，形成了带有中心节点的稠密网络。代谢网络不同于 λ = 0 λ = 0.5 的树形结构，也不同于的星形结构。因此，从网络的结构类型来看，代谢网络和权重为 λ = 0.8 λ = 1 下的最优图最相似。当时，最优图达到了最短路径长度d，而代谢网络的平均最短路径长度为2.77628，因此并不是完全依赖于目标是最 = 1
6
λ = 1
小化顶点之间的平均路径长度的最优图，同时对应的最优图是N个顶点的完备图，需要最多的边数。此时，代谢网络中的任何一对反应物之间都需要酶催化，需要最多数量的酶，这与实际情况不相符合。因此总体上，代谢网络是偏重顶点之间平均最短路径长度最小的目标的最优图，保证了多数反应3步到达，实现了反应物之间的快速转换。这与Wagner,D.等学者对代谢网络的分析中得到了代谢网络的小世界特性的结论是一样的。正如其所述，代谢网络需要对外界环境的变化所引起的酶浓度的变化或代谢物浓度的变化做出快速反应。代谢网络是连通的，其中的每一组分都会被扰动影响而传播到整个网络，使得网络整体通过达到一个新的代谢状态来适应外部环境。因此代谢网络的小世界特性允许整个网络做出快速反应达到新的代谢水平[14]。
图4 代谢网络数据和最优图之间的信息熵随λ 变化图
4结束语
本文将多信息源比较的信息离散度量方法——FDOD方法引入复杂系统的研究中，比较不同网络之间度分布所带来信息的离散程度。以代谢网络为例，比较了代谢网络和最优网络之间的离散程度，得到了代谢网络是在偏重顶点之间的平均最短路径长度最小的目标下的一个最优网络，解释了代谢网络平均最短路径长度较小的“小世界”特性。自然，我们的研究还存在一些局限性，由于计算最优网络时涉及到计算的复杂度问题，我们处理问题的数据规模比较小，只是以大多数生物都具有的保守代谢途径——糖酵解途径为例，探讨了信息离散度量方法在复杂网络研究中的应用。
参考文献
1.Albert,R ,Barabási,A.L.. Statistical mechanics of complex networks. Reviews of modern physics. 2002,74:47-97.
2. Newman M.E.J.. The structure and function of complex networks. SIAM Review.2003, 45,167-256.
3. Dorogovtsev S. N.,J. F. F. Mendes. Evolution of networks. Advances in Physics. 7
2002,51(4):1079-1187.
4. Ferrer R, Solé, R.V.. Optimization in complex networks. Lecture Notes in Physics.2003,625:114-126
5. Paul1, G.a, Tanizawa T., Havlin S., et al. Optimization of robustness of complex networks. The European Physical Journal B.2004,38(2),187-191
6.Valverde,S.,Ferrer,R.V..Scale-free networks from optimal design. Europhysics letters.2002,60(4),512-517.
7. Venkatasubramanian V, Katare S, Patkar P.R.,et al. Spontaneous emergence of complex optimal networks through evolutionary adaptation. Computers and Chemical Engineering, 2004,28(9):1789-1798.
8.谭跃进,吴俊.网络结构熵及其在非标度网络中的应用.系统工程理论与实践，2004,24(6):1-3.
9.Fang Weiwu, Roberts F S, Ma Zhengrong. A measure of discrepancy of multiple sequences. Information Sciences, 2001,137(1): 75-102
10.Fang Weiwu. The characterization of a measure of information discrepancy Information Sciences, 2000,125(1): 207-232
11. Jin LX, Fang WW, Tang HW. Prediction of protein structural classes by a new measure of information discrepancy. Computational Biology and Chemistry, 2003, 27(3): 373-380
12.张立震，唐焕文.一种基于子序列分布的蛋白质结构类预测方法 计算机与应用化学,2003,23(2):1-6
13.阎长俊,王启家,初长庚. 系统和熵. 沈阳建筑工程学院学报,1997,13(2): 213-216.
14.Wagner ,A,Fell D. The small world inside large metabolic networks. Proceedings of Royal Society London Ser B,2001,280: 1803-1810.
15.Pramanik J., Keasling J. D.. Stoichiometric model of Escherichia coli metabolism: incorporation of growth-rate dependent biomass composition and mechanistic energy requirements. Biotechnology and Bioengineering, 1997,56(4):398-421
8