阿波罗网络起源于阿波罗填充问题,本文中将阿波罗填充问题进行扩展,提出了四边形阿波罗填充问题,如图1所示,迭代生成过程如下:1)在一个二维平面上,存在4个相切的圆片,它们的空隙为曲边四边形,在四边形中放入一个合适大小的圆片,并产生4个曲边三角形; 2)将产生的空隙放入一个合适大小的圆片,使得圆片与空隙相切,且每个空隙只能放置一个圆片,可知空隙并没有被放入的圆片充满而是产生了3个更小的空隙.将第2)步不断重复下去,如果用t表示迭代的次数,当t→SymboleB@时,将每个圆片的圆心视为一个节点,若他们是同一时刻加入的圆片,则将其相邻的圆片圆心相连,并且将每一次新加入圆片的圆心与上一次相邻的新加入的圆片的圆心相连,便得到了本文中构造的网络模型.

图1 四边形阿波罗填充问题
Fig.1 Quadrilateral Apollo filling problem

记t时刻的阿波罗网络为N_t,初始的阿波罗网络为N₀,在4个三角形内各增加一个内部点(记为节点),并将节点与各自所在的三角形的顶点连边,构造出N₁.同样的,在N₁的各个三角形里增加新的节点,依旧与各个节点所在的三角形顶点连边,构造出N₂,以此类推,可得到网络N_t,此过程由以下算法表述.

如图2所示,初始t=0,N₀由4个顶点与一个中心点构成,并且将大的正方形划分为4个三角形.迭代:t≥1,通过对N_t-1添加节点并且进行连边得到,将每个三角形内部中心添加一个新的节点,并连接新节点与其所在的三角形的3个顶点,新划分出的三角形又成为下一时刻网络演化过程中产生新节点的三角形.

图2 网络结构迭代增长示意图
Fig.2 Network structure iterative growth diagram

对于已知t时刻阿波罗网络N_t,用记号n_v(t)和n_e(t)分别记为它的节点数目和边的数目,记号V(t)和E(t)分别表示阿波罗网络N_t的节点集合和边集合,即是n_v(t)=|V(t)|,n_e(t)=|E(t)|.在网络增长过程中,节点按照规律增长,且每个节点被创建时的初始度为3.由于阿波罗网络增长过程的迭代性质,可以得到

n_v(t)=n_v(t-1)+4×3^t-1,n_v(0)=5,t≥1.

n_e(t)=n_e(t-1)+4×3^t,n_e(0)=8,t≥1.

经过递推式求通式的方法化简得到如下点和边的表达式:

n_v(t)=2×3^t+3,t≥0,(1)

n_e(t)=2×3^t+1+2,t≥0.(2)

此外,N_t的平均度^[5]根据定义为:

〈k〉=(2n_e(t))/(n_v(t))=(2(2×3^t+1+2))/(2×3^t+3).(3)

当t→SymboleB@时平均度〈k〉→6,说明阿波罗网络N_t是一个稀疏网络,并且由结构可以看出,N_t不仅具有优先链接性,还具有增长性.Zhang等^[6]证明了阿波罗网络属于无标度模型.

一般地,从网络N_t的顶点集中删除一个子集能导致整个网络瘫痪,若有子集X^*V[N_t],使得对任意的子集XV[N_t]总有分支数ω(N_t-X^*)≥ω(N_t-X)成立,记网络N_t的点瓦解度^[8]为:

Cor(t)=(|X^*|)/(|V[N_t]|).(7)

显然,满足瓦解度Cor(t)的子集可能有多个.可以看出Cor(t)的值越大,网络受损程度越厉害.在四边形阿波罗网络中:

Cor(t)=(2×3^t-1+3)/(2×3^t+3)≈1/3.

由计算结果可得,在四边形阿波罗网络中,破坏X^*中的全部节点才能使网络遭到破坏后的分支最多,瓦解度最大.

同理可以定义^[6]边瓦解度:对任意边子集YE(N_t),若存在边子集Y^*E(N_t),使得总有分支数ω(E(t)-Y^*)≥ω(E(t)-Y)成立,网络N_t的边瓦解度记为:

Cor_E(t)=(|Y^*|)/(|E[N_t]|).(8)

在四边形阿波罗网络中:

Cor_E(t)=(2×3^t+1+2)/(2×3^t+1+2)=1.

可以看出,要破坏网络中的所有边才可以使瓦解度达到最大,这说明本文中提出的网络结构稳定性很强,若将其应用到基站建设,通信网络建设中,即使因为各种因素发生节点、边的损耗甚至破坏,整个网络依然具有很好的健壮性,仍然可以正常运转,想要网络失去作用,必须破坏所有的边.

一个顶点的度说明了这个顶点与其他顶点是否发生了连边,在通信交通网络中,一个顶点的度说明了这个顶点是否具有良好的信息传播性质,研究这一性质可以更好地刻画网络结构内部信息的传递性质.本研究针对这一特性考察邻点平均度和吸引数指标,力求刻画所提出的网络结构这方面的性质.文献[8]中定义顶点v₀的邻点平均度为t时刻v₀的邻点的度之和与X度的比值,记为:

d_ave(v₀)=1/(k(v₀,t))∑_y∈nei(v0)k(y,t),(9)

其中,k(v₀,t)表示N_t中顶点的度,nei(v₀)表示N_t中顶点v₀的所有邻点构成的集合.而顶点v₀的吸引数定义为:

att(v₀)=(k(v₀,t)-1)/(∑_y∈nei(v0)k(y,t)).(10)

对于本文研究的网络,时刻t下的顶点v₀有:

d_ave(v₀)=(2(2^t+1+1)+2^t×3t+2^t+2)/(2^t+1+1),

att(v₀)=(2^t+1)/(2(2^t+1+1)+2^t×3t+2^t+2).