第19卷 第1期 中 国 水 运 Vol.19 No.1 2019年 1月 China Water Transport January 2019
收稿日期：2018-09-20
作者简介：杨 洋（1994-），女，江苏人，上海理工大学 管理学院，硕士生，从事复杂网络研究。 基于Tsallis 熵的网络比对
杨 洋
（上海理工大学 管理学院，上海 200093）
摘 要：本文优化了一种网络比对的算法NND（network node dispersion），该算法基于Tsallis 熵，并通过网络肖像表示不同网络的特征，该算法主要包括两个部分，Tsallis 熵和网络节点距离分布，两个部分均给出了具体的操作步骤。算法经过试验仿真，通过合理设置Tsallis 熵的非广延程度指数q，以NW 小世界网络为例，得出可以区分不同网络拓扑结构的最优非广延程度指数q 值。该算法可以满足不同拓扑结构的网络进行差异比对，实验结果表明，当q=2.1时，实现的算法可以更精确的区分不同拓扑结构的网络。 关键词：复杂网络；网络比对；Tsallis 熵；小世界 中图分类号：F830 文献标识码：A 文章编号：1006-7973（2019）01-0080-03
一、绪论
复杂系统由多个彼此相关的元素组成，可以用复杂网络描述，其中节点是元素而边是元素之间的复杂关系[1-3]。图论的基本概念首先被用于描述复杂网络结构性质[4]。复杂网络的模体是几个节点形成的花样结构，其在网络上出现的频数显著高于在随机化后网络中出现的频数。如果网络在不同尺度上统计性质相似，网络被定义为具有分形结构。总之，人们已经发展出一套指标体系来描述复杂网络结构性质[5-7]。
为了深入地认识复杂网络形成机制，人们发展起来了诸多模型，用以重现复杂网络的结构特征，如小世界网络和无尺度网络等。但是，这些模型只是为了重现某一个或者几个结构特征（如度分布）而设计的。真正准确完整地把握网络形成机制，则需要综合考虑网络的不同尺度上的结构特征，把模型产生的网络与现实中的网络进行系统的比较。
文献中给出了一些复杂网络比较的方法[8]，如统计Motif 的分布和采用小图（graphlet）重新表述网络结构等。最近Tiago 等提出了网络节点散度的概念（network node dispersion，本文记为NND [9]）。其核心思想是，某从节点出发通过指定跳跃能达到的所有节点的个数，称为该节点的多阶度。统计具有每一指定多阶度值的节点个数，得到多阶度分布函数。一个网络可以用不同阶数的度分布来表征，称为网络结构画像。计算两个网络的每一个阶度分布的互熵，其平均值作为网络结构差异的度量。
这一方法可以很好地描述大量网络之间的差异，但是也存在一些问题。首先，复杂网络各阶度分布中总是存在相当数量很小的概率值，这些会对计算结构带来涨落；在熵定义中各个概率的贡献等权重地进行了平均，把网络结构差异最明显的部分平均掉了。为此，本文中我们提出采用Tsallis 熵的方法，给不同概率成分以不同的权重，从而凸现出复杂网络具体的差异。作为算例，我们考察小世界网络模型产生的网络与规则网络的差。随着重连概率的增加，采用香农熵
计算的结果虽然整体趋势上逐渐增大，但是局部存在着明显的涨落，识别差异的精度不够。Tsallis 熵能显著地提高识别差异的精度。
二、方法和材料 1．NW 小世界模型
D.J.Watts 和S.H.Strogatz 于1998年首次提出并从数学上定义了小世界概念，小世界网络是介于随机网络和规则网络中间形态，兼具随机网络低平均路径长度和规则网络高聚类系数等特性，可以描述复杂网络中普遍存在的一个性质，也就是节点间平均距离很小，并且以正比于网络规模的对数缓慢地增加[10]。具体构造规则为：
（1）首先构造规则格点网络。把一维格点链首尾相接，每个节点与d 个最近邻格点相连，得到每个节点度为2d 的规则网络；
（2）出规则网络中任何两个格点形成的格点对，如果两者之间没有连边，以概率r 在这两个格点之间建立一条边；
（3）遍历所有的格点对，操作上一步骤，得到一个小世界网络。格点就是节点，格点之间的链接就是边，格点个数N 就是网络的规模，建立连边概率r 称为重连概率。
2．复杂网络的画像
我们考虑以节点的距离概率分布函数为元素的向量，而不是使用元素是数字的向量，这样可以执行高度精确的比较[11-12]
。每个节点i 的距离的概率分布函数为P i ={P i (j），()
i p j 表示与节点i 距离为j 的节点个数占所有节点的比例[13]。节
点距离分布的集合{P 1，P 2，P 3…P N } 就包含了网络拓扑结构的细节信息。从这个集合中，我们就可以推导出网络的度分布、网络距离分布和其他网络的特征，因此Pi 比度分布和网络距离分布等单一指标包含更多的信息，进行网络比对时，也能够更加精确的区分不同拓扑结构的网络。
3．网络间相似性的Tsallis 熵方法
1988年巴西物理学家 ConstantinoTsallis 提出了一
第1期 杨 洋：基于Tsallis 熵的网络比对 81
种含有指数q 的熵表达式[9]，即非广延熵Tsallis 熵S q （指数q 反映了非广延程度），包括广义平均概率的状态并可以平移标度均值[14]。对于离散的概率分布{P i }满足条件∑i P i =1，Tsallis 熵即可定义为：
()(1)
,11
a i i k p Sq q q -=
≠-∑
NND 是一个测量图G 在连通性距离上的异质性度量。当一个网络图具有高度多样性的节点-距离模式，则它具有较高的NND 值，我们就可以限定它为异构网络。原始的NND 算法基于香农熵来度量网络间的差异性。本文优化的 NND 算法基于Tsallis 熵，通过绘制出网络节点的距离分布{P 1，P 2，P 3…P n }，计算所有节点距离分布的Tsallis 熵之和。
()
()
()11q
ij ij N p NND =
cielabq N q -≠-∑
三、结果 1．小世界网络镜片镀膜机
采用小世界模型构建网络，取N=500，d=2。图1可以看出，未优化的NND 值在不同重连概率p 的影响
下，虽然有波动，但波动毫无规律可循，无法准确根据NND 的取值来判断基于不同重连概率p 下小世界网络的差异。图2可以看出. FaxianTsallis 熵的NND 值q 越小，NND 差值越大，随着q 的增加，差值逐渐变小，图3可以看出，随着重连概率p 的增加，网络不规则性增加，因此NND 值不断减小，当q<2.1时，虽NND 变化明显，但其呈现的非线性关系不能准确判别不同重连概率下NW 小世界网络的差异，当q=2.1时，NND 与重连概率p 有明显的线性关系且此时NND 差异大于q> 2.1的情况，因此q=2.1时的NND 可以用来量化不同重连概率p 下小世界网络的差异，更好的区分不同拓
扑结构的网络。
图1 优化前，小世界网络的NND
线性驱动器分布情况
图2 优化后，不同重连概率p 的条件下，NND 随q
的变化
图3 优化后，小世界网络的NND 分布情况 2．3个不同拓扑结构的网络
使用3个带有9个节点和9个连接的网络（图4），表示不同的拓扑结构。3个网络有明显不同的拓扑结
构，其中N1没有断开链接，N2有一个断开连接的节点，N3分割成3个部分。通过两种常用的描述距离的方法：加权平均[15]和图编辑距离[16]，以及优化前和优化后的NND 算法，我们明显可以看出，加权平均和图编辑距离无法显示它们之间相关的拓扑差异，返回了相同的距离值，加全平均为12，图编辑距离为6，完全忽略了N2一个节点断开连接和N3完全断开的情况，优化前的NND 则可以区分3个网络间的差异，不过通过对比优化后的NND，优化后Tsallis 熵在q=2.1情况下的NND 不仅可以区分不同拓扑结构网络间的差异，并且优化后的NND 相比于优化前的NND 在数值上能更大程度上的
区分N1、N2、N3间的差异，也就是NND 差值更加显著。
图4 3个带有不同拓扑结构的网络图 表1 4种网络比对方法的比较
网络 加全平均
图编辑距离
NND（优化前）
NND（优化后）
(N1，N2） 12 6 0.039 0.1181 (N1，N3）
12 6 0.142 0.1875 (N2，N3）
12
6
0.181
0.3056
（下转第84页）
84 中 国 水 运 第19卷
体内容如表6所示。其中集卡路线S
1i →k→m→S
2j
表示集卡
从进口船舶i号贝位装载对应集装箱，行进至k号进口箱区，然后行进至m号出口箱区装载对应集装箱，转运至出口船舶对应的j号贝位。
表6 集卡运输路径及运送量
路径号 集卡路线 装载量（TEU） 卸载量（TEU）
1 S11→5→4→S23 60 60
2 S11→5→2→S2240 40
3 S12→3→4→S2360 60
4 S12→1→5→S2450 50
5 S13→2→1→S2360 60
6 S13→1→3→S2230 30
7 S14→3→5→S2150 50
8 S14→2→2→S2220 20
9 S14→4→3→S2180 80
10 S15→4→2→S2360 60
11 S15→3→1→S2540 40
12 S15→4→5→S2420 20
可以发现，在保证运输过程中岸桥所用时间、场桥所用时间、集卡水平运输所用时间三阶段总时间最小的前提下，采用“作业面”运输模式来提高集卡的满载行驶率，可很大程度上降低集卡因“作业线”模式下大量空载行驶造成的资源浪费情况。
五、结语
本文考虑船舶贝位及出口箱区部分集装箱需按指定路线进行运送的前提下，研究“作业面”运输模式下的集卡调度问题，使集卡及场桥、岸桥运行总时间最短。研究表明采用“作业面”运输模式可以提高集卡的满载行驶率，降低集卡因“作业线”模式下大量空载行驶造成的资源浪费情况，并对集装箱的转运路径及装卸量形成初步规划，为提高集装箱码头运行效率提供了一定的参考价值。
参考文献
[1] 丁荣涛.基于协作能力约束的港口集卡调度优化策略[J].
清华大学学报（自然科学版），2012，（8）：1158-1164.
[2] 曾庆成.集装箱码头同贝同步装卸调度模型与算法[J].交
通运输工程学报，2010，（1）：88-93.
[3] 计明军，靳志宏.集装箱码头集卡与岸桥协调调度优化[J].
复旦学报（自然科学版），2007，46（4）：60-72. [4] 赵金楼，黄金虎，刘馨.集装箱码头的集卡两阶段路径优
化研究[J].中国管理科学，2017，（4）：152-157.
[5] Savaskan RC，Bhattacharya S，Van L Wassenhove. Closedloop
supply chain models with product remanufacturing [J].Management Science，2004，50（2）：239-253. [6] HaghaniA，Kaisar EI. A model for designing container loading
plans for containership[J].Working paper，University of Maryland，Transportation Research Board 2
001 Annual meeting，2001：35-42.
[7] Kim KH. A crane scheduling method for port container
terminals[J].European Journal of Operational Research，2004，156（3）：752-76.
（上接第81页）
四、讨论
随着近几年越来越多的人开始研究复杂网络，将其运用于社会科学、医学、生物学以及物理学的网络，传统的对网络结构特征描述已经不能满足我们的区分不同网络拓扑结构的需要，本文提出的方法是一种网络间相似性的Tsallis熵方法，通过网络肖像的方法将度分布和网络距离分布等特征收集起来，并通过计算Tsallis来可以识别并量化拓扑结构上的差异，相比于网络间相似性的香农熵算法，本方法可以通过调节Tsallis熵的q值，使得不同拓扑结构网络间的差异具有可度量性。
参考文献
[1] 汪小帆，李翔，陈关荣.复杂网络理论及其应用[M].北京：
清华大学出版社，2006.
实验室用振荡器
[2] D. conte，P. foggia，C. sansone，et al. Thirty years of graph matching看门狗电路
in pattern recognition[J].International Journal of Pattern Recognition & Artificial Intelligence，2008，18（03）：265-298.
[3] 汪秉宏，周涛，何大韧.统计物理与复杂系统研究最近发
静压测试
展趋势分析[J].中国基础科学，2005，7（3）：37-43. [4] Arenas，A. et al. Synchronization in complex networks[J].Phys.
Rep.2008，（469）：93–153.
[5] Taylor，D. et al. Topological data analysis of contagion maps
for examining spreading processes on networks[J].Nat.
Commun，2015，（6）：7723.
[6] Boccaletti，S.et al. Complex networks：structure and
dynamics[J].Phys. Rep. 2006，（424）：175–308.
[7] Kelmans A K. Comparison of graphs by their number of
spanning trees [J].Discrete Mathematics，1976，16（3）：241-261.
[8] Arenas，A. et al. Synchronization in complex networks[J].Phys.
Rep. 2008，（469）：93–153.
[9] Tiago A，Laura Carpi，Albert. Quantfication of network structural
dissimilarities[J].Nature Communications，2017，（09）. [10] Watts DJ，Strogatz SH. Collectivedynamics of ’small-
world’ networks[J].Nature. 1998，393 （6684）：440-442.
[11] Fernandez，M. L. &Valiente，G. A graph distance metric
combining maximum common subgraph and minimum common supergraph[J].Pattern. Recogn. Lett，2001，（22）：753–758. [12] Gao，X.，Xiao，B.，Tao，D. & Li，X. A survey of graph
edit distance[J].Pattern Anal. Appl，2010，（13）：113–129.
[13] Bagrow J P，Bollt E M，Skufca J D，et al. Portraits of Complex
Networks[J].Epl，2007，81（81）：68004.
[14] 曹克非，王参军.Tsallis熵与非广延统计力学[J].云南大学
学报（自然科学版），2005，27（6）：514-520.
[15] Hamming，R. W. Binary codes capable of correctingdeleti
ons[J].insertions，and reversals，1950，（10）：147–160.
[16] Sanfeliu，A. & Fu，K. S. A distance measure between
attributed relational graphs for pattern recognition[J].IEEE T.
Syst. Man Cyb. 1983，13（3）：353–363.
