复杂网络电输运性能与通信序列熵之间的关联*

陈单 石丹丹 潘贵军

(湖北大学物理与电子科学学院,武汉 430062)

1 引 言

21世纪初网络科学的出现极大地推动了复杂系统的跨学科研究.随着人类认知能力的提升,发现在每个系统背后都有一个网络,它对系统各部分之间的交互进行编码[1−4].例如: 编码基因、蛋白质和代谢物之间相互作用的网络将这些成分整合到活细胞中[3]; 捕捉神经元之间连接的接线图,称为神经网络,是理解大脑如何运作和思考的关键[4].这些网络大多表现出高度的复杂性,如连接结构的复杂性、节点类型的复杂性和网络演化过程的复杂性[5]等.此外,网络还具有小世界性质[6]、无标度性质[7]和模块性质[8,9].这些特征足以说明,网络不仅具有不断变化的内容和形式,而且具有更加复杂的连接结构.

网络结构与动力学的关系决定了基于网络的复杂系统的行为,其中一个核心问题是,在给定约束条件下如何设计网络结构来优化其功能,诸如网络上的同步优化[5]、扩散动力学优化[8]、导航优化[10−15]以及电输运性能优化[16−22]等.特别地,通过向基础地理网络添加远程连接可以优化网络中的信息和能量传输[12,13],这意味着合理的设计网络可以使网络中的信息高效地从源流向目标.另外,当从信息的角度去看待系统时,以香农熵为背景的信息理论工具已经成功应用于许多领域.熵作为一种有效度量系统信息的指标,以其独特的内涵应用于统计物理、信息论以及其他广义系统,已成为复杂系统研究的重要工具[23].在网络科学领域,从香农信息理论工具的角度去观察网络对于理解网络结构和动力学之间的关系是非常有益的.

Hu等[24]将熵用于解释小世界网络中有效导航标度律的可能起源.李勇军等[25]提出基于最大熵模型的链路预测算法,该方法在预测链路时避免了特征之间相互独立的约束.此外,熵也被用作衡量网络异质性的重要指标[26].例如: Wang等[27]认为度分布熵可以作为表征网络异质性的测度; 吴俊等[28]以节点的相对度值为指标,定义相对度分布熵来衡量网络的异质性.上述两种熵只关注“节点”和“边”在网络结构中的单一作用,在全局特征描述上存在不足[23].蔡萌等[29]通过引入综合考虑径向测度和中间测度的网络流概念,提出了流介数结构熵.最近,Cai等[30]综合分析了之前的几种熵,指出流介数结构熵能够有效地表征复杂网络的异质性.从以上的这些熵中可以发现一个共同的特点: 它们主要是基于描述网络某一局部特征而构建的概率分布熵,忽略了网络的其他信息,所以不能很好地表征网络的整体拓扑信息,进而就不能有效地分析它们与网络功能之间的关系.为此,寻求可以描述网络整体信息的概率分布是极其重要的.Braunstein等[31]利用缩放的拉普拉斯矩阵的谱定义了一种新的熵,打破了传统分布熵的局限性.特别地,最近de Domenico 和 Biamonte[32]提出了一套基于谱熵的信息理论工具,用于比较复杂网络.该谱熵相对于传统的分布熵似乎更能反映出网络的整体拓扑信息.另外,Chen等[33]提出了一个表征网络全局通信能力的测度-复杂网络的通信序列熵,基于该测度可以有效地量化网络之间的差异性,证实了通信序列熵是表征网络整体结构信息的有效测度.

在文献[16—22]中已经研究了不同拓扑结构的网络对电输运性能的影响,本文将从信息的角度寻求影响网络电输运性能的关键测度,预测复杂网络的电输运性能与其通信序列熵之间的紧密联系.为了探索这其中的关联,系统地研究了小世界网络、无标度网络、关联无标度网络、有社团结构的网络以及IEEE57等节点网络的通信序列熵和电输运性能之间的关联特性.最终的研究结果表明,对于小世界网络、无标度网络、关联无标度网络、社团网络以及IEEE57等节点网络而言,它们的通信序列熵与电输运性能成正关联.这一发现,对构建高效率的电输运网络具有一定的指导意义,换句话说,可以通过提高网络的通信序列熵来优化它们的电输运性能.

2 方 法

2.1 网络通信序列熵的定义

考虑一个由N个节点和E条边组成的无权无向网络,邻接矩阵用N×N的矩阵A表示,矩阵元素用aij表示.如果节点i和节点j之间直接相连,则aij=1,否则aij=0.为了表征节点间的通信能力,Estrada等[34−36]提出了网络的通信矩阵:

任意一对节点i和j之间的通信能力对应于通信矩阵C第i行j列的元素,即cij.使用特征值分解可以将邻接矩阵分解为A=QΛQ−1,从 而eA=QeΛQ−1,这样便可求出矩阵C的矩阵元,其中Q是一个由标准正交基组成的正交矩阵.

考虑到通信矩阵C的对称性,这里仅将矩阵C对角线上方的元素cij(i

S(P)称 为网络的通信序列熵,这里规定 0 log20:=0.为了消除网络尺寸效应,定义标准熵为

2.2 网络电输运性能的表征

本文为了表征整个网络的电输运性能,利用文献[16—22]采用的方法将网络的所有连边视为电阻并在任意一对节点i和j之间外加电源装置,这样,运用欧姆定律和基尔霍夫定律便可求出节点i和j之间的局部电导Gij,所有节点间的平均全局电导被用来表征网络的电输运性能,即

3 特殊网络的SN与之间关联性的理论研究

接下来将首先对几种特殊网络SN和进行相应的理论研究.

孤立节点网络邻接矩阵A的特征值全为0,eA=I,I是N阶单位矩阵.由于孤立节点网络不同节点之间没有边相连,所以它们之间的通信能力均为 0,每个节点的自通信为 1,通信序列为P={0,···,0},因此通信序列熵SN=0.此外,孤立网络任意一对节点间的局部电导均为 0,故平均电导=0.

完全网络邻接矩阵A有N−1 个特征值等于–1,还有一个特征值是N−1,因此,通信矩阵的对角线元素为cii=(eN+N−1)/(Ne)[36],剩下的非对角元素均相等,即cij,i=j=(eN−1)∑/(Ne).于是,通信矩阵对角线上方元素之和为i

因此可以根据(3)式计算出完全网络的通信序列熵:

由于完全网络中任意一对节点都有直接相连的边,所以通信序列中的元素是相等的,熵是最大的.

不难想象完全网络的平均电导也是最大的.为了证实这一点,这里以三个节点的完全网络来说明任意一对节点之间电导的计算过程.如图1,假定每条边对应一个单位电阻,即R=1,加在任意一对节点之间的是一个单位电流源.

根据并联电路分流定律知I=I1+I2,即有为节点 1 和 2 之间的等效电阻.同理,G13=1.5,G23=1.5.所以平均电导=1.5.以此类推,对于N个节点的完全网络,平均电导如下:

图1 完全网络任意一对节点之间等效电导的计算过程Fig.1.The calculation of equivalent conductance between any pair of nodes in a complete network.

因此,对于一个节点数量为N的网络,有

星型网络邻接矩阵A有两个非零特征值,分别为如果设定中心节点是1,则中心节点的自通信能力为由于任意一个边缘节点到中心节点的距离均为1,所以通信矩阵第一行和第一列的元素均相等,即

对角线上的其余元素也相等,cii=(c11+N−2)/(N−1)(i=2,···,N).不难想象,任意一对边缘节点间的最短路径距离均等于2,因此通信矩阵中剩余元素均等于

于是,星型网络的通信序列为

相应的通信序列熵:

对于星型网络,每条边对应的局部电导均等于1,即G1i=1(i2).当输入输出节点均不为中心节点时,输入节点和输出节点间的局部电导Gij=0.5(i=j=1).因此星型网络的全局平均电导为

因此,对于孤立节点网络、完全网络和星型网络,可以得出如下结论:SN(孤立)

4 复杂网络SN与之间的关联性研究

本节以小世界网络[6]、无标度网络[7]、关联无标度网络、有社团的网络[37]以及IEEE57等节点网络为例研究复杂网络的通信序列熵和电输运性能之间的关联特性.

4.1 小世界与无标度网络

图2 WS 小世界网络的 (a) 通信序列熵 SN 和 (b) 平均全局电导与 重连概率 Prew 的依赖关系; (c),(d) 相应的 SN 与之间的关系Fig.2.Dependence of (a) communicability sequence entropy S N and (b) mean global conductance on rewiring probability of WS small-world network; (c),(d) the relation between SN and of WS small-world network.

在图2(a)和(b)中分别展示了WS小世界网络的通信序列熵SN,平均全局电导与重连概率Prew的关系,其中网络尺寸N=1000,表示网络的平均度.在重连概率Prew从 0 (对应一个完全规则的网络)增加到1 (对应一个完全随机的网络)的过程中,网络的SN和均呈现出增大的趋势.对于较小的Prew,SN和呈现非常缓慢的增长趋势,当Prew近似大于 1 0−2时,SN和都呈现出明显的增长趋势.由此可以得出在网络节点和边一定的情况下,SN(规则)

这里,采用Gao个人网站[38]上的算法生成无标度网络并控制最大节点度kmaxN1/2,以保证不同度分布指数γ下的无标度网络具有相同的平均度,并且使生成的网络近似于无关联网络.进而研究通信序列熵SN,平均全局电导与度分布指数γ的依赖关系.其中网络尺寸N=1000,代表网络的平均度.图3(a)和(b)显示,在严格控制成本后,熵SN随着γ的增大逐渐增大,也随着γ的增大而增大.并且在节点一定的情况下,SN和都 会随着的增大而增大.在文献[16]中已经详细地研究了无标度网络P(k) ～k−γ的电输运性能.在本文中,会 随着γ的增大而增大,而文献[16]恰好显示了一个相反的结果,但这二者并不矛盾,原因是文献[16]并没有严格控制不同度分布指数下的无标度网络具有相同的平均度.在他们的模型中,平均度会随着γ的增大而减小.而我们显示的结果表明在控制不同γ的无标度网络具有相同的平均度这一前提下,将 随着γ的增大而增大.类似地,将与SN映射在同一个坐标系下,从图3(c)和(d)中可以明显地看出二者也成正关联.对于无标度网络,随着度分布指数γ的增大,节点之间的通信能力变得越来越均匀,网络逐渐从有序向无序转变,当γ→ ∞时,网络几乎是一个ER随机网络,此时通信能力变得最均匀,达到最无序的状态,所以SN会随着γ的增大而增大.另一方面,在无标度网络中,由于存在枢纽节点,在电输运模型中,这些节点会影响电输运效率[16].所以当γ逐渐增大时,网络向随机网络演化,度-度异质性变弱,枢纽节点的影响力越来越小,电输运性能不断增强.

图3 无标度网络的 (a) 通信序列熵 SN 和 (b) 平均全局电导与 度分布指数 γ 的依赖关系; (c),(d) 将与 SN 映射在同一坐标系下的结果Fig.3.The dependence of (a) communicability sequence entropy S N and (b) mean global conductance on degree distribution exponent γ of scale-free network; (c),(d) the results of mapping w ith SN in the same coordinate system.

4.2 关联无标度网络

大多数真实网络不仅具有度分布的无标度特性,而且还具有度-度关联特性.实证表明,绝大多数社会网络呈现正关联特性,而自然网络则趋向于负关联特性.常见的衡量网络度相关特性的方法有基于最近邻平均度值knn(k) 的度-度相关性和基于Pearson相关系数r的度-度相关性[39].对于前者,当knn(k) 是 关于k的单调增函数时,表明网络中度大的节点倾向于连接度大的节点,网络是正相关的;当knn(k) 是 关于k的单调减函数时,表明网络中度大的节点倾向于连接度小的节点,网络是负相关的.对于后者,若r>0,网络是正相关的; 若r<0,网络是负相关的; 若r=0,则表明网络中节点的度-度之间不具有相关性.

事实上,Xue等[20]提出了一种通过分类或选型拓扑对无标度网络的传输效率进行调优的方法,阐明无标度网络的独特传输行为是由度分布的异质性造成的,从数值仿真结果发现在无标度网络从异配(负关联)演变到同配(正关联)的过程中,网络的平均全局电导逐渐减小(如图4(b)和(e),度分布指数分别为γ=2.5 和γ=3.0).下面我们将研究关联的无标度网络的通信序列熵和电输运性能之间的关联,其中N=3000,=4.图4(a) 和 (d)分别展示了度分布指数γ=2.5 和γ=3.0 下的SN和度-度关联系数r的依赖关系,结果表明通信序列熵SN呈现出与平均电导类似的变化关系,即SN是关于r的单调递减函数.在文献[40]中,Johnson等通过引入吉布斯函数熵,利用最大熵原理证明了负关联的无标度网络的熵大于无关联的无标度网络的熵,给出了自然网络趋向于负关联特性的一个解释.这里,基于通信序列熵也得出了同样的结论.最后将通信序列熵SN和平均全局电导映射在同一个坐标系下(图4(c)和(f)),可以明显地看出SN与成正关联特性.对于图4(a) 和 (d),可作如下解释: 在无标度网络中由于大量的节点只拥有少量的连边,少部分节点拥有大量的连接.因此,大度节点和大度节点相连,会导致大度节点之间具有更强的通信能力,而大部分小度节点之间的通信能力会较小,导致通信序列中元素的分布变得不均匀.于是网络从异配演变到同配的过程中,通信序列熵会减小.对于电输运性能而言,在同配模型中,大度节点和大度节点相连会导致电输运效率下降,电导减小[20].

图4 度分布指数 γ 分别等于 (a) 2.5 和 (d) 3.0 时的关联无标度网络的通信序列熵 S N 与度-度关联系数 r 的依赖关系; 相应的平均全局电导 与 关联系数 r 的依赖关系,γ 分别等于 (b) 2.5 和 (e) 3.0; (c),(f)与 SN 的关系曲线Fig.4.Dependence of communicability sequence entropy S N of the scale-free network on the degree-degree correlation coefficient r,here,the degree distribution exponent γ is equal to (a) 2.5 and (d) 3.0,respectively; (b),(e) the dependence of the mean global conductance on the correlation coefficient r ; (c),(f) the a nd SN relation curve.

4.3 社团网络

实证研究表明,许多真实网络都含有社团结构,即整个网络由若干个社团组成,每个社团内部之间的节点连接比较紧密,社团之间具有少量的连接.下面研究具有社团结构的网络对通信序列熵和电输运性能的影响.首先,基于文献[37]的算法,以BA网络和ER网络[41]为基础构造具有社团结构的无标度网络和随机网络.以BA网络为例,具体算法如下: 1)按照文献[7]的方法生成一个包含N个节点和E条边的 BA网络; 2)生成a个独立的BA社团网络,每个社团拥有几乎相等的节点和边,在各自独立的集团中随机选取少量的边断开,并将这些断开的边的端点连接到其他社团中断开的边的端点上,组成一个含有a个社团的网络(图5).

分别计算基于BA和ER的同等规模且平均度相同的社团网络的通信序列熵SN,平均电导和社团数量a的关系,相应的数值结果如表1所示.随着网络中社团数量的增加,这两种类型网络的通信序列熵SN和平均电导均逐渐减小.由于社团的存在,其内部的点连接相对稠密,社团之间的连接稀少,这就导致了通信序列中的元素分布不均匀,因而通信序列熵SN变小.社团数量越多,元素分布的不均匀性越强,通信序列熵SN就会越小.另一方面,对于电导而言,社团内部节点之间的局部电导较大,而处在不同社团的节点对之间局部电导较小,然而这些节点对的数量占主导地位,所以平均电导随着社团数量的增加而减小.因此,对于含有社团结构的网络而言,通信序列熵SN和平均电导成正关联特性.

表1 含有社团结构的网络[BA (左),ER (右)]通信序列熵 SN 、平均全局电导与社团个数的关系Table 1.Relationship between communicability sequence entropy SN,mean global conductance and number of communities in networks[BA (left),ER (right)] containing communities.

表1 含有社团结构的网络[BA (左),ER (右)]通信序列熵 SN 、平均全局电导与社团个数的关系Table 1.Relationship between communicability sequence entropy SN,mean global conductance and number of communities in networks[BA (left),ER (right)] containing communities.

ER SN images/BZ_280_721_1206_811_1285.png1(C1) 0.9363 1.9380 1 0.9704 2.2106 2 (C2) 0.8925 1.6168 2 0.9256 1.8006 3 (C3) 0.8703 1.5026 3 0.9010 1.6625 4 (C4) 0.8512 1.4401 4 0.8832 1.5728 5 (C5) 0.8440 1.3929 5 0.8704 1.5203 6 (C6) 0.8409 1.3653 6 0.8642 1.4813 BA SN images/BZ_280_721_1206_811_1285.png

图5 以BA网络为例构建的社团网络可视化图,社团个数为1—6,分别表示为C1—C6.图中每一个网络中社团网络的生成方式都是按照文献[7]的方法生成.网络规模 N=900,网络边数 E ≈2700.具体算法如下: 1)首先生成一个含有900个节点,2700条边的BA网络(图C1); 2)生成两个含有450个节点、1350条边的BA网络,然后在每个社团中随机断开少量的边,并将这些断开的边连接到其他社团中断开的边的端点上,形成一个含有两个社团的网络C2; 3)以此类推,便可生成含有3,4,5,6个社团的 BA 网络 C3,C4,C5,C6Fig.5.A visualization of the community network based on the BA network.The number of communities is 1 to 6,which are denoted as C1 to C6.The generation method of the community network in each network in the figure is generated according to the method of Ref.[7].The network size is N=900,the number of network edges is E ≈2700.The specific algorithm is as follows:1) First,a BA network with 900 nodes and 2700 edges is generated,as shown in figure C1; 2) two BA networks containing 450 nodes and 1350 edges are generated,and then a small number of edges are randomly disconnected in each community,and these disconnected edges are connected to the endpoints of the interrupted edges of other communities to form a network C2 containing two communities; 3) in this way,BA network C3,C4,C5 and C6 containing 3,4,5 and 6 communities can be generated.ntaining 3,4,5 and 6 communities can be generated.

4.4 IEEE57和IEEE118节点网络

最后,以IEEE57节点和IEEE118节点供电网络为例,测试了三个dk随机化参考模型 (d=0,1,2) 以及网络本身的通信序列熵和平均全局电导,结果如表2 所示.这里,d=0 可以保证在随机布线的过程中与原网络具有相同的节点数和边数;d=1可以保证随机布线的过程中与原网络具有相同的节点数和度分布;d=2 则是保证与原网络具有相同节点、度分布和二阶度相关性.显然,阶数d越大,随机化网络模型就越接近原始的网络.随机化参考模型采用文献[42]中的算法生成.结果表明,从0阶模型演化到2阶模型的过程中,通信序列熵和平均电导均逐渐减小,并且都大于原始网络的通信序列熵和平均电导.这是因为在不考虑权重的情况下,0阶模型是最无序的,通信序列元素集中在某个值附近,熵最大.随着阶数的增加,网络逐渐从无序状态转变到有序状态,熵逐渐减小.对于电输运性能而言,真实的网络通常是复杂拓扑结构的共同体,根据前面的研究结论,真实网络的电输运性能比其各阶随机化模型的电输运能力要小是不难理解的.另外可以推测出当随机化模型阶数充分高时,相应的通信序列熵SN和平均电导将无限的接近于原始网络的SN和.因此,可以得出SN和成正关联.需要指出的是,这里讨论的均是无权网络,然而对于真实电气节点网络而言,每条连接都是有权重的,通信序列熵能否有效表征有权重网络的电输运能力是下一步要研究的内容.

表2 电力供需网络以及对应的随机化参考模型的 SN 和平均电导,IEEE57 (左),IEEE118 (右)Table 2.Power supply network and corresponding randomized reference model S N and mean global conductance,IEEE57 (left),IEEE118 (right).

表2 电力供需网络以及对应的随机化参考模型的 SN 和平均电导,IEEE57 (左),IEEE118 (右)Table 2.Power supply network and corresponding randomized reference model S N and mean global conductance,IEEE57 (left),IEEE118 (right).

IEEE57 SN images/BZ_280_721_1206_811_1285.pngIEEE118 SN images/BZ_280_721_1206_811_1285.png0阶 0.8744 0.6404 0阶 0.8884 0.7418 1阶 0.8502 0.6302 1阶 0.8692 0.7388 2阶 0.8391 0.6225 2阶 0.8689 0.7086原始 0.8116 0.5616 原始 0.8029 0.4981

5 结 论

在文献[33]中已经提出了可以基于通信函数[34,35]的通信序列熵来表征网络的整体拓扑信息,并基于该测度比较成功地量化了网络之间的差异性.本文从网络的通信能力这一角度系统地研究了网络的电输运性能与通信序列熵的关联性.首先,通过对孤立节点网络、完全网络和星型网络等特殊网络的通信序列熵SN,电输运性能指标进行相关的理论研究,发现这三种网络的SN大小顺序与的大小顺序是一致的.其次,在聚焦网络成本(节点和边)一定的条件下,研究了小世界网络、无标度网络、关联无标度网络、有社团结构的网络以及IEEE57 等节点网络的SN与之间的关联.研究发现,这些网络的SN与成正关联.具体来讲,从规则网络演变到小世界网络的过程中,网络的SN和都逐渐增大; 对于无标度网络,在度分布指数逐渐增大的过程中,网络的SN和均逐渐增大; 对于度-度关联性改变的无标度网络,从异配演变到同配的过程中,SN和都逐渐减小; 对于含有社团结构的网络,SN和均随着社团数量的增加而减小.最后研究了IEEE57和IEEE118两个经典的节点供电网络以及相应的随机化模型的SN和之间的关联.结果表明,随着随机化模型阶数d的增加,SN和都逐渐减小,并且都越来越接近原始网络的SN和.综上所述,对于以上所研究的网络而言,它们的通信序列熵与电输运性能成正关联.这一发现,为设计高传输效率的电输运网络提供了一个有效的策略,即可以通过提高网络的通信序列熵来优化其电输运性能.值得注意的是,本文寻求出了一个影响电输运性能的关键结构测度,但对于特定网络,并未展开讨论如何改变其结构来提高通信序列熵,进而提升网络的电输运性能,然而,后者在工程实际中却具有更为广泛的应用价值.为此,这些问题有必要在今后的工作中进一步探索.