基于拓扑势的网络拓扑建模方法
苏 瑞，王勇，杨指挥
(桂林电子科技大学网络中心，桂林 541004)
摘要：针对现有拓扑建模研究中层次型模型不满足幂率分布规律的问题，提出一种基于节点拓扑势与幂率特性的层次化网络拓扑建模方法，给出拓扑生成算法PPHM。通过计算拓扑势实现网络节点的分层，能准确发现网络中的重要连接。对平均最短路径长度等拓扑参数的比较结果证明了该方法的有效性。
关键词：拓扑势；影响因子；模型；幂率；层次
Network Topology Modeling Method Based on Topology Potential
SU Rui, WANG Yong, YANG Zhi-hui
(Network Center, Guilin University of Electronic Technology, Guilin 541004)
【Abstract】In view of the question that the hierarchical mold does not satisfy the power law distribution rule in the existing topological modeling research, this paper proposes a hierarchical network topology model and a topology generating algorithm PPHM based on topology potential and power law. It realizes node stratifying by computing the topology potential, exactly discovers network important connection. Through comparing with the topological properties such as average minimum road length and so on, the validity of this modeling method is proved.
【Key words】topology potential; influence factor; model; power law; hierarchical
计 算 机 工 程 Computer Engineering第V·
1 概述
复杂网络拓扑结构建模是复杂网络研究的一个重要内容。现实中的复杂网络实例都具有层次模块特性和幂律分布特性，如自然网络和社会网络。层次模块特性用标度律来刻画是C(k)~k-A，其中，A为层次指数；C(k)是度为k的节点的平均聚集系数，即度为k的节点其邻居节点之间存在边的概率。幂律度分布特性，是指网络中一个被随机选中的节点有k条边(即度为k)的概率服从p(k)~k-C，其中，C为度指数[1]。无论层次模型还是幂率模型都仅是围绕复杂网络的某一个特性来建立的。为了更符合实际网络，更好地描述网络的各种特性，越来越多新的复杂网络模型被提出。Internet作为一个最大的人为复杂网络在层次模块性和幂律度分布上极具代表性。因而，需要用一个更合理的模型来全面描述Internet网络拓扑结构，体现Internet的真实特性。
2 网络拓扑建模现状
2.1 层次模型
人们广泛认为网络是分层次的，随着人们对层次模型研究的不断深入，也产生了各种基于层次模型的网络拓扑生成器。通常的分层结构中，同一层上的节点出度接近，不同层间节点出度差别很大。目前得以广泛应用的层次模型有Tiers模型和Transit-Stub模型。Tiers模型是第1个得以广泛应用的AS级层次拓扑模型。在该模型中，它将Internet中的节点划分为3个层次：LAN层节点，MAN层节点，WAN层节点。Tiers模型首先生成树，再将剩下的节点与生成树连接以保证拓扑图的连通性。节点间冗余边的添加主要依据2个节点的Euclidean距离，从最近的节点开始加边。该模型虽然保证了图的连通性，但不能以有效的方法增加连接。而Transit-Stub是GT-ITM(Georgia Tech-Internetwork Topology Models)软件包的一部分，有时GT-ITM也就是指Transit-Stub模型[2]。
2.2 幂率分布模型
网络拓扑的幂率特性是由Faloutsos等人对NLANR (National Lab for App lied Network Research)的3份边界网关协议数据以及1995年的一份TRACEROUTE测量数据进行分析得到的。他们发现Internet拓扑存在着3条幂率。幂率特性的发现表明，在Internet中即不存在Waxman模型当中的“平等”，也不像Tiers模型和Transit-Stub模型那样的“等级森严”，而是具有一种松散的层次性。而且网络中只有少数节点具有很高的出度，而大量节点只拥有很少的出度。目前，一些以符合幂率分布为目标的Internet拓扑建模研究已经逐步展开并取得了一些成果，如：Inet[3], PLRG[4], BA[5], BRITE[6]等。
3 节点拓扑势
节点拓扑势的概念是基于认知物理学中的数据场理论提出的。在基础物理学中，稳定有源场又被称为有势场或者保守场。其中势的物理含义是：把一个单位质点，如引力场中的单位质量、静电场中的单位正电荷，从场中的某一点A移动到参考点时场力所做的功[7]。节点拓扑势的大小描述了网络拓扑中的某个节点受自身和近邻节点共同影响所具有的势值。典型的节点重要性度量有节点度、介数和中心接近度等。
基金项目：2008年度广西研究生教育创新计划基金资助项目“计算机综合网络管理系统”(2008105950812M427)
作者简介：苏 瑞(1980－)，女，硕士研究生，主研方向：复杂网络拓扑建模，数据挖掘；王 勇，教授、博士；杨指挥，硕士研究生
收稿日期：2009-08-01 E-mail：surui530@guet.edu.cn
那些网络中度较大的节点、介数较大的节点、靠近网络中心的节点及其之间的边在网络中的地位都比较重要。因此，用节点的拓扑势来衡量节点的重要性，并且对网络节点进行分层能更为精细、真实地反映节点在整个网络中的的重要性、发现网络中的重要节点和敏感连接，使网络的分层更为准确。在网络拓扑中，通常采用拓扑距离计算节点通过网络拓扑传递所产生的势。设网络拓扑为G(N,V)，节点i处的势φ(i)为[8] 1()(e)jidnijjvmσϕ→−==×Σ
4 建模方法及PPHM算法的实现
为了克服随机拓扑模型的松散性以及当前层次拓扑模型用度划分层次的模糊性与片面性、为能更真实地模拟Internet的各种特性，本文引入拓扑势的概念，利用节点拓扑势来综合评价网络中的节点，并进行层次划分，使分层更为合理。具体的建模步骤如下：
(1)对网络中的节点计算各节点的势，根据各节点的势，对节点按照重要性排列，得到一个节点序列；
(2)按照节点的重要性程度对节点进行分类。序列中前10%的节点形成重要节点集合，中间30%的节点属于次重要节点集合、而剩余60%的节点划分为普通节点集合；
(3)利用幂率分布特性分别对3个层次中的节点用改进的PLOD算法[9]形成层内的网络拓扑连接；
(4)在保证各层内部节点连通性的同时，分别将次重要节点结合和普通节点集合中的重要节点以最短路径为依据与上层节点集合中路径最短的节点相连接。以此完成整个拓扑模型的层次连接。
PPHM拓扑生成算法按照以上所述的模型实现了拓扑的生成，算法如下：
g.Potential=Optimal_Sigma.GetFai(g.vex,g.ShortestPaths, g.Sigma);
g.GetGroup();
TopologyGenerate(g, g.group[0].members, g.group[0].ArcNums, alpha);
TopologyGenerate(g, g.group[1].members, g.group[1].ArcNums, alpha);
TopologyGenerate(g, g.group[2].members, g.group[2].ArcNums, alpha);
shortestPathdistinc = double.PositiveInfinity;
for ( i = 0; i < vexNum; i++)
{ for(j = 0;j< g.group[0].members.Length; j++)
{tmp=g.ShortestPaths[g.group[1].members[i], g.group[0].members [j]];
if (tmp != 0 && tmp != double.PositiveInfinity && tmp< shortestPathdistinc)
{shortestPathdistinc = tmp;
posti = i;
postj = j;}
}
}
5 算法分析
在整个建模方法中计算节点拓扑势是一个非常重要的基础，而在节点势的计算过程中影响因子σ的优化是关键。在求势φ(i)的式子中，mj代表节点j的质量，可映射为实际网络中的某些属性，如节点数据流量或者节点度等；dj→i代表节点j到节点i的最短路径长度；σ为影响因子，即节点影响的范围，通常可根据网络中节点的势熵对其进行优选。优化σ的过程实质上是一个单变量非线性函数即势熵最小化的问题[7]。当σ=0时，φ(j→i)→0，所以，φ(i)=mi=M，势熵趋近于Hmax=lgN。当σ→∞时，φ(j→i)→mj，即任意2个节点间的影响完全相同，φ(i)=NM，经Z归一化后，势熵再次趋近Hmax= lgN。由于势墒的大小反映了不确定性的强弱[8]，得知随着影响因子的单调递增，势熵的变化曲线在两端达到极大值，中间将存在一个极小值，此时节点的势分布最不均匀，不确定性最小。按以上思想，笔者对影响因子进行优化，图1给出了当数据场中包含有300个数据点的势熵H与影响因子σ的关系曲线，当σ近似等于0.015 6时，此时Hmin势熵值近似等于2.24。
图1 势熵H与影响因子σ的关系曲线
现实世界中总是存在着一些偏好连接的现象。在Internet中存在着局域网、城域网、国家主干、国际互联等各种不同层次的网络，这些网络被按照域-路由器的结构组织管理起来，每一台主机的连接不是漫无目的的随机连接，而是就近只与相同域内的距离较近的主机或路由节点相连接。在本算法中，始终以最短路径为依据进行节点之间的互联，使拓扑模型中任意节点对之间的连接总能保持是最短路径的连接。对于节点的分层，本着按照节点重要性程度划分层次的原则，将所有节点分为重要、次重要和普通节点，可以采取多种方式，如层次聚类等。由于本文的算法对于节点的层次划分并不需要严格的定义类别，因此为了降低整体算法的复杂度，采取通常所使用的按比例划分类别的方法，按一定比例来划分了网络中的节点。
本文所采用的数据[10]经过反复实验，采用复杂网络评价参数中的平均最短路径长度、网络聚集系数和平均节点度作为模型性能评价的基本依据。将真实连接graph, PPTM模型和TS模型[11]的拓扑数据进行比较，如表1所示。
表1 真实连接graph、PPHM模型和TS模型的拓扑数据
节点数
边数
平均节点数
最小平均 路径长度
网络聚集系数
真实连接graph
10 334
30 845
6.0
3.26
0.024 7
PPHM模型
10 334
20 701
4.2
3.09
0.009 0
TS模型
10 334
25 385
5.3
2.73
0.013 1
可见，使用本文的拓扑模型以及拓扑生成算法来模拟真实网络得到的结果与真实网络的实际情况较为接近，可以用来描述真实网络拓扑结构。
6 结束语
目前，无论是应用于网络仿真或是网络监控领域，网络拓扑图都是一种必不可少的工具。本文提出一种基于节点拓
（下转第113页） —110 —
苏 瑞，王勇，杨指挥
(桂林电子科技大学网络中心，桂林 541004)
摘要：针对现有拓扑建模研究中层次型模型不满足幂率分布规律的问题，提出一种基于节点拓扑势与幂率特性的层次化网络拓扑建模方法，给出拓扑生成算法PPHM。通过计算拓扑势实现网络节点的分层，能准确发现网络中的重要连接。对平均最短路径长度等拓扑参数的比较结果证明了该方法的有效性。
关键词：拓扑势；影响因子；模型；幂率；层次
Network Topology Modeling Method Based on Topology Potential
SU Rui, WANG Yong, YANG Zhi-hui
(Network Center, Guilin University of Electronic Technology, Guilin 541004)
【Abstract】In view of the question that the hierarchical mold does not satisfy the power law distribution rule in the existing topological modeling research, this paper proposes a hierarchical network topology model and a topology generating algorithm PPHM based on topology potential and power law. It realizes node stratifying by computing the topology potential, exactly discovers network important connection. Through comparing with the topological properties such as average minimum road length and so on, the validity of this modeling method is proved.
【Key words】topology potential; influence factor; model; power law; hierarchical
计 算 机 工 程 Computer Engineering第V·
1 概述
复杂网络拓扑结构建模是复杂网络研究的一个重要内容。现实中的复杂网络实例都具有层次模块特性和幂律分布特性，如自然网络和社会网络。层次模块特性用标度律来刻画是C(k)~k-A，其中，A为层次指数；C(k)是度为k的节点的平均聚集系数，即度为k的节点其邻居节点之间存在边的概率。幂律度分布特性，是指网络中一个被随机选中的节点有k条边(即度为k)的概率服从p(k)~k-C，其中，C为度指数[1]。无论层次模型还是幂率模型都仅是围绕复杂网络的某一个特性来建立的。为了更符合实际网络，更好地描述网络的各种特性，越来越多新的复杂网络模型被提出。Internet作为一个最大的人为复杂网络在层次模块性和幂律度分布上极具代表性。因而，需要用一个更合理的模型来全面描述Internet网络拓扑结构，体现Internet的真实特性。
2 网络拓扑建模现状
2.1 层次模型
人们广泛认为网络是分层次的，随着人们对层次模型研究的不断深入，也产生了各种基于层次模型的网络拓扑生成器。通常的分层结构中，同一层上的节点出度接近，不同层间节点出度差别很大。目前得以广泛应用的层次模型有Tiers模型和Transit-Stub模型。Tiers模型是第1个得以广泛应用的AS级层次拓扑模型。在该模型中，它将Internet中的节点划分为3个层次：LAN层节点，MAN层节点，WAN层节点。Tiers模型首先生成树，再将剩下的节点与生成树连接以保证拓扑图的连通性。节点间冗余边的添加主要依据2个节点的Euclidean距离，从最近的节点开始加边。该模型虽然保证了图的连通性，但不能以有效的方法增加连接。而Transit-Stub是GT-ITM(Georgia Tech-Internetwork Topology Models)软件包的一部分，有时GT-ITM也就是指Transit-Stub模型[2]。
2.2 幂率分布模型
网络拓扑的幂率特性是由Faloutsos等人对NLANR (National Lab for App lied Network Research)的3份边界网关协议数据以及1995年的一份TRACEROUTE测量数据进行分析得到的。他们发现Internet拓扑存在着3条幂率。幂率特性的发现表明，在Internet中即不存在Waxman模型当中的“平等”，也不像Tiers模型和Transit-Stub模型那样的“等级森严”，而是具有一种松散的层次性。而且网络中只有少数节点具有很高的出度，而大量节点只拥有很少的出度。目前，一些以符合幂率分布为目标的Internet拓扑建模研究已经逐步展开并取得了一些成果，如：Inet[3], PLRG[4], BA[5], BRITE[6]等。
3 节点拓扑势
节点拓扑势的概念是基于认知物理学中的数据场理论提出的。在基础物理学中，稳定有源场又被称为有势场或者保守场。其中势的物理含义是：把一个单位质点，如引力场中的单位质量、静电场中的单位正电荷，从场中的某一点A移动到参考点时场力所做的功[7]。节点拓扑势的大小描述了网络拓扑中的某个节点受自身和近邻节点共同影响所具有的势值。典型的节点重要性度量有节点度、介数和中心接近度等。
基金项目：2008年度广西研究生教育创新计划基金资助项目“计算机综合网络管理系统”(2008105950812M427)
作者简介：苏 瑞(1980－)，女，硕士研究生，主研方向：复杂网络拓扑建模，数据挖掘；王 勇，教授、博士；杨指挥，硕士研究生
收稿日期：2009-08-01 E-mail：surui530@guet.edu.cn
那些网络中度较大的节点、介数较大的节点、靠近网络中心的节点及其之间的边在网络中的地位都比较重要。因此，用节点的拓扑势来衡量节点的重要性，并且对网络节点进行分层能更为精细、真实地反映节点在整个网络中的的重要性、发现网络中的重要节点和敏感连接，使网络的分层更为准确。在网络拓扑中，通常采用拓扑距离计算节点通过网络拓扑传递所产生的势。设网络拓扑为G(N,V)，节点i处的势φ(i)为[8] 1()(e)jidnijjvmσϕ→−==×Σ
4 建模方法及PPHM算法的实现
为了克服随机拓扑模型的松散性以及当前层次拓扑模型用度划分层次的模糊性与片面性、为能更真实地模拟Internet的各种特性，本文引入拓扑势的概念，利用节点拓扑势来综合评价网络中的节点，并进行层次划分，使分层更为合理。具体的建模步骤如下：
(1)对网络中的节点计算各节点的势，根据各节点的势，对节点按照重要性排列，得到一个节点序列；
(2)按照节点的重要性程度对节点进行分类。序列中前10%的节点形成重要节点集合，中间30%的节点属于次重要节点集合、而剩余60%的节点划分为普通节点集合；
(3)利用幂率分布特性分别对3个层次中的节点用改进的PLOD算法[9]形成层内的网络拓扑连接；
(4)在保证各层内部节点连通性的同时，分别将次重要节点结合和普通节点集合中的重要节点以最短路径为依据与上层节点集合中路径最短的节点相连接。以此完成整个拓扑模型的层次连接。
PPHM拓扑生成算法按照以上所述的模型实现了拓扑的生成，算法如下：
g.Potential=Optimal_Sigma.GetFai(g.vex,g.ShortestPaths, g.Sigma);
g.GetGroup();
TopologyGenerate(g, g.group[0].members, g.group[0].ArcNums, alpha);
TopologyGenerate(g, g.group[1].members, g.group[1].ArcNums, alpha);
TopologyGenerate(g, g.group[2].members, g.group[2].ArcNums, alpha);
shortestPathdistinc = double.PositiveInfinity;
for ( i = 0; i < vexNum; i++)
{ for(j = 0;j< g.group[0].members.Length; j++)
{tmp=g.ShortestPaths[g.group[1].members[i], g.group[0].members [j]];
if (tmp != 0 && tmp != double.PositiveInfinity && tmp< shortestPathdistinc)
{shortestPathdistinc = tmp;
posti = i;
postj = j;}
}
}
5 算法分析
在整个建模方法中计算节点拓扑势是一个非常重要的基础，而在节点势的计算过程中影响因子σ的优化是关键。在求势φ(i)的式子中，mj代表节点j的质量，可映射为实际网络中的某些属性，如节点数据流量或者节点度等；dj→i代表节点j到节点i的最短路径长度；σ为影响因子，即节点影响的范围，通常可根据网络中节点的势熵对其进行优选。优化σ的过程实质上是一个单变量非线性函数即势熵最小化的问题[7]。当σ=0时，φ(j→i)→0，所以，φ(i)=mi=M，势熵趋近于Hmax=lgN。当σ→∞时，φ(j→i)→mj，即任意2个节点间的影响完全相同，φ(i)=NM，经Z归一化后，势熵再次趋近Hmax= lgN。由于势墒的大小反映了不确定性的强弱[8]，得知随着影响因子的单调递增，势熵的变化曲线在两端达到极大值，中间将存在一个极小值，此时节点的势分布最不均匀，不确定性最小。按以上思想，笔者对影响因子进行优化，图1给出了当数据场中包含有300个数据点的势熵H与影响因子σ的关系曲线，当σ近似等于0.015 6时，此时Hmin势熵值近似等于2.24。
图1 势熵H与影响因子σ的关系曲线
现实世界中总是存在着一些偏好连接的现象。在Internet中存在着局域网、城域网、国家主干、国际互联等各种不同层次的网络，这些网络被按照域-路由器的结构组织管理起来，每一台主机的连接不是漫无目的的随机连接，而是就近只与相同域内的距离较近的主机或路由节点相连接。在本算法中，始终以最短路径为依据进行节点之间的互联，使拓扑模型中任意节点对之间的连接总能保持是最短路径的连接。对于节点的分层，本着按照节点重要性程度划分层次的原则，将所有节点分为重要、次重要和普通节点，可以采取多种方式，如层次聚类等。由于本文的算法对于节点的层次划分并不需要严格的定义类别，因此为了降低整体算法的复杂度，采取通常所使用的按比例划分类别的方法，按一定比例来划分了网络中的节点。
本文所采用的数据[10]经过反复实验，采用复杂网络评价参数中的平均最短路径长度、网络聚集系数和平均节点度作为模型性能评价的基本依据。将真实连接graph, PPTM模型和TS模型[11]的拓扑数据进行比较，如表1所示。
表1 真实连接graph、PPHM模型和TS模型的拓扑数据
节点数
边数
平均节点数
最小平均 路径长度
网络聚集系数
真实连接graph
10 334
30 845
6.0
3.26
0.024 7
PPHM模型
10 334
20 701
4.2
3.09
0.009 0
TS模型
10 334
25 385
5.3
2.73
0.013 1
可见，使用本文的拓扑模型以及拓扑生成算法来模拟真实网络得到的结果与真实网络的实际情况较为接近，可以用来描述真实网络拓扑结构。
6 结束语
目前，无论是应用于网络仿真或是网络监控领域，网络拓扑图都是一种必不可少的工具。本文提出一种基于节点拓
（下转第113页） —110 —
选择“Disable on www.wenxuecity.com”
选择“don't run on pages on this domain”
