復雜網絡匹配系數控制算法＊

關世杰

（沈陽工學院，遼寧 撫順 113122)

復雜網絡匹配系數控制算法＊

關世杰

（沈陽工學院，遼寧 撫順 113122)

針對CAIDA提供的探測數據進行分析，得到互聯(lián)網AS級宏觀拓撲結構的隨時間演化情況，在對匹配系數進行深入分析的基礎上，提出了一種單調改變網絡匹配系數的算法——邊重連算法。該算法可以在兩個方向上構造具有連續(xù)匹配系數的網絡集合，選擇向同配方向重連則可構建匹配系數漸進增大的連續(xù)匹配系數網絡，選擇向異配方向重連則可構建匹配系數不斷減小的連續(xù)匹配系數網絡，當邊重連足夠充分時可以得到具有極大匹配系數或極小匹配系數的網絡。

復雜網絡；互聯(lián)網AS級；網絡拓撲；度；CAIDA

1 引言

當今復雜網絡的研究得到了飛速發(fā)展，電力網絡、科研網絡、神經網絡等多個領域［1～3］都取得了一定的研究成果，而Internet網絡由于節(jié)點數量巨大、結構復雜等特點成為了科研學者關注的熱點問題。在復雜網絡領域中，互聯(lián)網拓撲結構的研究［3～7］對分析互聯(lián)網的結構特點，理解互聯(lián)網的功能、發(fā)現(xiàn)互聯(lián)網中未被發(fā)現(xiàn)的規(guī)律并預測互聯(lián)網的發(fā)展有非常重要的意義。關于度相關性方面的研究與小世界性［8］、無標度性［9］等統(tǒng)計特性一樣，是對復雜網絡最重要和最普遍的研究熱點問題之一。度相關性是指不同度值節(jié)點連接時所表現(xiàn)出的偏好性導致節(jié)點之間的連接存在某種相關性，節(jié)點間連接的偏好性是網絡拓撲結構特征的一種體現(xiàn)，對互聯(lián)網度相關性的分析與計算具有重要意義。

計算網絡度相關性的方法有兩種，第一種方法是通過鄰居節(jié)點平均度分布knn（k)來計算：

其中，概率P（k′｜k)表示度值為k的節(jié)點與度值為k′的節(jié)點相連接的概率。通過計算不同度值節(jié)點的鄰居節(jié)點的平均度分布，就可以得到該網絡的度相關性。

第二種方法是通過網絡的匹配系數［10］來進行計算。計算匹配系數的公式如下：

2 網絡的度相關性演化分析

2.1 數據來源

目前從互聯(lián)網獲取數據有多種方法，本文所采用的數據從CAIDA獲取的。CAIDA是一個可以在全世界范圍內采集Internet的數據并對其進行分析的研究機構。最新的探測架構是Ark架構，該架構采用分布式的測量方法，各個探測節(jié)點通過元組空間來通信，實現(xiàn)了各探測節(jié)點的協(xié)作工作。

本文從CAIDA提取了2007年10月至2011年2月AS級網絡拓撲的數據，其中2007年10月網絡節(jié)點數N＝15681，邊數L＝36055；2011年2月網絡節(jié)點數N＝25804，邊數L＝60852。

2.2 度相關性演化分析

為了發(fā)現(xiàn)網絡度相關性演化規(guī)律，首先需要對互聯(lián)網的AS級宏觀拓撲結構特征的演化情況進行分析。計算網絡的匹配系數，結果如圖1所示，橫坐標為月份，可以發(fā)現(xiàn)該網絡是異配網絡，而且匹配系數是在一定范圍內不斷變化的，從總體上看是逐漸增大的，說明網絡的異配特性具有逐漸變弱的趨勢。新加入網絡的節(jié)點度值較小，而由于整個網絡的匹配系數逐漸增大，可以得出新加入網絡的節(jié)點中有一部分節(jié)點是與度值較小的節(jié)點相連接的，而且這部分新加入網絡的節(jié)點數量成上升趨勢。

Figure 1 Revolution of assortativity coefficient of AS-level topology圖1 AS級拓撲網絡匹配系數演化情況

3 邊重連算法

從AS級互聯(lián)網度相關特性的分析結果可以發(fā)現(xiàn)互聯(lián)網的度相關特征的異配性有弱化的趨勢。為了深入分析和預測網絡變化的趨勢，在進一步分析度相關性特征——匹配系數基礎上，創(chuàng)造性地提出了邊重連ER（Edge Rewiring)算法。

3.1 算法描述

首先，由網絡相關性的定義［10］可知匹配系數的計算公式為：

其中，di、dj是網絡中全部節(jié)點的度組成的向量dT＝［d1d2… dn］里面的兩個元素，是該網絡的鄰接矩陣A中的一個元素。根據鄰接矩陣和期望的關系有：

Nk為網絡中所有距離為k的節(jié)點對的數量。從公式（9)可以得出，在節(jié)點度值不變的情況下，匹配系數ρD的值與N3成正比。顯然，對于某一度向量節(jié)點構成的網絡，它的匹配系數的值域為－1～1。

3.2 算法實現(xiàn)

根據上述對于網絡匹配系數的論述，本文提出了邊重連算法，算法描述如下：

首先，在網絡中隨機選擇兩條邊v1～v2和v3～v4，這兩條邊對應的節(jié)點是v1、v2、v3、v4，可以確定存在邊重連的可能性是v1～v3和v2～v4或v1～v4和v2～v3。然后把四個隨機節(jié)點按照度值由大到小排列，即d1≥d2≥d3≥d4，并把四個節(jié)點命名為nd1、nd2、nd3、nd4，此時四個節(jié)點只可能存在三種連接關系，如下所示：連接所對應的匹配系數關系為：

三種狀態(tài)Sa、Sb、Sc中對應的匹配系數值的大小關系為ρa≥ρb≥ρc。那么，如果按Sa→Sb，Sa→Sc，Sb→Sc關系進行重連，會使匹配系數遞減，相反，按照Sc→Sb，Sc→Sb，Sb→Sa進行重連，會使匹配系數遞增。上述推導過程證明了邊重連算法的正確性，即通過部分邊的交換重新連接來獲取漸變的匹配系數的值，同時保持節(jié)點度值的不變。隨著交換邊數的連續(xù)增加，符合規(guī)則的重連邊數將會減少。從理論上來說，給予足夠多的重連機會的話，匹配系數的值將收斂到某一極值。

算法的實現(xiàn)過程如下：

基于上面的理論研究，我們對ER算法進行了設計實現(xiàn)。該算法可以在兩個方向上構造具有連續(xù)匹配系數的網絡集合。選擇向同配方向重連則可構建匹配系數漸進增大的連續(xù)匹配系數網絡；選擇向異配方向重連則可構建匹配系數不斷減小的連續(xù)匹配系數網絡。當邊重連足夠充分時可以得到具有極大匹配系數或極小匹配系數的網絡。

下面是算法的實現(xiàn)過程描述：

（1)提取網絡拓撲信息進行網絡的構建，并保存。從網絡中任意選擇兩條邊，記為 （v1，v2)和（v3，v4)，存儲這兩條邊節(jié)點的索引號（保存在數組fourNodes［4］中)，用fourDegrees［4］數組保存節(jié)點對應的度值；然后，用數組orderIndex［4］存儲這四個節(jié)點度值的降序的序列的數組下標，orderIndex［0］保存最大度值節(jié)點的數組下標，orderIndex［3］保存最小度值節(jié)點的數組下標。

（2)根據所選擇的重連方向（異配方向或同配方向)的不同，把這兩條邊 （v1，v2)和 （v3，v4)重連，并記錄執(zhí)行重連的次數。

①選擇同配方向時，需要滿足下列條件：

a兩條邊的四個節(jié)點沒有公共節(jié)點，即v1?。絭3，v1！＝v4，v2?。絭3，v2?。絭4。

b網絡中的邊不符合（fourNodes［orderIndex［0］］，fourNodes［orderIndex［1］］)或（fourNodes［orderIndex［2］］，fourNodes［orderIndex［3］］)，即不存在重連生成的新邊。

c兩條邊 （v1，v2)和 （v3，v4)不能都是最大度值節(jié)點連邊或最小度值節(jié)點連邊。

d新生成的網絡必須是連通的。

②選擇異配方向時，需要滿足如下列條件：

a兩條邊的四個節(jié)點沒有公共節(jié)點，即v1?。絭3，v1?。絭4，v2?。絭3，v2?。絭4。

b網絡中不存在邊（fourNodes［orderIndex［0］］，fourNodes［orderIndex［3］］)和（fourNodes［orderIndex［1］］，fourNodes［orderIndex［2］］)。

c兩條邊 （v1，v2)和 （v3，v4)不能都是最大度值節(jié)點連邊或最小度值節(jié)點連邊。

d新生成的網絡必須是連通的。

③重復執(zhí)行重連過程pM次，其中M為網絡節(jié)點的連邊總數，p表示進行重連的比值。當p取足夠大的值時，就可以形成極小匹配系數網絡或極大匹配系數網絡。在重復執(zhí)行邊重連過程中，將重連網絡保存下來，就可以得到連續(xù)的匹配系數網絡集合。

3.3 算法驗證

下面用多個模型網絡和實際網絡對ER算法進行驗證，該算法都能夠很好地生成連續(xù)匹配系數的網絡集合。對使用BA模型生成的復雜網絡進行多次的ER操作過程之后，發(fā)現(xiàn)匹配系數的變化情況如圖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級互聯(lián)網極大與極小匹配系數演化

另外，為了更有效地確定AS級拓撲匹配系數值的變化范圍，對采集的AS級網絡數據進行了ER算法操作，分別從異配方向（匹配系數增大)和同配方向（匹配系數減小)對網絡進行了邊重連操作，計算出匹配系數的變化情況，結果如圖3所示，圖3a為實際網絡的極大匹配和極小匹配系數的變化情況，圖3b為匹配系數的極大值與極小值之差，極值與實際值之間差值的變化情況。參考圖2中網絡匹配系數的變化，發(fā)現(xiàn)如下比較明顯的特征：（1)匹配系數的極大值和極小值隨著實際網絡的匹配系數變化而出現(xiàn)了逐漸增大趨勢，這種現(xiàn)象說明了互聯(lián)網AS級拓撲網絡的異配性特征有弱化的趨勢；（2)從圖3b中可以發(fā)現(xiàn)，AS級拓撲網絡匹配系數的值的范圍有減小的趨勢，即匹配系數的值域在減小，這種現(xiàn)象說明了互聯(lián)網AS級拓撲的度相關特征變化逐漸穩(wěn)定。

4 結束語

本文通過CAIDA獲取互聯(lián)網拓撲信息作為數據來源，對互聯(lián)網AS級拓撲網絡的鄰居節(jié)點平均度分布情況進行分析，觀察網絡的演化特征，發(fā)現(xiàn)其異配性有弱化的趨勢，并且匹配系數值域在減小。在對匹配系數進行深入分析的基礎上，提出了一種單調改變網絡匹配系數的算法—邊重連算法，實驗表明該算法能夠較好地得到連續(xù)匹配系數網絡集合。

［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，F(xiàn)ushun 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，F(xiàn)ushun 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.