復(fù)雜網(wǎng)絡(luò)匹配系數(shù)控制算法＊

關(guān)世杰

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

復(fù)雜網(wǎng)絡(luò)匹配系數(shù)控制算法＊

關(guān)世杰

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

針對(duì)CAIDA提供的探測(cè)數(shù)據(jù)進(jìn)行分析，得到互聯(lián)網(wǎng)AS級(jí)宏觀拓?fù)浣Y(jié)構(gòu)的隨時(shí)間演化情況，在對(duì)匹配系數(shù)進(jìn)行深入分析的基礎(chǔ)上，提出了一種單調(diào)改變網(wǎng)絡(luò)匹配系數(shù)的算法——邊重連算法。該算法可以在兩個(gè)方向上構(gòu)造具有連續(xù)匹配系數(shù)的網(wǎng)絡(luò)集合，選擇向同配方向重連則可構(gòu)建匹配系數(shù)漸進(jìn)增大的連續(xù)匹配系數(shù)網(wǎng)絡(luò)，選擇向異配方向重連則可構(gòu)建匹配系數(shù)不斷減小的連續(xù)匹配系數(shù)網(wǎng)絡(luò)，當(dāng)邊重連足夠充分時(shí)可以得到具有極大匹配系數(shù)或極小匹配系數(shù)的網(wǎng)絡(luò)。

復(fù)雜網(wǎng)絡(luò)；互聯(lián)網(wǎng)AS級(jí)；網(wǎng)絡(luò)拓?fù)洌欢龋籆AIDA

1 引言

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

計(jì)算網(wǎng)絡(luò)度相關(guān)性的方法有兩種，第一種方法是通過鄰居節(jié)點(diǎn)平均度分布knn（k)來計(jì)算：

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

第二種方法是通過網(wǎng)絡(luò)的匹配系數(shù)［10］來進(jìn)行計(jì)算。計(jì)算匹配系數(shù)的公式如下：

2 網(wǎng)絡(luò)的度相關(guān)性演化分析

2.1 數(shù)據(jù)來源

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

本文從CAIDA提取了2007年10月至2011年2月AS級(jí)網(wǎng)絡(luò)拓?fù)涞臄?shù)據(jù)，其中2007年10月網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N＝15681，邊數(shù)L＝36055；2011年2月網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N＝25804，邊數(shù)L＝60852。

2.2 度相關(guān)性演化分析

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

Figure 1 Revolution of assortativity coefficient of AS-level topology圖1 AS級(jí)拓?fù)渚W(wǎng)絡(luò)匹配系數(shù)演化情況

3 邊重連算法

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

3.1 算法描述

首先，由網(wǎng)絡(luò)相關(guān)性的定義［10］可知匹配系數(shù)的計(jì)算公式為：

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

Nk為網(wǎng)絡(luò)中所有距離為k的節(jié)點(diǎn)對(duì)的數(shù)量。從公式（9)可以得出，在節(jié)點(diǎn)度值不變的情況下，匹配系數(shù)ρD的值與N3成正比。顯然，對(duì)于某一度向量節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)，它的匹配系數(shù)的值域?yàn)椋?～1。

3.2 算法實(shí)現(xiàn)

根據(jù)上述對(duì)于網(wǎng)絡(luò)匹配系數(shù)的論述，本文提出了邊重連算法，算法描述如下：

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

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

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

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

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

（1)提取網(wǎng)絡(luò)拓?fù)湫畔⑦M(jìn)行網(wǎng)絡(luò)的構(gòu)建，并保存。從網(wǎng)絡(luò)中任意選擇兩條邊，記為 （v1，v2)和（v3，v4)，存儲(chǔ)這兩條邊節(jié)點(diǎn)的索引號(hào)（保存在數(shù)組fourNodes［4］中)，用fourDegrees［4］數(shù)組保存節(jié)點(diǎn)對(duì)應(yīng)的度值；然后，用數(shù)組orderIndex［4］存儲(chǔ)這四個(gè)節(jié)點(diǎn)度值的降序的序列的數(shù)組下標(biāo)，orderIndex［0］保存最大度值節(jié)點(diǎn)的數(shù)組下標(biāo)，orderIndex［3］保存最小度值節(jié)點(diǎn)的數(shù)組下標(biāo)。

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

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

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

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

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

d新生成的網(wǎng)絡(luò)必須是連通的。

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

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

b網(wǎng)絡(luò)中不存在邊（fourNodes［orderIndex［0］］，fourNodes［orderIndex［3］］)和（fourNodes［orderIndex［1］］，fourNodes［orderIndex［2］］)。

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

d新生成的網(wǎng)絡(luò)必須是連通的。

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

3.3 算法驗(yàn)證

下面用多個(gè)模型網(wǎng)絡(luò)和實(shí)際網(wǎng)絡(luò)對(duì)ER算法進(jìn)行驗(yàn)證，該算法都能夠很好地生成連續(xù)匹配系數(shù)的網(wǎng)絡(luò)集合。對(duì)使用BA模型生成的復(fù)雜網(wǎng)絡(luò)進(jìn)行多次的ER操作過程之后，發(fā)現(xiàn)匹配系數(shù)的變化情況如圖2所示。

Figure 2 Variety of assortativity coefficient of BA network via fully ER圖2 對(duì)BA網(wǎng)絡(luò)進(jìn)行ER操作過程匹配系數(shù)變化情況

其中網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)N＝230，邊數(shù)L＝675，把重連邊數(shù)與網(wǎng)絡(luò)總邊數(shù)的比值做橫坐標(biāo)，每次保存網(wǎng)絡(luò)的間隔為5%，縱坐標(biāo)是新生成的網(wǎng)絡(luò)的匹配系數(shù)。圖3分別從異配方向和同配方向?qū)A網(wǎng)絡(luò)重連，當(dāng)重連比值大于400%時(shí)，新生成的網(wǎng)絡(luò)匹配系數(shù)基本保持不變，具有一個(gè)極值。

Figure 3 Evolution of maximum and minimum assortativity coefficient of AS-level internet圖3 AS級(jí)互聯(lián)網(wǎng)極大與極小匹配系數(shù)演化

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

4 結(jié)束語

本文通過CAIDA獲取互聯(lián)網(wǎng)拓?fù)湫畔⒆鳛閿?shù)據(jù)來源，對(duì)互聯(lián)網(wǎng)AS級(jí)拓?fù)渚W(wǎng)絡(luò)的鄰居節(jié)點(diǎn)平均度分布情況進(jìn)行分析，觀察網(wǎng)絡(luò)的演化特征，發(fā)現(xiàn)其異配性有弱化的趨勢(shì)，并且匹配系數(shù)值域在減小。在對(duì)匹配系數(shù)進(jìn)行深入分析的基礎(chǔ)上，提出了一種單調(diào)改變網(wǎng)絡(luò)匹配系數(shù)的算法—邊重連算法，實(shí)驗(yàn)表明該算法能夠較好地得到連續(xù)匹配系數(shù)網(wǎng)絡(luò)集合。

［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遼寧省撫順市沈陽工學(xué)院圖書與檔案館

Address：Library and Archives，Shenyang Institute of Technology，F(xiàn)ushun 113122，Liaoning，P.R.China

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

關(guān)世杰（1977-)，男，遼寧沈陽人，碩士，講師，研究方向?yàn)閺?fù)雜網(wǎng)絡(luò)。E-mail：39960476＠qq.com

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