基于K-階結構熵的網絡異構性研究?

黃麗亞 霍宥良 王青 成謝鋒

(南京郵電大學,電子與光學工程學院,微電子學院,南京 210023)

(2018年7月19日收到;2018年11月8日收到修改稿)

結構熵可以考察復雜網絡的異構性.為了彌補傳統結構熵在綜合刻畫網絡全局以及局部特性能力上的不足,本文依據網絡節點在K步內可達的節點總數定義了K-階結構熵,可從結構熵隨K值的變化規律、最大K值下的結構熵以及網絡能夠達到的最小結構熵三個方面來評價網絡的異構性.利用K-階結構熵對規則網絡、隨機網絡、Watts-Strogatz小世界網絡、Barabási-Albert無標度網絡以及星型網絡進行了理論研究與仿真實驗,結果表明上述網絡的異構性依次增強.其中K-階結構熵能夠較好地依據小世界屬性來刻畫小世界網絡的異構性,且對星型網絡異構性隨其規模演化規律的解釋也更為合理.此外,K-階結構熵認為在規則結構外新增孤立節點的網絡的異構性弱于未添加孤立節點的規則結構,但強于同節點數的規則網絡.本文利用美國西部電網進一步論證了K-階結構熵的有效性.

1 引 言

大量系統都可以使用復雜網絡進行抽象的表達[1].復雜網絡各部分之間雖相互聯系,但通常存在著功能結構上的差異[2,3].因此,對網絡異構性的研究是分析節點重要性排序[4,5]、社區結構劃分[6,7]以及網絡傳播效率、同步能力等[8,9]內容的重要基礎.通常,網絡異構性是從拓撲結構的角度出發,通過定義結構熵予以定量評價.結構熵越小,意味著網絡各部分間的差異越大,異構性越強;反之意味著網絡結構越趨于均衡,異構性越弱.目前,已有諸多研究[10-15]各自從不同的角度定義了網絡結構熵.

Wu熵[10]以節點為主體,試圖通過分析網絡節點所擁有的邊的條數,即各節點度值之間的差異來反映網絡的異構性.而度分布結構熵[11](下文簡稱DD熵)則以度值為主體,依據擁有不同度值的節點數量之間的差異,對網絡的異構性進行了刻畫.可見,以上兩種方法僅將鄰居節點納入評價體系,未考慮非鄰居節點的影響,因而刻畫網絡全局特性的能力較弱,且對“橋”連接節點的重視程度不足.此外,Wu熵難以充分地解釋網絡中出現孤立節點的情況.蔡萌等[12]提出了一種基于點和邊差異性的網絡結構熵(下文簡稱SD熵),雖然將“點差異性”與“邊差異性”進行加權求和,但其本質仍是從網絡局部特性的角度出發,且加權系數是人為設置的,結果較為主觀;此外,SD熵在計算節點相對重要性時,人為地引入了?項,缺少理論解釋.為了充分利用網絡的全局特性,文獻[13,14]以節點介數以及邊介數為判據,定量地評價了網絡的異構性(下文簡稱節點介數熵為NB熵;邊介數熵為EB熵).介數雖然突出了橋節點的重要性,但對網絡拓撲中包含有環型或星型結構的部分解釋不足.為了綜合評估網絡的局部以及全局特性,蔡萌等[15]又提出了一種基于最大流的網絡結構熵,該方法使用網絡流量變化和節點度值的加權平均來計算網絡的異構性,但仍存在權重的選擇較為主觀、對?項的解釋不足等問題;且當網絡規模較大時,最大流矩陣的計算也十分復雜.此外,若網絡流量變化與節點度值量級不同,最終結果易受量級較大部分的影響.因此,尋找一種能夠綜合考查網絡全局以及局部特性的方便有效的異構性評價方法是本研究的目的所在.

文獻[16,17]將網絡視為節點間相互作用的系統,每個節點均處于其他所有節點產生的勢場之中.該方法假設網絡拓撲為短程場,并基于高斯勢函數定義了網絡拓撲勢函數,通過比較各個節點所處位置勢場值的大小研究了節點重要性、社區劃分等網絡特性.但網絡勢程的長短以及勢函數的形式應依網絡所代表的實際意義而各有不同,短程場以及高斯勢函數的假設均具有一定的局限性.

本研究試圖摒棄勢程長短、勢函數等額外假設,僅利用網絡的結構特性提出了一種K-階結構熵模型,并對規則網絡、隨機網絡、WS(Watts-Strogatz)小世界網絡、BA(Barabási-Albert)無標度網絡、星型網絡、在規則結構外新增孤立節點的網絡以及美國西部電網進行了理論研究與仿真分析,以證明該結構熵可以較好地反映不同網絡的異構性.

2 K-階結構熵模型

首先給定無權無向網絡圖G(V,E),其中V={v1,v2,···,vn}為節點集,共n個節點,E為邊集,并假設lij為節點vi到vj的最短路徑長度.為了避免網絡有無自環在分析上造成的差異,本文假設節點0步即可到達該節點本身,定義節點的K-階鄰居數為

其中I(·)為指示函數,即當節點vi與vj之間的最短路徑長度lij6K時I(·)=1,否則I(·)=0. 由(1)式可知,對于任意節點有=1.

K-階鄰居數衡量了網絡節點在K步內可達的節點總數,本文將K值命名為影響力尺度.由于本文研究的網絡大小是有限的,顯然當K大于網絡最大連通部分的直徑d時,各節點的K-階鄰居數均不再隨K值的變化而變化.因此K∈{0,1,···,d},并將d命名為最大影響力尺度.

若某節點的K-階鄰居數越多,可認為該節點在尺度K下所影響的節點越多,節點則越重要.為了衡量網絡在尺度K下各節點影響力或重要性的差異,即網絡的異構性,可將所有節點的K-階鄰居數加總代入到信息熵公式,從而得到K-階結構熵為

由隨機矩陣理論可知,網絡鄰接矩陣A的k次冪Ak中的第i行、第j列元素表示從節點vi到vj通過k條邊連接的路徑數目.因此,(1)式可以改寫為

其中為矩陣Ak中的第i行、第j列元素.此處A0=E為單位陣,恰對應于前文節點零步可達該節點自身這一假設.

事實上,(3)式表示的是矩陣多項式A0+A1+中第i行或列向量(無向圖的鄰接矩陣A為對稱陣,則其多項式亦對稱)中非零元素的個數,即L0范數.于是(3)式可以改寫為

HK值越小,證明網絡在影響力尺度K下的異構性越強,反之越弱.

由前文可知,K的取值是有限的,因此在分析網絡異構性時僅需研究K-階結構熵序列{H0,H1,···,Hd}即可. 對任意網絡而言, 當K=0時,各節點0步內只可到達其本身,因此有H0=log(n);當K=1時,各節點1步內可達該節點本身及其鄰居節點,因此H1按各節點“度值加一”代入信息熵公式進行計算,與Wu熵相似卻存在差異.若網絡是連通的,各節點在d步內均可到達網絡任意節點,因此Hd=log(n);若網絡是非連通的,Hd將依網絡結構而各不相同.此外,由于結構熵序列是可列有限的,其最小值minH=min{H0,H1,···,Hd}可被認為表征了網絡能夠達到的最強異構性.綜上所述,在應用K-階結構熵模型研究網絡的異構性時,應綜合考察結構熵序列隨K值的變化規律、Hd以及minH.

當網絡為有向網絡時,可將上述K-階結構熵演變為K-階發送以及接收結構熵兩部分進行討論.此時,可以將由某節點出發、K步內可達的節點總數(包含其自身)記為該節點的K-階發送節點數,依此得到K-階發送結構熵;同理可以計算出K-階接收結構熵.顯然,K-階發送以及接收結構熵分別衡量了網絡發、收能力的異構性,分析時均應予以考慮.當網絡為有權網絡時,若網絡邊權表示節點間的路徑長度,在計算節點的K-階鄰居數時,只需按有權網絡路徑長度的方法進行計算即可;若網絡權值表示節點間連接的強度時,則可選定某一閾值或者采用多閾值的方法將網絡進行二值化處理,再利用上述方法進行研究.

3 典型網絡的結構熵

為了驗證K-階結構熵評價網絡異構性的能力,本文對規則網絡、隨機網絡、WS小世界網絡、BA無標度網絡、星型網絡、在規則結構外新增孤立節點的網絡以及美國西部電網進行了仿真分析.以下所有仿真結果均取500次實驗的平均值.

3.1 WS小世界網絡

小世界網絡是指具有較大平均聚類系數以及較短特征路徑長度的一類網絡結構.Watts與Strogatz[18]最先提出了一種構造小世界網絡的方法,即將最近鄰耦合網絡每條邊的一個端點保持不變,另外一個端點依概率p隨機改連至其他節點,通常將生成的網絡稱為WS小世界網絡.當p=0時,網絡為規則結構,其異構性應當最弱;當p=1時,網絡中任意兩節點依一定概率隨機連接,其網絡異構性應強于規則網絡.值得注意的是,WS小世界網絡雖為規則與隨機網絡之間的過渡形式,其“主體”保持著最近鄰耦合結構,而個別節點卻擁有“長程”連接.但正是由于這些特殊節點的存在,使得網絡的特征路徑長度大大減少,起到了“橋”的作用.由此可見,WS小世界網絡中個別節點存在著連接上的突出優勢,而隨機網絡各節點的連接狀態是相似的,因此可認為WS小世界網絡的異構性強于隨機網絡.

下面基于K-階結構熵模型從結構熵隨K值的變化規律、網絡最強異構性minH等角度對WS小世界網絡進行考察.本文約定網絡隨機重連后不能有自環、重邊且仍為連通圖,易證Hd=H0=log(n).接下來,圖1和圖2分別仿真了50和200節點最近鄰耦合網絡在不同重連概率p下所生成網絡的結構熵隨K值的變化規律,其中該最近鄰耦合網絡每個節點與其左右各2個鄰居節點相連.

顯然,最近鄰耦合網絡的結構是對稱的,節點數為n的最近鄰耦合網絡的K-階結構熵恒等于log(n),如圖1(a)和圖2(a)所示.由于隨機重連打破了網絡結構的對稱性,在50及200節點網絡中均可觀察到,在任意重連概率p下,網絡結構熵隨K值的增加先下降再上升,且結構熵最小值minH所對應的K值隨p的增大而逐漸減小.但值得注意的是,當節點個數為50時,minH隨p的增加而減小;但當節點個數為200時,minH隨p的增加先減小,如圖2(a)—(f),后又略有增大,如圖2(f)—(h).有理由認為,minH不僅與網絡的拓撲結構有關,更與網絡的規模有著密切的聯系.因此,圖3仿真了網絡minH與小世界指數σ隨網絡節點數n以及重連概率p的變化曲線,其中對minH進行了歸一化處理.參照有關文獻[19,20],本文所使用的小世界指數定義為

其中,C和L分別為網絡的平均聚類系數與特征路徑長度,Cn與Ln分別為同節點數最近鄰耦合網絡的平均聚類系數與特征路徑長度.顯然,當網絡為最近鄰耦合網絡時,σ=1;由于小世界網絡擁有較高的平均聚類系數,與最近鄰耦合網絡相近,即C≈Cn;但其特征路徑長度較短,遠小于最近鄰耦合網絡,與同規模隨機網絡相近,即L?Ln.因此可認為σ值越大,網絡的小世界性越顯著;由圖3所示,從某p值開始,σ隨p的增加而下降.這是由于隨著重連概率的增加,網絡將同時具有較短的特征路徑長度以及較小的平均聚類系數,逐漸呈現出隨機網絡的特性.

圖1 50節點最近鄰耦合網絡在不同重連概率p及影響力尺度K下的結構熵 (a)p=0;(b)p=0.001;(c)p=0.002;(d)p=0.005;(e)p=0.01;(f)p=0.05;(g)p=0.1;(h)p=0.5;(i)p=1Fig.1.K-order structure entropy at in fluence scale K in graphs generated by randomly rewiring a 50 nodes nearest-neighbor coupled network based on different probability p:(a)p=0;(b)p=0.001;(c)p=0.002;(d)p=0.005;(e)p=0.01;(f)p=0.05;(g)p=0.1;(h)p=0.5;(i)p=1.

圖2 200節點最近鄰耦合網絡在不同重連概率p及影響力尺度K下的結構熵 (a)p=0;(b)p=0.001;(c)p=0.002;(d)p=0.005;(e)p=0.01;(f)p=0.05;(g)p=0.1;(h)p=0.5;(i)p=1Fig.2.K-order structure entropy at in fluence scale K in graphs generated by randomly rewiring a 200 nodes nearestneighbor coupled network based on different probability p:(a)p=0;(b)p=0.001;(c)p=0.002;(d)p=0.005;(e)p=0.01;(f)p=0.05;(g)p=0.1;(h)p=0.5;(i)p=1.

圖3 不同網絡規模n及重連概率p下的minH和小世界指數σ (a)n=10;(b)n=25;(c)n=50;(d)n=75;(e)n=100;(f)n=150;(g)n=200;(h)n=250;(i)n=300Fig.3.The minimum structure entropy minH and small-world coefficient σ at different network size n and rewiring probability p:(a)n=10;(b)n=25;(c)n=50;(d)n=75;(e)n=100;(f)n=150;(g)n=200;(h)n=250;(i)n=300.

圖4 不同網絡規模n及重連概率p下的小世界指數σ,DD熵、Wu熵、SD熵、NB熵以及EB熵 (a)n=10;(b)n=25;(c)n=50;(d)n=75;(e)n=100;(f)n=150;(g)n=200;(h)n=250;(i)n=300Fig.4.Small-world coefficientσ,degree distribution entropy(DD entropy),Wu entropy(Wu entropy),node and edge difference entropy(SD entropy),node betweenness entropy(NB entropy),edge betweenness entropy(EB entropy)at different network size n and rewiring probability p:(a)n=10;(b)n=25;(c)n=50;(d)n=75;(e)n=100;(f)n=150;(g)n=200;(h)n=250;(i)n=300.

由圖3可知,當網絡規模較小時,網絡的小世界性不明顯,minH隨p的增加單調下降;當網絡規模較大且p較小時,網絡具有顯著的小世界性,此時minH隨重連概率先下降再上升.因此,K-階結構熵認為最近鄰耦合網絡、隨機網絡以及WS小世界網絡的異構性依次增強,且網絡的小世界性越強,其異構性則越強.可見,K-階結構熵模型能夠較好地依據小世界屬性來反映網絡的異構性.

為了進一步驗證K-階結構熵的性能,圖4繪制了小世界指數σ與DD熵、Wu熵、SD熵、NB熵以及EB熵隨網絡節點數n以及重連概率p的變化曲線.

由圖4可見,在任意網絡規模下,DD熵隨p單調遞增,而Wu熵隨p單調遞減,可見DD熵與Wu熵均難以表征小世界網絡的異構性;此外,DD熵認為隨機網絡的異構性弱于規則網絡,與通常理解存在偏差;當網絡規模較小時,SD熵認為最近鄰耦合網絡、隨機網絡以及WS小世界網絡的異構性依次增強,與本文結論相似.但當網絡規模較大時,SD熵隨p的增加迅速上升,隨之保持在隨機網絡的異構性水平不變,但此時網絡仍具有較強的小世界性;EB熵在網絡小世界性較強時認為WS小世界網絡的異構性最強,但卻認為隨機網絡的異構性弱于最近鄰耦合網絡,這一結論同樣與普遍理解存在偏差.只有NB熵與本文結論相似.

3.2 BA無標度網絡與星型網絡

BA無標度網絡依據增長和擇優機理而構建[21],所生成的網絡度分布符合γ=3的冪律形式,網絡中少數節點擁有極多的連接,而大多數節點只有少量的連接,通常認為無標度網絡具有較強的異構性[22,23].星型網絡是指以中央節點為中心,其余節點均只與中央節點相連的拓撲結構,通常可被看作是無標度網絡的極端形式,其異構性要強于一般的無標度網絡.下面基于K-階結構熵對二者的異構性進行考察.文中規定BA無標度網絡與星型網絡均為連通圖,同樣有Hd=H0=log(n).

圖5仿真了在不同網絡規模下,BA無標度網絡與星型網絡歸一化后的K-階結構熵隨K的變化規律.

圖5 BA無標度網絡及星型網絡在不同網絡規模n及影響力尺度K下的結構熵 (a)BA無標度網絡;(b)星型網絡Fig.5.K-order structure entropy of BA scale-free networks and star networks at different in fluence scale K and the network size n:(a)BA scale-free network;(b)star network.

由圖5可見,在任意網絡規模下,BA無標度網絡與星型網絡的結構熵均隨K的增加先下降再上升.此外,BA無標度網絡minH所對應的K值隨網絡規模的增加逐漸增大,而星型網絡minH所對應的K值與網絡規模無關,即K=1時達到最小.這是由于在任意網絡規模下,星型網絡的節點均可在二步內到達其余節點.圖6仿真了最近鄰耦合網絡、隨機網絡、BA無標度網絡以及星型網絡等不同結構的minH,DD熵、Wu熵、SD熵、NB熵和EB熵隨網絡節點數n的變化情況.

由圖6可見,minH與Wu熵認為,在任意網絡規模下,最近鄰耦合網絡、隨機網絡、BA無標度網絡以及星型網絡的異構性依次增強;且隨著網絡規模的增加,以上拓撲結構的minH與Wu熵均呈上升趨勢.在此觀點下,星型網絡的異構性隨網絡規模的增加而減弱,這可以解釋為在任意網絡規模下,星型網絡只擁有一個中心節點,其余節點均是度1節點.隨著網絡規模的增加,重要性相同的度1節點的數量顯著增加,這導致了網絡的異構性有所減弱.此結論比SD熵和DD熵認為的星型網絡的異構性隨其規模的增大略有增強后保持不變的解釋更為合理;此外,DD熵區分隨機網絡與BA無標度網絡的能力不足,且無法充分反映最近鄰耦合網絡異構性隨其網絡規模的演化規律;NB熵對最近鄰耦合網絡、隨機網絡以及BA無標度網絡異構性隨其網絡規模演化規律的解釋與K-階結構熵相同,但卻無法充分反映星型網絡的異構性;EB熵認為隨機網絡與BA無標度網絡的異構性弱于最近鄰耦合網絡,與通常解釋存在偏差.

圖6 最近鄰耦合網絡、隨機網絡、BA無標度網絡、星型網絡在不同網絡規模n下的minH,DD熵、Wu熵、SD熵、NB熵以及EB熵 (a)minH;(b)DD熵;(c)Wu熵;(d)SD熵;(e)NB熵;(f)EB熵Fig.6.The minH,DD entropy,Wu entropy,SD entropy,NB entropy,EB entropy of nearest-neighbor coupled networks,random networks,BA scale-free networks and star networks at different network size n:(a)minH;(b)DD entropy;(c)Wu entropy;(d)SD entropy;(e)NB entropy;(f)EB entropy.

3.3 在規則結構外新增孤立節點的網絡

由于最近鄰耦合網絡、全連接網絡和環型網絡等規則網絡的結構是對稱的,因此其異構性應當較弱.現假設在規則網絡結構之外再新增若干個孤立節點,由于孤立節點在網絡中的結構與作用是固定不變的,它們只影響其自身,不與原規則部分中的任何節點發生作用,即孤立節點的存在增加了網絡的無序程度,因此該網絡的異構性應弱于原規則結構;但由于孤立節點與原規則部分的節點存在著結構上的差異,因此在規則結構外新增孤立節點的網絡的異構性應強于同節點數的規則網絡.

不失一般性,以下內容以最近鄰耦合網絡為例進行分析.由前文可知,當最近鄰耦合網絡未新增孤立節點時,K-階結構熵在任意影響力尺度K下均為log(n);現假設最近鄰耦合網絡的節點數為n,額外新增的孤立節點數為i,在任意影響力尺度K下,易證原最近鄰耦合部分各節點的K-階鄰居數相同,記為

而各孤立節點的K階鄰居數始終為1.因此,得到該網絡結構的K-階結構熵為

若假設n和i不變,由(8)式易證HK將隨著K的增加單調減少,因此有Hd6H0,即Hd6 log(n+i);且最大影響力尺度d下的結構熵Hd與最小結構熵minH相等.在最大影響力尺度d下,對于原最近鄰耦合網絡部分的節點有Nd=n,因此網絡的Hd即minH為

由(9)式易證log(n)6Hd.綜上有log(n)6Hd6 log(n+i),即可認為在n節點最近鄰耦合網絡外新增i個孤立節點后,其網絡異構性介于n與n+i節點最近鄰耦合網絡之間,與前文討論相符.事實上,節點為n的任意連通圖額外新增i個孤立節點后,其最大影響力尺度d下的異構性Hd均符合(9)式的結果,但網絡最小結構熵minH未必等于Hd.此外,隨著孤立節點的增多,當i?n2時,(9)式可近似為log(i),這可認為當孤立節點的數量遠超原網絡(任意連通圖)的規模時,其網絡異構性將更多地受到孤立節點的影響,也是符合實際的.值得注意的是,任意連通圖的Hd始終為log(n).因此只有當網絡非連通時,Hd的討論才有意義.

圖7 在20節點最近鄰耦合網絡外新增i個孤立節點后的網絡在不同K值下的結構熵Fig.7.K-order structure entropy at different in fluence scale K of different networks generated by adding isolated nodes to a 20 nodes nearest-neighbor coupled network,where the number of isolated nodes is i.

圖7 仿真了20節點最近鄰耦合網絡新增i個孤立節點后,其K-階結構熵隨K值的變化規律.圖8則繪制了20節點最近鄰耦合網絡新增i個孤立節點后,其Hd(minH),DD熵、Wu熵、SD熵、NB熵以及EB熵隨i的變化規律.

如圖8所示,Wu熵、SD熵、NB熵以及EB熵均認為n節點最近鄰耦合網絡新增i個孤立節點后,其網絡異構性要強于n+i節點最近鄰耦合網絡;但Wu熵、NB熵以及EB熵卻認為n節點最近鄰耦合網絡增添孤立節點前后的網絡異構性不發生變化,這一結論忽略了孤立節點對網絡結構的影響;而SD熵認為與原n節點最近鄰耦合網絡相比,網絡異構性隨增添孤立節點個數的增加先增大后減少,目前對于這一結論缺乏合理的解釋;DD熵認為n節點最近鄰耦合網絡增添i個孤立節點后,其網絡異構性要比n和n+i節點最近鄰耦合網絡都弱,與前文討論不一致.由此可見,K-階結構熵對最近鄰耦合網絡新增孤立節點后的網絡異構性的解釋更為合理.其實,K-階結構熵與Wu熵類似,均將節點作為基本單元來評價網絡的異構性,但本文將節點自身納入影響力范圍,從而避免了Wu熵中由于孤立節點度值為0所造成的分析上的不便.

綜上所述,K-階結構熵能夠較好地刻畫并區分規則網絡、隨機網絡、WS小世界網絡、BA無標度網絡以及星型網絡的異構性,認為以上網絡的異構性依次增強,與文獻[24]的理論研究保持一致.其中,K-階結構熵能夠較好地依據小世界屬性來刻畫WS小世界網絡的異構性,且對星型網絡異構性隨其規模演化規律的解釋也更為合理.此外,本文還分析了在規則結構外新增孤立節點后的網絡的異構性,認為n節點規則網絡增添i個孤立節點后,其異構性介于n和n+i節點規則網絡之間,并初步探索了minH和Hd之間的關系.

圖8 在20節點最近鄰耦合網絡外新增i個孤立節點后的網絡與20+i節點最近鄰耦合網絡的Hd(minH),DD熵、Wu熵、SD熵、NB熵以及EB熵 (a)Hd(minH);(b)DD熵;(c)Wu熵;(d)SD熵;(e)NB熵;(f)EB熵Fig.8.The Hd(minH),DD entropy,Wu entropy,SD entropy,NB entropy,EB entropy of(20+i)nodes nearestneighbor coupled networks and graphs generated by adding i isolated nodes to 20 nodes nearest-neighbor coupled networks:(a)Hd(minH);(b)DD entropy;(c)Wu entropy;(d)SD entropy;(e)NB entropy;(f)EB entropy.

3.4 美國西部電網

為了進一步闡述K-階結構熵評估網絡異構性的能力,本文以某一公用數據集為例進行說明.該數據集為美國西部電網[18],描述了美國西部高壓輸電網的拓撲結構,共有4941個節點,代表發電廠、變電站以及中間電氣連接點等場所;網絡共有6594條邊,代表輸電線和變壓器支路.該網絡規定各節點無差別,且忽略輸電線的物理構造及電氣參數差異,即認為各邊無差異,且無向無權.

Watts和Strogatz首次揭示了美國西部電網的小世界性,認為該網絡同時具有近似于同規模隨機網絡的較短的特征路徑長度,以及遠大于隨機網絡的平均聚類系數[18].表1列出了美國西部電網與同規模隨機網絡的平均聚類系數、特征路徑長度等參數.

表1 美國西部電網及同規模隨機網絡的網絡參數Table 1.Network features of the Western Power Grid of the United States and random networks.

由表1可知,美國西部電網的特征路徑長度僅為隨機網絡的2.33倍,而平均聚類系數是隨機網絡的510倍,以文獻[18]的觀點可認為美國西部電網是具有小世界性的.下面將基于K-階結構熵對美國西部電網進行考察.

圖9仿真了美國西部電網以及同規模最近鄰耦合網絡、WS小世界網絡、隨機網絡和BA無標度網絡在不同影響力尺度K下的結構熵.由圖9可見,美國西部電網的結構熵隨K先減少后增加,其minH約為11.95,與p=0.01下的WS小世界網絡最為接近(minH=11.997),遠大于BA無標度網絡(minH=11.544),且小于隨機網絡(minH=12.187).因此,從最強異構性minH的角度出發,可認為美國西部電網的異構性與小世界網絡相似,與前文平均聚類系數、特征路徑長度等特性的分析結果以及相關文獻[18,25-27]的研究均保持一致.

圖9 美國西部電網、最近鄰耦合網絡、WS小世界網絡、隨機網絡以及BA無標度網絡在不同影響力尺度K下的結構熵Fig.9.K-order structure entropy at different in fluence scale K of the Western Power Grid of the United States,nearest-neighbor coupled networks,WS small-world networks,random networks and BA scale-free networks.

前文指出,網絡的異構性還應從結構熵隨K值的變化規律等方面予以考察.然而,美國西部電網的結構熵HK隨K的變化曲線卻與WS小世界網絡、BA無標度網絡等模型存在較大的差異.其中,該電網minH所對應的K值為5,遠小于p=0.01下的WS小世界網絡(K=27),與隨機網絡(K=3)和BA無標度網絡(K=2)更為接近.事實上,Barabási和Albert等以美國西部電網為研究對象時指出,該電力網絡的度分布符合γ≈4的冪率形式,具有一定的無標度性[21],而WS小世界模型的度分布卻為泊松形式.此外,BA無標度模型的度分布雖為冪率形式,但其冪指數γ=3,與美國西部電網比較也存在差異;且BA無標度模型的聚類系數較小,無法體現美國西部電網的小世界性.

可見,若從minH的角度出發,可認為美國西部電網的異構性與小世界網絡相似,但若從K-階結構熵隨K值的變化規律的角度出發,美國西部電網的異構性又與隨機網絡、WS小世界網絡、BA無標度網絡均不相同.目前,本文未能定量地給出HK隨K值的變化規律與網絡特性之間的關系,不能確定美國西部電網的全部性質,且美國西部電網也十分復雜,并不完全符合WS小世界、BA無標度等傳統的理論模型.因此,深入探尋結構熵隨K值的變化規律與網絡特性之間的關系、探尋冪指數與minH等指標的關系、提出更符合諸如美國西部電網等實際網絡的模型,均為未來的工作提出了新的要求.

值得注意的是,本文是通過定義K-階鄰居數來計算K-階結構熵的,K-階鄰居數表征了某節點在K步內可達的節點總數,在一定程度上反映了節點的重要性,而節點重要性排序是研究網絡傳播效率等網絡功能的重要前提.顯然,節點重要性的排序將依K值的選擇而有所不同.依前文所述,當網絡具有最強的異構性時,各節點重要性分化達到最大限度.因此,選擇minH所對應的K值作為節點重要性排序的參數是最為合理的.此外,K-階鄰居數還可以作為社區結構劃分以及研究網絡傳播效率的依據.以社區結構劃分為例,由于社區內部節點間的連接較為密集,而社區之間的連接則相對稀疏,因此社區中心節點的K-階鄰居數往往較多,而社區邊界節點的K-階鄰居數則相對較少.由此,通過尋找被邊緣節點所分割的中心節點,便可實現網絡社區結構的自然劃分.這里仍可將minH所對應的K值作為社區結構劃分的參數選擇.而基于K-階鄰居數的節點重要性排序、社區結構劃分及網絡傳播等其他研究的具體過程本文不再展開敘述.

4 結 論

本文依據網絡節點在不同影響力尺度下的K-階鄰居數提出了一種K-階結構熵模型來評價網絡的異構性.K-階結構熵不是依據單一指標對網絡進行分析,而是基于不同的影響力尺度K對網絡的異構性進行多角度的討論.研究發現,K-階結構熵隨K的變化規律、最大影響力尺度d下的異構性Hd以及網絡能夠達到的最強異構性minH均可以從不同的角度反映網絡的異構性.通過對規則網絡、隨機網絡、WS小世界網絡、BA無標度網絡和星型網絡的理論研究和仿真分析發現,K-階結構熵模型能夠克服DD熵、Wu熵、SD熵、EB熵無法充分依據小世界屬性來反映網絡異構性的缺陷,并彌補了DD熵以及NB熵對星型網絡解釋的不足,且K-階結構熵對在規則結構外新增孤立節點的網絡異構性的解釋也優于其他結構熵.此外,本文還基于K-階結構熵對美國西部電網進行了討論.由于本文的主要工作集中于提出新的網絡結構熵模型以及利用經典的網絡結構進行實驗分析,對于網絡結構熵的定量計算、結構熵隨K值的變化規律與網絡結構特性之間的關系、基于K-階結構熵的節點重要性排序、社區結構劃分等其他應用將會是后續研究的重點.值得注意的是,本研究僅探索了在規則結構外新添孤立節點的特殊情況,對其他拓撲結構添加孤立節點后,結構熵隨K的變化規律、Hd與minH之間的關系等問題也仍需進一步探索.