复杂网络匹配系数控制算法＊

关世杰

（沈阳工学院，辽宁 抚顺 113122)

复杂网络匹配系数控制算法＊

关世杰

（沈阳工学院，辽宁 抚顺 113122)

针对CAIDA提供的探测数据进行分析，得到互联网AS级宏观拓扑结构的随时间演化情况，在对匹配系数进行深入分析的基础上，提出了一种单调改变网络匹配系数的算法——边重连算法。该算法可以在两个方向上构造具有连续匹配系数的网络集合，选择向同配方向重连则可构建匹配系数渐进增大的连续匹配系数网络，选择向异配方向重连则可构建匹配系数不断减小的连续匹配系数网络，当边重连足够充分时可以得到具有极大匹配系数或极小匹配系数的网络。

复杂网络；互联网AS级；网络拓扑；度；CAIDA

1 引言

当今复杂网络的研究得到了飞速发展，电力网络、科研网络、神经网络等多个领域［1～3］都取得了一定的研究成果，而Internet网络由于节点数量巨大、结构复杂等特点成为了科研学者关注的热点问题。在复杂网络领域中，互联网拓扑结构的研究［3～7］对分析互联网的结构特点，理解互联网的功能、发现互联网中未被发现的规律并预测互联网的发展有非常重要的意义。关于度相关性方面的研究与小世界性［8］、无标度性［9］等统计特性一样，是对复杂网络最重要和最普遍的研究热点问题之一。度相关性是指不同度值节点连接时所表现出的偏好性导致节点之间的连接存在某种相关性，节点间连接的偏好性是网络拓扑结构特征的一种体现，对互联网度相关性的分析与计算具有重要意义。

计算网络度相关性的方法有两种，第一种方法是通过邻居节点平均度分布knn（k)来计算：

其中，概率P（k′｜k)表示度值为k的节点与度值为k′的节点相连接的概率。通过计算不同度值节点的邻居节点的平均度分布，就可以得到该网络的度相关性。

第二种方法是通过网络的匹配系数［10］来进行计算。计算匹配系数的公式如下：

2 网络的度相关性演化分析

2.1 数据来源

目前从互联网获取数据有多种方法，本文所采用的数据从CAIDA获取的。CAIDA是一个可以在全世界范围内采集Internet的数据并对其进行分析的研究机构。最新的探测架构是Ark架构，该架构采用分布式的测量方法，各个探测节点通过元组空间来通信，实现了各探测节点的协作工作。

本文从CAIDA提取了2007年10月至2011年2月AS级网络拓扑的数据，其中2007年10月网络节点数N＝15681，边数L＝36055；2011年2月网络节点数N＝25804，边数L＝60852。

2.2 度相关性演化分析

为了发现网络度相关性演化规律，首先需要对互联网的AS级宏观拓扑结构特征的演化情况进行分析。计算网络的匹配系数，结果如图1所示，横坐标为月份，可以发现该网络是异配网络，而且匹配系数是在一定范围内不断变化的，从总体上看是逐渐增大的，说明网络的异配特性具有逐渐变弱的趋势。新加入网络的节点度值较小，而由于整个网络的匹配系数逐渐增大，可以得出新加入网络的节点中有一部分节点是与度值较小的节点相连接的，而且这部分新加入网络的节点数量成上升趋势。

Figure 1 Revolution of assortativity coefficient of AS-level topology图1 AS级拓扑网络匹配系数演化情况

3 边重连算法

从AS级互联网度相关特性的分析结果可以发现互联网的度相关特征的异配性有弱化的趋势。为了深入分析和预测网络变化的趋势，在进一步分析度相关性特征——匹配系数基础上，创造性地提出了边重连ER（Edge Rewiring)算法。

3.1 算法描述

首先，由网络相关性的定义［10］可知匹配系数的计算公式为：

其中，di、dj是网络中全部节点的度组成的向量dT＝［d1d2… dn］里面的两个元素，是该网络的邻接矩阵A中的一个元素。根据邻接矩阵和期望的关系有：

Nk为网络中所有距离为k的节点对的数量。从公式（9)可以得出，在节点度值不变的情况下，匹配系数ρD的值与N3成正比。显然，对于某一度向量节点构成的网络，它的匹配系数的值域为－1～1。

3.2 算法实现

根据上述对于网络匹配系数的论述，本文提出了边重连算法，算法描述如下：

首先，在网络中随机选择两条边v1～v2和v3～v4，这两条边对应的节点是v1、v2、v3、v4，可以确定存在边重连的可能性是v1～v3和v2～v4或v1～v4和v2～v3。然后把四个随机节点按照度值由大到小排列，即d1≥d2≥d3≥d4，并把四个节点命名为nd1、nd2、nd3、nd4，此时四个节点只可能存在三种连接关系，如下所示：连接所对应的匹配系数关系为：

三种状态Sa、Sb、Sc中对应的匹配系数值的大小关系为ρa≥ρb≥ρc。那么，如果按Sa→Sb，Sa→Sc，Sb→Sc关系进行重连，会使匹配系数递减，相反，按照Sc→Sb，Sc→Sb，Sb→Sa进行重连，会使匹配系数递增。上述推导过程证明了边重连算法的正确性，即通过部分边的交换重新连接来获取渐变的匹配系数的值，同时保持节点度值的不变。随着交换边数的连续增加，符合规则的重连边数将会减少。从理论上来说，给予足够多的重连机会的话，匹配系数的值将收敛到某一极值。

算法的实现过程如下：

基于上面的理论研究，我们对ER算法进行了设计实现。该算法可以在两个方向上构造具有连续匹配系数的网络集合。选择向同配方向重连则可构建匹配系数渐进增大的连续匹配系数网络；选择向异配方向重连则可构建匹配系数不断减小的连续匹配系数网络。当边重连足够充分时可以得到具有极大匹配系数或极小匹配系数的网络。

下面是算法的实现过程描述：

（1)提取网络拓扑信息进行网络的构建，并保存。从网络中任意选择两条边，记为 （v1，v2)和（v3，v4)，存储这两条边节点的索引号（保存在数组fourNodes［4］中)，用fourDegrees［4］数组保存节点对应的度值；然后，用数组orderIndex［4］存储这四个节点度值的降序的序列的数组下标，orderIndex［0］保存最大度值节点的数组下标，orderIndex［3］保存最小度值节点的数组下标。

（2)根据所选择的重连方向（异配方向或同配方向)的不同，把这两条边 （v1，v2)和 （v3，v4)重连，并记录执行重连的次数。

①选择同配方向时，需要满足下列条件：

a两条边的四个节点没有公共节点，即v1！＝v3，v1！＝v4，v2！＝v3，v2！＝v4。

b网络中的边不符合（fourNodes［orderIndex［0］］，fourNodes［orderIndex［1］］)或（fourNodes［orderIndex［2］］，fourNodes［orderIndex［3］］)，即不存在重连生成的新边。

c两条边 （v1，v2)和 （v3，v4)不能都是最大度值节点连边或最小度值节点连边。

d新生成的网络必须是连通的。

②选择异配方向时，需要满足如下列条件：

a两条边的四个节点没有公共节点，即v1！＝v3，v1！＝v4，v2！＝v3，v2！＝v4。

b网络中不存在边（fourNodes［orderIndex［0］］，fourNodes［orderIndex［3］］)和（fourNodes［orderIndex［1］］，fourNodes［orderIndex［2］］)。

c两条边 （v1，v2)和 （v3，v4)不能都是最大度值节点连边或最小度值节点连边。

d新生成的网络必须是连通的。

③重复执行重连过程pM次，其中M为网络节点的连边总数，p表示进行重连的比值。当p取足够大的值时，就可以形成极小匹配系数网络或极大匹配系数网络。在重复执行边重连过程中，将重连网络保存下来，就可以得到连续的匹配系数网络集合。

3.3 算法验证

下面用多个模型网络和实际网络对ER算法进行验证，该算法都能够很好地生成连续匹配系数的网络集合。对使用BA模型生成的复杂网络进行多次的ER操作过程之后，发现匹配系数的变化情况如图2所示。

Figure 2 Variety of assortativity coefficient of BA network via fully ER图2 对BA网络进行ER操作过程匹配系数变化情况

其中网络结点数N＝230，边数L＝675，把重连边数与网络总边数的比值做横坐标，每次保存网络的间隔为5%，纵坐标是新生成的网络的匹配系数。图3分别从异配方向和同配方向对BA网络重连，当重连比值大于400%时，新生成的网络匹配系数基本保持不变，具有一个极值。

Figure 3 Evolution of maximum and minimum assortativity coefficient of AS-level internet图3 AS级互联网极大与极小匹配系数演化

另外，为了更有效地确定AS级拓扑匹配系数值的变化范围，对采集的AS级网络数据进行了ER算法操作，分别从异配方向（匹配系数增大)和同配方向（匹配系数减小)对网络进行了边重连操作，计算出匹配系数的变化情况，结果如图3所示，图3a为实际网络的极大匹配和极小匹配系数的变化情况，图3b为匹配系数的极大值与极小值之差，极值与实际值之间差值的变化情况。参考图2中网络匹配系数的变化，发现如下比较明显的特征：（1)匹配系数的极大值和极小值随着实际网络的匹配系数变化而出现了逐渐增大趋势，这种现象说明了互联网AS级拓扑网络的异配性特征有弱化的趋势；（2)从图3b中可以发现，AS级拓扑网络匹配系数的值的范围有减小的趋势，即匹配系数的值域在减小，这种现象说明了互联网AS级拓扑的度相关特征变化逐渐稳定。

4 结束语

本文通过CAIDA获取互联网拓扑信息作为数据来源，对互联网AS级拓扑网络的邻居节点平均度分布情况进行分析，观察网络的演化特征，发现其异配性有弱化的趋势，并且匹配系数值域在减小。在对匹配系数进行深入分析的基础上，提出了一种单调改变网络匹配系数的算法—边重连算法，实验表明该算法能够较好地得到连续匹配系数网络集合。

［1］ Xu T，Chen J，He Y，et al.Complex network properties of Chinese power grid［J］.International Journal of Modern Physics B，2004，18（17)：2599-2603.

［2］ Wang F，Qiu J，Yu H.Research on the cross-citation relationship of core authors in scientometrics［J］.Scientometrics，2012，91（3)：1011-1033.

［3］ Wang Z，Liu Y，Li M，et al.Stability analysis for stochastic Cohen-Grossberg neural networks with mixed time delays［J］.IEEE Transactions on Neural Networks，2006，17（3)：814-820.

［4］ Kitsak M，Gallos L K，Havlin S，et al.Identification of influential spreaders in complex networks［J］.Nature Physics，2010，6（11)：888-893.

［5］ Shao J，Buldyrev S V，Braunstein L A，et al.Structure of shells in complex networks［J］.Physical Review E，2009，80（3)：036105.

［6］ Vespignani A.Complex networks：The fragility of interdependency［J］.Nature，2010，464（7291)：984-985.

［7］ Shao J，Buldyrev S V，Cohen R，et al.Fractal boundaries of complex networks［J］.EPL （Europhysics Letters)，2008，84（4)：48004.

［8］ Watts D J，Strogatz S H.Collective dynamics of small-world networks［J］.Nature，1998，393（6638)：440-442.

［9］ Arabsi A L，Albert R.Emergence of scaling in random networks［J］.Science，1999，286（5439)：509-512.

［10］ Newman M E J.Assortative mixing in networks［J］.Physical Review Letters，2002，89（20)：208701.

［11］ Fiol M A，Garriga E.Number of walks and degree powers in a graph［J］.Discrete Mathematics，2009，309（8)：2613-2614.

On the algorithm of controlling of matching coefficient of complex networks

GUAN Shi-jie
（Shenyang Institute of Technology，Fushun 113122，China)

According to the analysis of the detection data provided by CAIDA，the AS level topology of the internet developed by the time is found.On the basis of the deep analysis of the matching coefficient，an algorithm，named Edges Rewiring，is proposed，which can monotonously change the coefficient of the matched network.This algorithm can construct a network set with continuous matching coefficient in two directions.It can construct the crescent continuous net of matching algorithm network when choosing the same direction of reconnection，and it can construct the decreasing continuous matching algorithm when choosing the opposite direction of reconnection.The network with the maximal matching coefficient or with the minimal matching coefficient can be constructed when the number of edges rewiring is enough.

complex networks；AS-level internet；network topology；degree；CAIDA

TP393.02

A

10.3969/j.issn.1007-130X.2014.04.011

2013-04-03；

2013-06-22

通讯地址：113122辽宁省抚顺市沈阳工学院图书与档案馆

Address：Library and Archives，Shenyang Institute of Technology，Fushun 113122，Liaoning，P.R.China

1007-130X（2014)04-0634-05

关世杰（1977-)，男，辽宁沈阳人，硕士，讲师，研究方向为复杂网络。E-mail：39960476＠qq.com

GUAN Shi-jie，born in 1977，MS，lecturer，his research interest includes complex network.