图论在网络研究中的一些应用

2019-12-23

广州大学学报（自然科学版） 2019年4期

关键词：拓扑图图论标度

(西北师范大学数学与统计学院，甘肃兰州 730070)

数学的拓扑图是编码关系结构的一种自然的表示，这种关系结构在许多领域都会遇到.通过图结构数据定义的计算被广泛应用于各领域，计算生物学和化学的分子分析，自然语言理解的知识图或图结构解析的分析等等.

1 研究背景、术语、定义

1.1 拓扑图是各种学科的通用语言之一

当今世界的数不清的事物关联组合都可以用拓扑图来表示或描绘，拓扑图属于数学的一个叫做图论的分支.图1、图2、图3和图4是拓扑图应用的例子.

图1 拓扑图的例子Fig.1 Examples of topological graphs

(a) 泛着色泛结构拓扑图；(b) 饱和烷烃拓扑图；(c) 物理关联知识拓扑图

图2 英特网络

图3 左右主导的大脑网络

图4 引自文献[10]的一个生物网络Fig.4 A biological network cited from Ref.[10]

通常，全体网络可分为动态网络 (dynamic networks) 和非动态网络.非动态网络是在一个时间段内没有节点和连线数目的变化，如铁路、公路网等；而动态网络的节点和连线的数目随时间而变，如Internet，WWW，生物代谢网，物联网等.网络研究中的网络图是一种图解模型，形状如同网络，故称为网络图，他们均是拓扑图.网络图是由作业 (箭线)、事件 (节点) 和路线三个因素组成的.Pavlopoulos 等[1]指出：“图论的 (随机的或非随机的) 图和有向图自然而生动地被用来作为理解的模型以及模拟复杂的网络.”更多的例子指明拓扑图是各种学科的通用语言之一.

1.2 人工智能研究中的拓扑图应用

2018年6月，Battaglia等[2]发表关于图网络的论文.孙茂松团队[3]2018年12月综述了关于图神经网络的研究.2019年1月，俞士纶团队[4]发表了图神经网络研究的综述.

在机器学习和人工智能中，许多有关系推理能力的方法都使用关系归纳偏置(relational inductive biase).Battaglia 等在文献[2]中提出了一个新的人工智能模块——图网络 (graph network).图网络具有强大的关系归纳偏置，是对以前各种对图进行操作的神经网络方法的推广和扩展，为操纵结构化知识和生成结构化行为提供了一个直接的界面.Battaglia 等还讨论了图网络如何支持关系推理和组合泛化 (combinatorialGeneralization)，探讨了如何在深度学习结构 (例如，全连接层、卷积层和递归层) 中，使用关系归纳偏置，促进对实体、关系，以及组成它们的规则进行学习，为更复杂、可解释和灵活的推理模式打下基础.图网络已经被用来分析自然语言3D场景生物学等实际应用场景.

Li等[5]针对图结构对象的检索与匹配这一具有挑战性的问题发表了关于图匹配网络(Graph Matching Networks)的文章，研究了图结构对象的相似性学习(similarity learning)问题，演示了如何训练图神经网络在向量空间中生成图嵌入，从而实现高效的相似性推理，提出了一种新的图匹配网络模型，通过一种新的基于注意力的跨图匹配机制，对图对进行联合推理，计算出一对图之间的相似度评分.

张钹(1)清华大学张钹院士在2018全球人工智能与机器人峰会大会报告“走向真正的人工智能”(Towards A Real Artifitial Intelligence)，CCF-GAIR 2018年6月15日，深圳.主张“有理解的人工智能”，他指出，由于一种人工智能的基本方法是用符号模型来模拟理性行为，符号模型可以表达信息的内容，所以它是在一个语义的符号空间里头，离散符号表示使得很多数学工具用不上.另一种基本方法是模拟感性行为，用的是特征空间的向量，可以把优化工具、概率统计工具等数学工具用上.

李立浧(2)2018盐城绿色智慧能源大会李立浧院士主题演讲“智能电网与能源网的融合”.首次提出了“透明电网”的定义是信息技术、计算机技术、数据通信技术、传感器技术、电子控制技术、自动控制理论、运筹学、人工智能、互联网等有效地综合运用于电力系统.通过在电网中安装多个小微智能传感器，使每一个设备都处于数据影像下.形成小微智能传感器的传感.智能设备和设备的智能化，智能二次系统，强大的软件平台、大数据平台、小微燃料获取的自由化，这些就构成了整个透明电网.透明电网会彻底改变电网的信息形态，整个电网系统都将是智能的、透明的.

1.3 运用图论理论和技术到网络研究中

Newman等[6]指出：“纯图论是美好而深刻的，但它与现实世界中的网络并不是紧密相关的.应用图论，顾名思义，则更关注现实世界的网络问题，但其方法是面向设计和工程”.著名的网络研究论著[1，7-9]均强调并使用了图论技术.

利用图论的知识来研究网络的文章数量庞大，涉及众多的网络学科分支，以个人之力综合网络研究是极其困难的.抛开实际应用网络，如电力网、物流网、社交网、财经网等，本文侧重动态网络的拓扑性质、构造，聚焦新概念、新问题，捕捉新对象、新技术、新理论，力图接近网络研究的主流，为网络研究提供有价值的参考.具有图论基础知识的读者理解本文的内容是不太困难的.

2 无标度图、集散点、崩溃度、物联网定义

2.1 无标度图定义

称函数f(x)为无标度函数 (scale-free function)，如果它满足f(ax)=g(a)f(x)，例如，f(x)=cxγ，则有

f(ax)=c(ax)γ=xγf(x).

2005 年，Li 等在文献[13]中首次提出建立无标度图理论，他们利用度-度相关系数，给出无标度图的定义：n个顶点的图G有定标度序列d=(d1,d2,…,dn)，如果对1≤k≤ns≤n，定标度序列d满足形如

(1)

的幂率规模秩关系，其中常数c>0，α>0.定义图G的s-度量为

(2)

注意到，对动态网络来说，精确量化s(G)是困难的，这就使得判断一个图是否为无标度图没有基于图的基本参数、可操作的量化标准.从动态的角度出发，运用文献[14]中的幂率度分布 (power law degree distribution)，给出下面的无标度图定义：

定义1[15-16]一个动态网络 (dynamic network) 是N(t)=(p(u,k,t),G(t)) (t∈[a,b])，其中p(u,k,t)是一个新进入网络N(t)的节点u与其他k个节点随机连接的概率，G(t)是网络N(t)的连通拓扑结构 (connected topological structure).对t∈[a,b]，若概率p(u,k,t)服从幂率度分布β(t)k-α，其中β(t)>0，则称G(t)为无标度图，网络N(t)为无标度网络 (scale-free network).

定义1的一个例子在图5中给出，但是这个定义仍然是利用幂率度分布来定义无标度图的，在实际应用中也是不容易操作的.因此，无标度图的定义仍需研究、探讨.

图5 无标度网络Fig.5 A scale-free network

2.2 集散点定义

注意到，无标度网络N(t)中的无标度图G(t)的阶数和边数一般情形下不是一个常数，这是因为不断地有节点进入或移出网络N(t)，而且每个节点的连线数目在时间区间[a,b]内也会变化，从而说明图G(t)不等同于图论中的图，称它为动态图 (dynamic graph).但对固定时刻t0，G(t0)就是图论中的拓扑图.对t∈[a,b]，G(t)的一个节点u的度是与它所连接的线的数目，记为degG(u,t)，且degG(u,t)>0.如果degG(u,t)等于正常数c，则说u是稳定点 (stable node).对t10，当G(t0)的特性和结构确定后，就可以用它来刻画或估测每一个G(t)的结构及其特性，t∈(t0-δ,t0+δ).为研究无标度网络N(t) (t∈[a,b]) 中不同类型的节点，寻找N(t)的“核图”，给出如下的概念：

定义3[16-18]称连通图G的一个顶点子集S⊆V(G)L(G)为平衡集 (balanced set)，若对图G的任何2棵生成树Ti和Tj，总有

|L(Ti)|-|S∩L(Ti)|=|L(Tj)|-|S∩L(Tj)|

(3)

当S≠V(G)时，称S为真平衡集 (proper balanced set).

有关网络模型中生成树的构造算法、生成树的数目等结论在文献[19-26]和文献[16]中均有研究报道.特别地，文献[16]介绍了PRESUB graph-算法，它是BREADTH-FIRST SEARCH algorithm的一个改进，PRESUB graph-算法可以找到网络模型中具有最多叶子的生成树.

2.3 网络崩溃度定义

在文献[27]中，Yao等为了刻画网络的坚韧性，给出了网络模型崩溃的定义.一个连通图H的顶点子集X使得删点图H-X不连通，删点图H-X有ω(H-X)>1个分支，称顶点子集X为连通图H的顶点割 (cut set).

定义5[15]在网络模型N(t)=(p(u,k,t),u(t),UG) (t∈[a,b])中，如果它的边集E(G(t))的一个子集E*使得删边网络模型N(t)-E*不连通，W1,W2,…,Wm是删边图N(t)-E*的分支，网络模型N(t)的边崩溃度 (edge-collapsed rank) 定义为

(4)

(5)

显然有0≤Ce(N(t)-E*)<1和0≤Cv(N(t)-V*)<1.实验表明，可以用边崩溃度和点崩溃度来描述网络模型N(t)的拓扑性质：(i)当Ce(N(t)-E*)和Cv(N(t)-V*)较大时，N(t)的连通性较高，稳定性也高；(ii) 当Ce(N(t)-E*)和Cv(N(t)-V*)较小时，N(t)的崩溃性较小；(iii) 当Ce(N(t)-E*)和Cv(N(t)-V*)接近1时，N(t)的稳定性高，此时，N(t)离无标度性也远.经过实验，下面定义6中的真优化割集在网络模型的崩溃性研究中有着重要的地位.

定义6[15]称连通图H的一个顶点割B*为真优化割集 (proper optimal cut set, POC-set)，如果它满足：

(i) 对任何顶点子集X⊆V(H)，总有分支数ω(H-B*)≥ω(H-X)；

(ii) 对任何顶点割Y⊂V(H)，且2个分支数ω(H-Y)=ω(H-B*)，总有 |B*|≤|Y|；

(iii) 分支数ω(H-B*)满足 |B*|≤ω(H(B*).

Yao等从连通图H的生成树入手，来寻找连通图H的真优化割集.显然，这是一个纯图论问题.

2.4 物联网定义

Yao 等在文献[26]中用图论的技术给出物联网模型的定义.

定义7一个物联网的拓扑功能网络 (topological network) 定义为Io(t)=(d(p,u,t),G(t),UD) (t∈[a,b]).拓扑功能网络Io(t)中的每个顶点u的度数为degIo(u)=d(p,u,t)s(u,t)，其中d(p,u,t)叫做连接函数 (linking function)，是t时刻在确定的规则 (rule)p下与顶点u关联的边数目，值为0，1的s(u,t)是活动函数(active function)，当s(u,t)=0，说顶点u是睡眠的，当s(u,t)=1，说顶点u是活动的.一条边uv是物联网Io(t)的显边 (expressed edge)，若s(u,t)=s(v,t)=1，此外，称它为隐边 (implied edge)；一条路P=u1u2…un上的每个顶点ui均是活动的；G(t)是拓扑图 (topological graph)，G(a)是初始图，UD是拓扑功能网络Io(t)的底图 (underlying graph)，它包含了拓扑功能网络在时间段[a,b]内所有的顶点和边.

拓扑网络Io(t)是连通的，也就是说它的任何一对顶点被一条由活动边构成的路连接.如果拓扑网络Io(t)是无标度的，规则p服从幂律度分布p～k-α.通常，一个物流网 (logistic network) 是物理网络(physical network)和信息网(information network)的合成.

定义8一个物联网的数据功能网络 (data functional network)定义为Fu(t)=(g(u,t),F(t)，UF) (t∈[a,b])，其中g(u,t)=ddFu(t)s(u,t)是数据功能网络Fu(t)中顶点u的连接函数，物数据度 (thing-data degree)ddFu(t)=|Da(u,t)|是t时刻顶点u所拥有的物数据集 (thing-data set)Da(u,t)的模，值为0，1的s(u,t)是传感函数 (sensor function)，当s(u,t)=0时，顶点u既不接受数据，也不发射数据，除此外，顶点u是接发受数据的.如果Da(u,t)∩Da(v,t)≠∅，顶点u与顶点v是数据相邻 (data adjacency)；数值jdF(uv,t)=|Da(u,t)∩Da(v,t)|叫做边uv∈E(Fu(t))的边数据度 (edge-data degree)；如果Fu(t)包含一条路P=x1x2…xn，其中jdF(xjxj+1,t)≥1和j=1, 2, …,n-1，则说顶点x1和顶点xn是由P物数据连通的 (thing-data connected)；如果Fu(t)的每对顶点是由P物数连通的，则称Fu(t)是数据连通的；F(t)是Fu(t)在t时刻的拓扑结构图 (topological structure)，F(a)是初始值 (initialvalue)；UF是数据功能网络Fu(t)的底图 (underlying graph)，它包含了Fu(t)在时间段[a,b]内所有的顶点和边.

相邻性、连通性 (adjacency and connectivity)：根据定义8，在Fu(t)中如果有Da(u,t)⊆Da(v,t)，则说顶点u和顶点v是全数据相邻的 (all-data adjacent)，用一条实边 (solid edge) 连接它们；如果有Da(u,t)⊄Da(v,t)和Da(u,t)∩Da(v,t)≠∅，则说顶点u和顶点v是条件数据相邻的 (conditional data-adjacent)，用一条虚边 (dot edge) 连接它们.如果一条路P=x1x2…xn满足|Da(xi,t)∩Da(xj,t)|≥k>0 (i≠j)，则说顶点x1和顶点xn是强k-数据连通的 (stronglyk-data-connected)；如果 |Da(xi,t)∩Da(xi+1,t)|≥k>0 (i=1,2，…，n-1)，则说顶点x1和顶点xn是奇异k-数据连通的 (singularlyk-data connected).

定义9对一个物联网IoT的数据功能网络Fu(t)=(g(u,t),F(t)，UF) (t∈[a,b])，每条边uv∈E(Fu(t))的行为定义为

(3) 如果顶点u和v互不控制对方，则边uv保持不变，说顶点u,v均有0-行为. 如果u=v，即边uv是自环 (self-edge, loop), 也说顶点u,v均有0-行为.

定义10一个物 (thing) 有它自己的web-语义、确定的行为 (determined behaviors) 和唯一的web-识别，它具有定义9的k个行为中的一个行为 (k∈{0,1-, 1+, 2}).一个物联网 (Internat of Things)是物的集合，他们被定义7中的拓扑功能网络和定义8中的数据功能网络以及控制函数网络这3个网络的合成连接成一个整体.

上面的定义10表明，物联网正是谷歌团队的图网络.

3 确定型网络、随机网络

自1999 年以后，研究无标度网络的文章如井喷，无标度网络的分支数不胜数，本文的内容是作者根据自己的经验和认识来选择介绍图论技术，不一定是图论研究无标度网络研究的全貌或研究主流，读者可提出意见或按照自己的选择来学习、研究无标度网络.

称一个网络模型是连通的，如果任何一对顶点通过路径连接.如果没有特别的声明，这里提到的网络模型均是连通的.现实世界的动态网络很多是无标度网络，或是小世界网络 (small world network)，或是层次网络 (hierarchical network)，或是这几种网络的混合体.

3.1 无标度网络模型

在复杂网络研究中，Barabasi等[14]首次使用词语“无标度”(scale-free) 来描述他们的发现：许多大型网络具有一个共同的性质，即网络的顶点连线服从幂率度分布

P(k)=Pr(x=k)～k-α, 0<α

(6)

具有这种性质的网络和网络模型统称为无标度网络或BA-模型 (BA-model).

尽管无标度网络得到广泛的认可[13,28-31]，Bollobas等[32]指出：“在网络图模型中，从来就没有‘无标度’的准确定义，关于无标度图的研究结果极大程度上是探索式的，或者是具有极少严格数学方式的实验性质的研究；时常发生与探索式的结论既肯定又相矛盾的情形.”

Barabasi等[33]发现，少数高连通网页将整个 WWW 支撑连接在一起，其中80%的网页平均只有4个连接，占总网页数目 0.01 的网页每个却有不小于1 000个的连接.基于图结构分析，文献[15]讨论了动态网络中的一些问题.

无标度网络具有严重的异质性，其各节点之间的连接状况 (度数) 具有严重的不均匀分布性：网络中少数称之为 Hub 点的节点拥有极其多的连接，而大多数节点只有很少量的连接.少数 Hub 点对无标度网络的进化起着主导的作用.从广义上说，无标度网络的无标度性是描述大量复杂系统整体上严重不均匀分布的一种内在性质.

Newman 在文献[34-35]中给出研究复杂网络的各种数学方法，他的著作《网络导引》有784页，他发表了150多篇关于网络研究的文章，如：随机超图及其应用、随机无圈网络、网络中的子图，及包含子图的任意分布的随机图等.

3.2 无标度网络模型的拓扑性质

无标度网络模型是一个机制模型，也就是说它不是描述互联网、WWW或者细胞网络的模型，它只是用来解释一个网络的无标度特性背后的机制.真实世界的网络比理论模型复杂得多，真实网络的幂指数值从0到8不等.由无标度机制生成的网络，它们的度分布无法用一个万能公式来解释.单纯的幂律只出现在简单的理想化的模型中，仅仅由生长机制和优先连接 (偏好依附) 驱动，并且不受其他因素干扰[36].文献[37]指出，得到BA-模型的过程必须有以下3个要点：

(1)生长模型和优先连接 (growth and preferential attachment) 机制.给网络N(t-1)添加一个新顶点u(growth)，在优先连接 (preferential attachment) 概率∏i=ki/∑jkj下，将新顶点u与网络N(t-1)中的m个顶点x1,x2,…,xm分别用边连接.

(2)动态方程 (dynamic equation, rate equation).建立动态方程∂ki/∂t=m∏i，用初始条件ki(ti)=m从动态方程中解得度函数ki(t).

(3)度分布 (degree distribution).利用时刻ti时的一致密度函数f(ti)=(ti+m0)-1来计算度分布

(7)

和方程(6)中的幂率度分布P(k)～k-α(0<α<3).

上述过程演变成有力的数学方法，在研究具有BA-模型的动力学规律的系统中得到了各种形式的改变和应用.随之而来的问题是，方程 (6) 中的幂律度分布是判断一个网络是否为无标度网络的方法，人们期望知道类似的判断方法以及构造无标度网络模型的算法.

3.3 无标度网络模型的新动态方程

随着时间的推移，动态复杂网络的范围变得越来越复杂，顶点和边缘的数量迅速增加，其空间结构将变得更加复杂.没有什么网络会永远不停的成长.经过一段较长的时间后，网络本身会趋于稳定或衰变.文献[38]对动态演化过程进行了研究，创新性地在每个时间步骤中包含了输入和移除的顶点、生成和移除的边以及来自外部的大量干扰，设计出5个特性函数来建立新的动态方程[39-40]：

(1) 添加新顶点函数f(t)=f(p1(t)m,t,ki(t), ∑∏1j(ki))是在t时刻给N(t-1)添加新顶点，使得新顶点ja与N(t-1)中的m个顶点相连，奉献p1(t)m(0

(2) 移去顶点函数g(t)=g(p2(t)b,t,ki(t), ∑∏2j(ki)) 表明，在t时刻有p2(t)b(0

(3) 添加新边函数h(t)=h(p3(t)r,t,ki(t), ∑∏3j(ki)) 是在t时刻给N(t-1)中某些没有边的顶点对添加p3(t)r(0

(4) 删去旧边函数z(t)=z(p4(t)s,t,ki(t), ∑∏4j(ki)) 是在t时刻将N(t-1)中的p4(t)s(0

(5) 外部干扰函数φ(t)表明网络进化的过程将承受外界不可避免的干扰.

假定有m0个顶点的初始网络模型N(0)是连通的，则t时刻网络模型N(t)中顶点度为ki(t)的偏微分方程是

(8)

偏微分方程(8)就是新的动态方程，它的解为

ki(t)=θ(t,ti,α1,α2,…,αr)

(9)

其中，式子 (9) 中的参数αi(i=1, 2, …,r) 与时刻t和ti关联，立得

P(ki(t)θ-1(ki(t),t,β1,

β2,…,βr))

(10)

上式(10)中的参数βi(i=1, 2, …,r)也与时刻t和ti关联.所以，网络模型N(t)中度数为k的顶点的概率为

t,β1,β2,…,βr))

(11)

进一步，Ma等在文献[38]中建立了一个社会网络模型，使之适应新动态方程 (8)，并采用3种不同的择优概率∏whole(ki), ∏local(ki)和∏random(ki)来合成主优先连接概率

∏(ki)=∏whole(ki)+∏local(ki)+

令A1=α1am(1-p1),A2=2(1-p1)am+ap1,A3=α1amp1,A4=2(1-p1)(m0-am)+p1(n0-a),B1=α2am(1-p2),B2=2(1-p2)am+ap2,B3=α2amp2,B4=2(1-p2)(m0-am)+p2(n0-a).当t→∞时，得到

(12)

其中,C=B3A2+B2A3+mA2B2α3.在初始条件ki(ti)=m下，方程 (12) 的解为

(13)

其中,D=-c/(B1A2+B2A1),β=(A2B1+A1B2)/A2B2.根据方程 (13)，度为ki(t) (小于k,P(ki(t)

(14)

假定以概率P(ti)=1/(m0+ti)在相等时间段添加新顶点，则度分布P(k)为

(15)

按照方程(15)，社会网络模型N(t)服从幂律度分布P(k)～k-γ，其中指数γ=1+1/β是可调的.类似的结论可在文献[41-42]中看到.

3.4 动态网络的连通性

在文献[2]中，Battaglia 等问到：“如果一个对象在图网络中分裂成多个碎片，代表该对象的节点也应该被分割成多个节点.如何在计算过程中自适应地修改图网络结构?在一个图网络被分裂后，如何描述这个图网络?如何对合成后的图网络的底图的结构进行变化，如何从合成后的图网络来重建原来的图网络?”

文献[43-45]的作者从图论的角度给出下面撕裂型连通的概念，其中的顶点撕裂运算可以回答“如果一个对象在图网络中分裂成多个碎片，代表该对象的节点也应该被分割成多个节点”，顶点重合运算可以实现“重建原来的图网络”.

顶点撕裂与重合运算 (vertex-divided operation andvertex-coincident operation).设图H有2个不相邻的顶点u′和顶点u″，这2个顶点的邻集满足Nei(u′)∩Nei(u″)=∅.将顶点u′和顶点u″重合成一个顶点u=u′∘u″，所得到的图记为G=H(u′∘u″)，且记H=Gu.由H得到G的过程叫做顶点重合运算 (vertex-coincident operation)，见图6(a)和6(b)；反之，由G得到H的过程叫做顶点撕裂运算 (vertex-divided operation)，见图6(b)和6(a).

边撕裂与重合运算 (edge-divided operation and edge-coincident operation).设图H有2条无公共顶点的边u′v′ 和边u″v″，且4个顶点的邻集满足Nei(u′)∩Nei(u″)=∅和Nei(v′)∩Nei(v″)=∅.将顶点u′和顶点u″重合成一个顶点u=u′∘u″，将顶点v′ 和顶点v″ 重合成一个顶点v=v′∘v″，将边u′v′ 和边u″v″ 重合成一条边uv=u′v′⊕u″v″，所得到的图记为G=H(u′v′⊕u″v″)，且记H=Guv.由H得到G的过程叫做边重合运算 (edge-coincident operation)，见图6(d)和6(b)；反之，由G得到H的过程叫做边撕裂运算(edge-divided operation)，见图6(b)～6(d).在图6中，不难看到，6(b)→6(a)→6(c)→6(d) 也是边撕裂运算.

图6 解释撕裂、重合运算的示意图Fig.6 A scheme for illustrating divided and coincident operations

上面的顶点、边撕裂运算导致下面的撕裂连通度概念：

顶点撕裂连通度 (v-divided connectivity).顶点撕裂k-连通图L满足：顶点撕裂图L是不连通的，其中V*={x1,x2, …,xk}是V(L)的一个顶点子集，L的每个分支Lj至少有一个顶点wj∉V*,且有|L和|E(L使得顶点撕裂图L不连通的最小的整数k叫做图L顶点撕裂连通度，记为κd(L).

边撕裂连通度 (e-divided connectivity).边撕裂k-连通图F满足：边撕裂图F是不连通的，其中E*={e1,e2, …,ek}是E(F)的一个边子集，F的每个分支Fj至少有一个顶点wj不是E*中的任何一条边的端点，且有

|V(F

|E(F

使得边撕裂图F不连通的最小的整数k叫做图F边撕裂连通度，记为κ′d(F).

Wang 等在文献[45]中证明了：

引理1一个图G是k-连通的，当且仅当它是顶点撕裂k-连通的，即是κd(G)=κ(G).

利用引理1可得下面的结论：

定理1如果k-连通图有一个与k-连通度关联的性质，则对应的顶点撕裂k-连通图也有此性质.

定理2任意一个连通图G的顶点撕裂连通度κd(G)和它的边撕裂连通度κ′d(G)满足κ′d(G)≤κd(G)≤2κ′d(G)，且上、下界可达.

令ndis(G)是顶点撕裂图GX的分支数目最大者，有下面连通图的结构刻画：

定理3设连通图G有一个顶点子集X使得图G-X不连通，n(G-X)是不连通图G-X的分支数目.则n(G-X)=ndis(G)的充分必要条件是不连通图G-X的每个分支是一个完全图Km(m≥2).

定理4连通图G的一个顶点子集X⊆V(G)，使得n(G-X)=ndis(G)=p的充分必要条件是存在连通图G的子图Q1,Q2, …,Qp, 使得每一个图Qj-Yj(Yj=V(Qj)∩X)是一个完全图Km(m≥2).换句话说，顶点撕裂图GX是不连通的，且它的分支恰为Q1,Q2, …,Qp.

上面的引理、定理可得到下面的事实：

(1)在实施顶点撕裂运算后，新的图网络H=Gu的边数和原来的图网络G的边数相同，只是增加了顶点的个数.将原来顶点u上的赋值或属性撕裂成2个，顶点重合运算再将2个子赋值或子属性合成一个，从而达到“重建原来的图网络”.如果采用图论中删顶点的技术，则使得新的图网络比原来的图网络要少边和顶点，更为重要的是，顶点和其关联的边上赋值或属性全部消失，给“重建原来的图网络”带来困难，甚至是在有效时间段内不可修复原来的图网络.

(2)在定理3中给出连通图结构的一个刻画，也是图网络坚韧性的一种度量.

(3)利用顶点撕裂运算可以证明具有q条边的连通欧拉图能够被撕裂成一个具有q个顶点的哈密尔顿圈[45-46].

(4)重合一对不相邻且无公共邻顶点的过程叫做保边收缩运算 (keep-edge concentrate operation).如果不能对图G做保边收缩运算，则称图G为不可收缩图.当图G是k-可着色的，所有对图G实施顶点撕裂运算得到的图均是k-可着色的.

3.5 拓扑图运算下的网络模型

设计、构造网络模型的目的：为实际的网络建设提供理论依据和具体的高效网络模型，深入探究网络的更多的性质，挖掘其实际应用的潜力.

3.5.1 拓扑图运算

文献[21]的作者建立了2类拓扑图：广义梯子图 (generalized ladder-graph) 和正则轮图 (regular wheel-graph).他们用图的连接运算 (link-Operation) 和融合运算 (merge-Operation) 对广义梯子图、正则轮图的生成树的数目进行计算，得到了生成树数目的精确公式.

文献[22]用图论的运算构造了广义自相似非平面图，创新设计了一种特殊矩阵运算，用它建立了一个稀疏网络空间 (sparse network space)，并验证了此空间的稀疏性 (sparsity)、小世界性，以及指数标度特征 (exponential-scale feature)P(k)～α-k.

图论的正三角增长运算 (upright triangle growth operation) 和倒三角增长运算 (inverted triangle growth operation) 在文献 [23] 中得到应用，并建立了一类顶点-边增长的小世界网络模型，证实了这类模型具有自相似和层次结构特征 (self-similar and hierarchical characters).图7给出正三角增长运算和倒三角增长运算的解释.

图7 正三角增长运算和倒三角增长运算

Fig.7 A scheme for understanding upright triangle-growth operation and inverted triangle-growth operation

Ma等在文献[25]中构造了2类Fibonacci-模型.主要技术手段是新定义了顶点速度δv(t) =Ft+Ft+1，其中{Ft}是斐波纳契序列 (Fibonacci sequence)，并利用图的三角增长运算来产生Fibonacci-模型.Ma等证实了Fibonacci-模型有着优秀的拓扑性质，十分有利于在实际应用中采用此模型来建立优质的动态网络.

文献[44]给出构造自相似树网络的几个算法，其中，有斐波纳契边算法 FIBONACCI-EDGE algorithm 和斐波纳契顶点算法 FIBONACCI-VERTEX algorithm.图8和图9给出一个自相似树网络的前4个时刻t=1,2,3,4的进化状态.自相似性的数学定义是

θ(r)=αθ(r)，或θ(r)～α

(17)

图8 自相似树网络

Ma 等在文献[47]中利用拓扑图的交运算 (join operation)、笛卡尔积运算 (Cartesian operation)、分形运算 (fractal operation) 等运算构造了无标度网络模型，并刻画了它们的拓扑性质.

3.5.2 菱形扩缩运算系统

王宏宇[48]设计了菱形扩缩运算系统(rhombus expanded-contracted operation system)，该系统以K3为初始运算对象，通过反复使用图10中的两种扩缩运算，生成一个4-可着色的极大平面图(maximal planar graph).

图9 在时刻t=4的自相似树网络N4043(t)

Fig.9 The self-similar Hanzi-networkN4043(t) shown at the forth stept=4

菱形扩缩运算系统可以应用到网络模型的构造.例如，在一个网络模型N(t-1)中选取一条2长的路xyw(图10(a))，将中间的顶点y撕裂成2个顶点y′和y″，使得2个顶点的邻集Nei(y)=Nei(y′)∩Nei(y″)，x,w∈Nei(y′)，这里允许Nei(y″)=∅，然后添加3条新边y′y″、xy″和wy″，得到一个菱形xy′wy″，产生的新网络模型记作N(t) (见图10(b)).

图10 菱形扩缩运算[48]Fig.10 The rhombus expanded-contracted operation cited from Ref.[48]

3.5.3 Peterson 网络模型

Peterson 网络模型 (Peterson model) 在文献[24]中作为物联网的模型得到了研究，Peterson 网络模型具有较高的平均度，较强的中心性，无标度的幂律度分布、累积度分布，较高的聚类分布等良好的拓扑性质，证明Peterson网络模型具有强坚韧性，是适合于物联网建设的可靠的网络模型之一.

3.6 超网络模型 (hypernetwork models)

定义复合控制网络模型Ncd(t)的主度分布 (main degree distribution)Pmain(k) 如下：

(18)

其中∂iP(k)是社区Gi(t)的度分布，也称为复合控制网络模型Ncd(t)的第i个偏度分布 (ith partial degree distribution).

如果每个偏度分布服从幂律度分布

∂iP(k)～k-γi(i=1, 2,…,n)，

显然，复合控制网络模型Ncd(t)的主度分布Pmain(k)远不是Ncd(t)的度分布P(k).而且，主度分布Pmain(k)仅仅是各个社区的度分布的线性组合，没有关联到基Base(t)的度分布，也没有关联到运算“(t)”.在特殊情形下，绝对值|Pmain(k)-P(k)|将会变得很小.

在文献[49]中，Su等取复合控制网络模型Ncd(t)中的基为Apollonian 网络模型，每个社区为 Sierpinski网络模型，从基Apollonian 网络模型的控制集中取顶点的概率为p(t)=1，控制集中的顶点替换成社区后的相邻顶点的社区连接运算是图的交运算，建立了2类复合控制网络模型，并研究了他们的部分拓扑性质.

复合控制网络模型Ncd(t)中以控制集Dom(t)作为活动顶点集，可以选取Dom(t)为Hub点集，或者其他类型的顶点.也可以将控制集Dom(t)换成一个基Base(t)的一个子图，叫做活动子图 (active subgraph).由于基Base(t)中的任何一个顶点要么在控制集Dom(t)中，要么它与控制集Dom(t)中的某个顶点相邻.所以，复合控制网络模型Ncd(t)的拓扑性质可以由基和社区来近似估计或度量.

设M(t)是一个网络模型，I(t)是M(t)的一个核，L(t)={Li(t): 1≤i≤n}是生成元集合，每个Li(t)是一个网络模型，O={Oi,j: 1≤i,j≤m} 是时间[a,b]段上的二元运算集合.复合网络CM|I,L,O(t)是将I(t)的边xy的2个端点分别换为Lx(t)和Ly(t)，对Lx(t)和Ly(t)实施二元运算Ox,y, 将顶点u∈V(M(t))V(I(t))与Lv(t)的一个顶点用一条边连接，其中Lv(t)对应I(t)的顶点v，边uv∈V(M(t)).图11给出2个复合网络CM|I,L,O(t)的示例.

图11 2个复合网络CM|I, L, O(t))

3.7 半随机网络模型

Yao等在文献[50]中介绍了几种图运算算子，以及收缩边运算、顶点边剖分运算等.他们的随机算子 (random operator) 是概率p(0

图12 一个动态确定型网络模型

(a) 2个图算子; (b) 初始确定型网络模型N(0); (c) 确定型网络模型N(1); (d) 确定型网络模型N(2)

图13 两个半随机网络模型

从网络模型N(2)中以概率prem=1/2随机地移走18条边后得到左图(e)，以概率padd=1/2随机地给左图添加9边后得到右图(f)

图14 另外两个半随机网络模型

从网络模型N(2)中以概率prem=1/3随机地移走12条边后得到左图(g)，以概率padd=2/3随机地给左图添加16边后得到右图(h)

3.8 构建最优网络模型

在文献[51]中，Lambiotte等为突破传统复杂网络建模的局限性，根据奥卡姆剃刀原则，好的模型即便是在高阶的条件下也应使用最少的假设，推导出可泛化的结论，从而使得模型的适用范围超过最初建模的情景.他们提出高阶模型可以引入下面几类的信息来扩展传统的复杂网络模型：

优-1. 传统的方法认为点与点之间的联系可以两两之间建模，在高阶网络中抛弃这个假设.

优-2. 传统的模型假设点与点之间的联系没有外部性，高阶的网络通过将网络中边的相互影响引入模型，从而改变传统模型对节点重要性，以及网络中群落 (社区) 组成的判定.

优-3. 高阶网络模型将点和点之间的连接分为不同的类型，例如在国际贸易网络中，将民用和军用的贸易分开，由于前者受经济规律影响，而后者受国际政治影响，从而需要以不同的方式对待.

优-4. 高阶网络模型将点与点之间的连接发生的时间和先后顺序引入模型.

优-5. 高阶网络模型会考虑节点之间关系对全局的影响，即网络中每个点的影响.

优-6. 传统的复杂网络，该文中即初阶马尔可夫模型 (first-order Markov model)，是符合马尔可夫的独立性假设的模型.

Lambiotte等[51]讨论了自我中心网络 (ego network)，时间序列数据的建模，高阶网络与群落检测，高阶网络与节点重要性分析，用图论中的 de Bruijn 图对高阶因果关系建模，高阶网络下的网络动力学，用网络对其中实体的相互关系进行抽象并建模，产生的数据又促使机器学习发展针对图的预测模型.

4 多部网络模型及其偏拓扑性质

由于多部网络模型与社交网络、一般网络的社区有着联系，研究它们有助于挖掘网络社区的拓扑性质.在实际的网络中，多部网络模型是很自然的.例如，由工人和机器组成的职业网络，股票市场的某些现象，两个或两个以上国家的科学合作.下面将构造不同于文献[52]的多部网络模型，并给出其拓扑性质，部分内容引自文献[40，53].

4.1 三部网络模型

令T(t)是具有顶点集划分 (X1(t),X2(t),X3(t)) 的三部网络模型，故T(t)的顶点集为V(t)=X1(t)∪X2(t)∪X3(t)，且当i≠j时，有Xi(t)∩Xj(t)=∅，3个子集X1(t),X2(t)和X3(t)均为独立集，T(t)的任何一条边的2个端点不在任何一个Xi(t)中.一个三部网络模型在图15中给出.下面的M-算法可以生成具有nv(t)个顶点和ne(t)条边的三部网络模型T(t).

图15 一个三部网络模型T(t)Fig.15 A tripartite model T(t)

构造算法-1：M-算法

初始化.T(0)是有n0个顶点和m0条边的连通图，它的顶点集

和 |Xi(t)∪Xj(t)|≥m,i≠j满足1≤i,j≤3.

迭代. 给T(t-1)的每个顶点集Xi(t-1)添加一个新顶点w，1≤i≤3和t≥1，将w与不在Xi(t-1)中的m(1≤m≤n0)个顶点以优先连接概率∏i用边连接，其中

经过t次迭代后，T(t)有nv(t)=n0+t个顶点和ne(t)=m0+mt条边.所以，T(t)的顶点度kj之和∑jkj等于∑jkj=2ne(t)，见图15的解释.由于新顶点w进入Xi(t-1)的事件独立于新顶点w进入Xj(t-1) (j≠i) 或进入Xl(t-1) (l≠i) 这2个事件.按照3个优先连接概率∏1, ∏2, ∏3是两两独立的假设，M-算法能够建立动态方程

(19)

在特殊情形下，能够求得方程(19)的解.假定Xi(t)的顶点的度和为

i=1,2,3, 以及 0

(20)

其中,

进一步，将式(20)代入，得

(21)

这里ni(T(t))是T(t)中度数为ki(t)的顶点的数目.根据在时刻ti的初始条件ki(ti)=m, 方程(20)的解为

它是一个顶点在时刻ti进入网络模型的度，其中

此外，使用在时刻ti的一致密度函数f(ti)=(ti+m0)-1，得到

P(ki(t)R(t))=

1-P(ti≤R(t))=

(22)

其中,

利用文献[14]和文献[37]的技术方法，可以计算出与其他k个顶点有k条边的概率PT(k)如下

进而，有

其中,

=1+1/A,A(-1)=1

(23)

按照文献[54]中介绍的网络模型的速度定义，三部网络模型T(t)的速度为

(24)

所以，T(t)以常量速度m增长、进化.下面推导三部网络模型T(t)的幂律度分布P(k)和累计度分布 (cumulative degree distribution)

(25)

(26)

P(ki(t)

(27)

并得到一个公式

上式可推出带有常数kmin>0的累计分布

这也是出现在方程(25)中公式的一个证明

许多研究文献都运用了方程(25)，此方程能够帮助估算三部网络模型T(t)中度数不小于k的顶点数目，这些顶点的数目接近数nv(t)k.

4.2 多部网络模型

一般情形下，需要考虑n-部网络模型M(t)，n≥4.构造算法如下：对每一时刻t，M(t)的顶点集V(t)=X1(t)∪X2(t)∪…∪Xn(t), 任何2个不同的子集满足Xi(t)∩Xj(t)=∅ (i≠j, 1≤i,j≤n)，且每个Xi(t)不包含M(t)的任何一条边的2个端点.给M(t-1)的顶点子集Xi(t)添加一个新顶点w，在优先连接概率

(28)

下，用新边将新顶点w于其他顶点子集Xj(t-1) (i≠j) 中的顶点用边分别连接，得到n-部网络模型M(t).用∑j∈Xi(t)kj(t)=2ne(t)pi(i=1, 2, …,n) 可以得到n个较为简单的优先连接

(29)

定理5任何一个无标度网络模型是一个r-部网络模型 (r>0).

显然，对每个无标度网络模型来说，确定上述定理中r的值是不轻松的.

4.3 伪二部网络模型

Szabo等在文献[52]中介绍了广义BA-模型的率方程(rate equation).受AB-模型[52]的启发，设计了伪二部网络模型NPB(t)，它的顶点集划分为2个不交的子集X(t)和Y(t)，使得V(t)=X(t)∪Y(t).下面的伪-算法可以产生具有nv(t)个顶点和ne(t)条边的伪二部网络模型.

构造算法-2：伪-算法.

初始化. 伪二部网络模型NPB(0)至少有m个顶点和m0≥m-1条边，以及V(0)=X(0)∪Y(0),X(0)∩Y(0)=∅.

迭代. 给伪二部网络模型NPB(t-1)的顶点子集X(t-1) (t≥1) 添加一个新顶点u，在优先连接概率

给顶点子集Y(t-1)添加一个新顶点w，其中py满足 0≤py≤1.伪-算法能够产生下面的动态方程

(30)

这是因为∏X(ki)和∏Y(ki)相互独立，其中p*满足0≤p*≤1.设置

和

来解动态方程(30).进而，得到一个较为简单的动态方程

(31)

其中,

(32)

基于方程 (31)，可以计算出下面的和式

(33)

其中,NPB(t)是M(t)中具有度数ki(t)的顶点的个数.接下来，在初始条件ki(ti)=m下，动态方程(31)的解是

在时刻ti，用一致密度函数f(ti)=(ti+m0)-1来计算

PB(ki(t)M(t))=

(34)

且

进一步，伪二部网络模型NPB(t)中具有k条边的顶点的概率PB(k)可由下面的式子计算

(35)

以及

且

θ=1+1/L,L(θ-1)=1

(36)

通过调整式(36)中L里的参数p,p*,px和py的值，不难使得伪二部网络模型NPB(t)成为BA-模型.注意到，伪二部网络模型NPB(t)有nv(t)=nv(0)+t个顶点和ne(t)=ne(0)+mt条边.按照文献[54]中关于模型速度的定义，NPB(t)的速度等于

(37)

这说明，伪二部网络模型NPB(t)以常量速度而稳定地增长和进化.

4.4 多部网络模型中的确定型增长网络模型

一些多部模型是确定型、非随机型的，用他们来认识、理解复杂的网络比较容易些.对于解释经验观测的现象以及证明具有某些性质的网络的存在，确定型网络模型是有独到之用的.确定型增长网络可以通过算法来构造，按照某些确定的要求(优先连接)来添加新顶点，并将新顶点连接到网络模型中的节点，然后不断的重复.确定型网络模型的度数分布、聚类系数、平均最短路径长度、顶点、边缘累积分布、速度、随机步行中心性等相关网络指标都可以得到分析和验证.

图16 随机K-模型

图17 一致K-模型NU3(2)Fig.17 A uniform K-model NU3(2)

步骤U2 一致K-模型NUm(t)是对NUm(t-1)的每一个Km-组顶点xi1,xi2,…,xim，给随机选取的顶点子集Xs(t-1)添加一个新顶点u，使得xij∉Xs(t-1) (1≤j≤m)，然后用边将新顶点u与每一个顶点xij(1≤j≤m) 连接在一起.

现在讨论具有nv(t)个顶点和ne(t)条边的确定型增长网络模型N(t).首先考虑确定型增长网络模型N(t)满足线性增长(linear growth) 方程组

nv(t)=avt+bv,ne(t)=aet+be

(38)

其中，av,bv,ae,be均为正整数.已知BA-模型满足方程 (38)，伪二部网络模型NPB(t)和前面章节介绍的T(t)、M(t)均满足方程 (38).通常，一个非线性增长(exponential growth) 方程组是

nv(t)=avrt+bv,ne(t)=aest+be

(39)

其中|r|≠1和|s|≠1，av,bv,ae,be均为正整数.此外，按照方程 (38) 和方程 (39)，网络模型N(t)的速度Vel(N(t))[54]等于

(40)

或者

(41)

进一步，得

(42)

当方程(39)中s=r时，有

nv(t)=avrt+bv,ne(t)=aert+be

(43)

其中|r|≠1，并且

(44)

存在满足方程(43)的确定型增长网络模型，例如，Sierpinski-模型S(t) (r=3)[60]，递归树模型R(t) (r=q+1,q≥2)[59]，以及阿波罗模型A(t) (r=m(d+1))[62]，以及矩形增长网络模型r=4[19].可以将满足方程(43)和方程(44)的确定型增长网络模型用速度来分类，称它们为r-级模型.这里，Sierpinski-模型S(t)的增长速度小于递归树模型R(t)和阿波罗模型A(t).文献[63]介绍的四部网络模型和文献[64]中介绍的三部网络模型均是2-级模型.

不幸的是，我们没有发现满足方程(39)中的情形s≠r的确定型增长网络模型.显然，存在不同于方程(38)和方程(39)的其他网络模型，它们的顶点数目和边数目是不能够用形如方程(38)和方程(39)来表示的.

4.5 多部网络模型的讨论和问题

前面的小节提出了模拟真实网络的多部网络模型，并讨论了出现在现实生活中的伪二部网络模型，所得到的结果可以总结出具有nv(t)个顶点和ne(t)条边的BA-模型N(t)的基本特征如下：

特征-1两种机制.增长机制nv(t)>nv(t-1),ne(t)>ne(t-1)和优先连接机制∏i(t).

特征-2动态方程

(45)

其中，函数f由6个基本要素构成：n个新顶点和m条新边，时刻t，度ki(t)，α个移走的顶点，β条移走的边，以及优先连接概率∏i(t).

特征-4幂律度分布P(k)～k-γ和累计度分布Pcum(k)～k1-γ满足方程

(46)

(47)

特征-6网络N(t)是稀疏的[58]，即它的平均度k接近一个常数，或者

ne(t)～O(nv(t)ln[nv(t)])

(48)

对于一般的网络模型N(t)，去掉它的社区内部的边，就是多部网络模型N-e(t).当多部网络模型N-e(t)的性质研究清楚了，给N-e(t)添加边，重构原来的网络模型N(t)，这是一种研究一般网络的方法.

5 控制集、控制图、拓扑矩阵

图论的控制集在图论的理论研究中有着重要的地位.同样，控制集与网络的生成树、连通性、拓扑结构有着紧密的联系，尤其在无标度网络中，控制集包含网络的许多Hub (路由器) 点、无标度顶点.

5.1 控制集、控制图

已知具有最多叶子的生成树Tmax可以运用到确定网络中节点的类型，确定控制集与寻找网络中生成树Tmax紧密相关.

定义11图H的一个顶点子集X叫做控制集 (dominating set)，如果H中的每个顶点在X中，或者与X中的某个顶点相邻.

若控制集X的导出图H[X]是连通的，则称X为连通控制集 (connected dominating set).图H的最小连通控制集S使对图H的任何连通控制集X，总有|S|≤|X|成立.

文献[65]证明：连通图G的一个最小连通控制集S和Tmax满足|G|=|S|+|L(Tmax)|, 这里L(T)是一棵树T的叶子的集合.下面将控制集概念推广到控制图.

定义12对于图H的一个子图I，记图H-V(I)的分支数目为ω(H-V(I)).称子图I为H的一个控制图 (dominating graph), 如果数目分支ω(H-V(I))≥2，且图H-V(I)的每一个分支有顶点与I中的顶点相邻.此外，当子图I是连通图时，称I为连通控制图.若对H的任意一个控制图J，总有ω(H-V(I))≥ω(H-V(J))，且|E(I)|最小，则称I为最佳控制图 (optimal dominating graph).

注意，控制图与控制集不相同.这是因为一个控制集X外的每个顶点x必须与X中的某个顶点相邻；删去一个控制图I后，余图的每个分支有部分顶点与I的顶点相邻，有些I外的顶点y使得距离 d(I,y)≥2.所以，当k≤n-2时，n个顶点的K-连通图必有n个顶点的控制图.完全图没有控制图，顶点撕裂运算与控制图存在一定的联系.

证明先证明第一个断言：连通图G的每一棵生成树Tmax使得V(Tmax-L(Tmax))是G的一个最小连通控制集.

设Z是连通图G的一个最小连通控制集，导出图G[Z]是连通的，且有叶子最多的生成树TZ.每一个顶点x∈V(G)与Z=V(TZ)中的一个顶点相邻，得到图G的一棵生成树T*.显然，V(G)是L(T*)的子集合.对于图G的每一棵生成树Tmax，树Tmax-L(Tmax)的顶点集合S=V(Tmax)-L(Tmax)是图G的一个连通控制集，且满足|Z|≤|S|.从而，|L(T*)|≥|L(Tmax)|，说明图G的生成树T*满足|L(T*)|=L+(G).故，|Z|=|S|，第一个断言成立.

根据控制集定义和上面的证明，有第二个断言：每个最小连通控制集导出一棵生成树Tmax.

5.2 拓扑编码矩阵

文小刚(3)刘小刚院士的文章“物理学的新革命——凝聚态物理中的近代数学”中的观点.指出：“从量子革命以来，我们越来越意识到，我们的世界不是连续的，而是离散的.我们应该用代数的眼光看世界.”图的着色和标号统称为拓扑编码 (topological coding)，他们与图的赋值略有不同，图的赋值一般不要求顶点和边的赋值之间满足一定的数学约束.拓扑图编码的定义域涉及到千万种事物，一个图将若干个事物连接在一起，在一定的约束条件下，形成一个完整的“故事”.

拓扑编码与拓扑编码矩阵 (Topcode-matrix) 紧密相连，带有编码的拓扑图需要拓扑编码矩阵输入计算机.反过来，抽象的拓扑编码矩阵需要用拓扑图展示给人们.文献[66]定义拓扑编码矩阵如下：

定义13[66]一个拓扑编码矩阵是如下的矩阵

(49)

其中，顶点向量X=(x1x2…xq)、边向量E=(e1e2…eq) 和顶点向量Y=(y1y2…yq)由非负整数ei、xi和yi构成，称xi和yi为ei的端点，i=1,2, …,q.此外，如果有函数f使得ei=f(xi,yi)(i=1,2, …,q)，则称拓扑编码矩阵Tcode是值关联的 (evaluated).

下面的矩阵A是一个拓扑编码矩阵

(50)

这个拓扑编码矩阵A对应的部分拓扑图形编码在图18中给出.由于拓扑编码矩阵对应的拓扑图不唯一，这就极大地限制了破坏者的进攻，相应地，增大了拓扑编码矩阵在网络安全中的应用潜力.

图18 (a)-(f)具有撕裂奇优美着色的拓扑图形编码，每一个都对应于矩阵(50)

Fig.18 (a)-(f) are Topsnut-gpws with (splitting) odd-edge-magic coloring and the Topcode-matrix A

Yao等在文献[66]中定义了拓扑编码矩阵的撕裂连通性，利用代数的线性方程组给出汉字矩阵，并证明了顶点撕裂连通度与图的连通度是相互等价的.注意到，一个拓扑编码矩阵可以对应多个着色的图 (见图18)，也就是对应多个相邻矩阵，因此，深入挖掘拓扑编码矩阵的性质是一项有意义的工作.拓扑编码矩阵不同于图的邻接矩阵 (adjacent matrix)、拉普拉斯矩阵 (Laplacian matrix) 等，它们是代数方法在图论中的应用.下面是有向拓扑编码矩阵的定义：

(51)

尽管有向图与实际应用最为融合，有向拓扑编码矩阵和有向拓扑图形编码的研究报道却十分稀少，绝大部分的研究都以无向图作为研究模型.Jensen等[67]的著作是学习和研究有向图的力作之一.

6 网络研究中的问题

王建方(4)中国科学院数学与系统科学研究院研究员.指出：“信息科学技术的发展给人类社会的各个领域都产生了并继续产生着巨大的影响，也为创建、发展新数学提供了难得的机遇、源泉和动力.”下面给出部分由网络研究产生的图论、数学问题.

6.1 各种类型的累计分布

除了累计度分布和累计边分布外，下面是其他类型的累计分布：

(1)Yao等[20,54,68]定义了：(1-1) vd-累计分布

(52)

其中，N(k′,t)是在t时刻网络N(t)中度为k′ (>k)的顶点的数目.

(1-2) d-累计分布 (d-cumulative distribution)

(53)

其中，nd(t)是t时刻网络N(t)中度数为d的顶点个数，1

(2)Wang等在文献[68]中定义了下面的混合型累计分布 (mixed cumulative distributions)：

(54)

(55)

(56)

并用它们验证了Comellas的递归树模型、Sierpinski网络模型和Apollonian网络模型的无标度性质.

通过修改式(54)～(56)，Wang等[68]又定义了下面的一组混合型累计分布

(57)

(58)

(59)

(60)

(3)Newman在文献[34]中证明了下面的累计分布函数 (cumulative distribution function)

(61)

其中，Pr(k′)是网络中顶点度数不小于k的概率.

(4)Su等在文献[69]中定义了d-累计度分布(d-cumulative degree distribution)

(62)

其中，nd(i)是在时刻i时，网络N(i)中度数为d的顶点数目.

(5)Dorogovtsev等在文献[70]中定义了聚类系数累计分布 (cumulative distribution of the clustering coefficient)

(63)

且γ=1+ln 3/ln 2，其中ξ和ξ′是离散谱的点，mc(ξ′,t)是具有聚类系数ξ′ 的顶点的数目.

(6)Yao等在文献[54]中定义了Beta-距离累计度分布.先给出Beta-距离平均度的定义：

(64)

(65)

其中，X(u,t,β) 是在t时刻，与顶点u的距离为β的顶点之集，也叫做顶点u的Beta-距离控制集[27].当β=1 时，则有k1=k=2ne(t)/nv(t).Beta-距离累计度分布的定义为

(66)

它是对网络N(t)的一个整体度量，集合Yu(t,β，k′)是在t时刻与顶点u的距离为β的度数为k′的顶点之集.对网络N(t)的一个顶点u，其局部Beta-距离累计度分布为

(67)

6.2 有关图论的问题

图-1. 再刻画无标度图定义，扩展深化无标度图理论的研究.

图-2. 刻画无标度极大平面图.

图-3. Sierpinski网络模型是无标度的欧拉图，刻画无标度欧拉图.

图-5. 求最小正整数m，用翻转运算来翻转一个极大平面图的m条边后，得到一个无标度极大平面图.

图-6. 连通刻画图G，使得图G的每一个顶点都是图G的某个具有最多叶子的生成树Tmax的叶子.

图-7. 确定图的Beta-距离控制集 ((64)，(65)，β≥1) 及其应用.

图-8. 给出连通图有真优化割集 (定义6) 的条件，并找出其真优化割集.

图-9. 求图的边崩溃度 (4) 和点崩溃度 (5) 及其极值.

图-10. 一个具有n个顶点的圈经过顶点重合运算后，可以得到多少个互不同构的欧拉图?

图-11. 顶点不可收缩图是任何一对不相邻顶点都有公共的邻点，刻画顶点不可收缩图，发掘顶点不可收缩图的应用.

图-12. 刻画图的控制集、控制图与图的顶点连通、顶点撕裂连通之间的关系及其应用.

图-13. 确定图的平衡集和真平衡集 (见定义3)，探索这2个特殊集合与无标度图之间的联系.

6.3 有关网络拓扑性质的问题

以下设网络模型N(t)具有nv(t)个顶点和ne(t)条边.集合Property的元素为：平均度 (average degree)，平均距离 (average distance),幂律度分布 (power-law distribution), 聚类分布 (clustering distribution), 累积度分布 (cumulate distribution), 累积边分布 (edge-cumulate distribution)，中心度 (K-shell) 和介数 (betweenness)，聚类系数累积分布 (cumulative distribution of the clustering coefficient)，度相关 (degree correlation)，特征值累积分布(cumulative distribution of eigenvalues)，中介中心性 (betweenness centrality).

网络-1. 无标度网络N(t)一定是稀疏的网络吗？即它的平均度k接近一个常数，或者N(t)的边数目ne(t)等价于O(nv(t) ln[nv(t)])，nv(t)是顶点数目.马飞用图论中的线图构造出具有稠密性质的无标度网络模型，王晓敏用图的交运算构造了稠密的无标度网络[71].

网络-2. 文献[2]的作者问到：图网络运行中的图是从哪里来的？此外，许多图网络的底图是稀疏的，解决图网络稀疏性这个公开问题.

网络-3. 无标度网络的具有最多叶子的生成树是无标度树吗?

网络-4. 文献[54]、[68]均猜测到：无标度网络满足

P(k)～Pcum(k)～Pecum(k)，

其中，累计边分布[20],[54]定义为

这里，E(k′,t)是t时刻网络N(t)中与度为k′(>k)的顶点关联的边的总数目.这个猜测已经在Sierpinski网络模型，Apollonian网络模型和Comellas的递归网络模型以及其他几个确定型网络上得到证实.

网络-5. 研究网络的其他类型的累计分布.

网络-6. 构造网络模型，使得其顶点度为ki(t)的偏微分方程为(8).

网络-7. 网络模型的边崩溃度(4)和点崩溃度(5)可否用来刻画网络模型的拓扑性质?

网络-8. 深化研究无标度网络在集合Property中的拓扑性质.

网络-9. 表征复合控制网络模型在集合Property中的拓扑性质.