復雜網(wǎng)絡中k-核與網(wǎng)絡聚集系數(shù)的關聯(lián)性研究

劉君，喬建忠

（東北大學 信息科學與工程學院，遼寧 沈陽 110819）

1 引言

復雜網(wǎng)絡是一種新興的網(wǎng)絡研究理論，該理論正滲透到數(shù)理學科、生命學科和工程學科等眾多不同的領域。學術界關于復雜網(wǎng)絡的研究方興未艾。特別是，國際上有2項開創(chuàng)性工作掀起了一股不小的研究復雜網(wǎng)絡的熱潮。一是1998年Watts和Strogatz在Nature雜志上發(fā)表文章，引入了小世界(small-world)網(wǎng)絡模型，以描述從完全規(guī)則網(wǎng)絡到完全隨機網(wǎng)絡的轉變；二是1999年Barabási和Albert在Science上發(fā)表文章指出，許多實際的復雜網(wǎng)絡連接度分布具有冪律形式[1，2]。近些年，對于復雜網(wǎng)絡的研究出現(xiàn)了較多成果，大致可以分為 2類：1）結構分解類：理解真實世界中復雜網(wǎng)絡（如Internet，WWW，細胞組織網(wǎng)絡等）的體系結構并抽取出它們中緊密聯(lián)系的部分——社團、結構洞、k-核等，發(fā)現(xiàn)它們之間的聯(lián)系[3，4]。2）特征指標類：研究人員提出了一系列復雜網(wǎng)絡特征（如介數(shù)、度分布、聚集系數(shù)等）來描述真實世界中復雜網(wǎng)絡的拓撲結構。這些指標為宏觀統(tǒng)計學角度研究復雜網(wǎng)絡提供了非常有力的工具，例如通過統(tǒng)計Internet中節(jié)點的數(shù)據(jù)交互，分析獲取 Internet拓撲結構的介數(shù)、度分布、聚集系數(shù)等特征，依據(jù)這些統(tǒng)計特征就可以設計相應的實模來仿真Internet的拓撲結構。

總體來看，目前關于復雜網(wǎng)絡的研究多數(shù)只是停留在宏觀統(tǒng)計分析上，通過對某一事件的關聯(lián)數(shù)據(jù)進行統(tǒng)計，采用曲線估計、擬合等方法分析并找出規(guī)律，例如在文獻[5]中，作者就Internet的拓撲結構突發(fā)性改變展開研究，通過統(tǒng)計大量Internet的數(shù)據(jù)來嘗試解釋突變的原因。宏觀統(tǒng)計分析能夠從統(tǒng)計學角度解釋很多一直困擾讓人的問題，但是由于數(shù)據(jù)的偶然性和時間的局限性，很難確保統(tǒng)計的樣本量對于規(guī)律描述是充分的，此時需要一種科學客觀的復雜網(wǎng)絡拓撲結構描述理論。將宏觀統(tǒng)計分析與該結構描述理論相結合能夠更科學地解釋一些現(xiàn)象，然而目前對于復雜網(wǎng)絡拓撲結構描述理論方面的研究幾乎處于空白。k-核解析是一種高效的圖形分析方法，通過該方法，網(wǎng)絡逐漸趨于核心的區(qū)域，一些研究人員給出了定性的結論：越中心的核，連通性越強。但是為什么會出現(xiàn)這種規(guī)律，連通性增強的幅度等問題均未回答。為此本文從k-核解析模型著手，研究了其數(shù)學意義，推導分析了該模型與網(wǎng)絡聚集系數(shù)的關聯(lián)性。得出的相關結論能夠為k-核解析的進一步應用奠定相應的基礎。

2 k-核解析模型

設圖G= (V，E)是由|V| =n個節(jié)點和|E|=e條邊所組成的一個無向圖，則k-核的定義[6]如下。

定義1k-核（k-core）。由集合C?V推導出的子圖H=(C，E|C)，當且僅當對C中的任意節(jié)點v，其度值均大于或等于k，即?v∈C： degreeH(v)≥k，具有這一性質的最大子圖就叫作k-核。核中包含的節(jié)點數(shù)目則稱為核的大小。依據(jù)k-核的定義，圖G的k-核就可以通過反復地移去那些度值小于k的節(jié)點以及與其連接的邊，直到余下圖中所有節(jié)點的度值都大于或等于k來得到。因此可以通過k-核解析由外層至內(nèi)層一層一層地解析網(wǎng)絡，直到最內(nèi)層為止，從而揭示網(wǎng)絡的層次結構性質。

圖1所示為k-核解析的流程。首先按照k-核定義去掉圖1中度值為1的黑色節(jié)點及其邊，剩下的由灰色與白色節(jié)點構成的拓撲圖即為2-核；然后去掉度值為2的灰色節(jié)點，剩下的由白色節(jié)點構成的拓撲結構圖為3-核。需要注意的是，若圖1中出現(xiàn)Y4節(jié)點，按照核解析的定義，需要反復去掉度值為2的節(jié)點，因此{Y1，Y2，Y3，Y4}都將會在2-核解析過程中被去除，即雖然它們初始度值不同，但是最終都屬于2-層節(jié)點。

3 k-核與聚集系數(shù)關聯(lián)性分析

大量文獻給出了關于k-核解析的定性描述：高核內(nèi)節(jié)點的連通性高、傳播性強。但是連通性、傳播性到底代表什么，用什么來表示，均未給出詳細定量的描述。本文將連通性、傳播性統(tǒng)稱為小世界特性，并引入網(wǎng)絡直徑與聚集系數(shù)概念來表征網(wǎng)絡小世界特性的強弱。網(wǎng)絡直徑越小、聚集系數(shù)越大的網(wǎng)絡小世界特性越強，反之越弱。

圖1 k-核解析示意

定義 2節(jié)點聚集系數(shù)(clustering coefficient)[7～9]。某節(jié)點i的聚集系數(shù)為該節(jié)點所有鄰居節(jié)點之間連接數(shù)目占可能的最大連接數(shù)目的比例

其中，li為節(jié)點i的鄰居節(jié)點個數(shù)，Ei為這li個節(jié)點之間存在的連接數(shù)目。一個網(wǎng)絡的聚集系數(shù)為網(wǎng)絡中所有節(jié)點CCi的均值C。節(jié)點聚集系數(shù)是反映節(jié)點在網(wǎng)絡連通性特征上貢獻的一個重要指標。網(wǎng)絡聚集系數(shù)是反映網(wǎng)絡拓撲結構連通性、傳播性的一個關鍵因素。

定義 3網(wǎng)絡直徑。指網(wǎng)絡中任意兩節(jié)點間跳數(shù)的最大值[10，11]。網(wǎng)絡直徑與聚集系數(shù)共同確定著網(wǎng)絡小世界特性的強弱。例如圖2(a)網(wǎng)絡的網(wǎng)絡直徑為6跳，網(wǎng)絡聚集系數(shù)Ca為

由此可以看出圖 2(b)網(wǎng)絡的小世界特性較圖2(a)網(wǎng)絡的小世界特性強，即連通性、傳播性均要高于圖2(b)網(wǎng)絡。因此在圖1給出的網(wǎng)絡拓撲基礎上進行k-核解析滿足上文提及的“高核對應著高連通性與傳播性”結論。但是是否在任意給定的拓撲結構中這一結論均成立？下文將圍繞這個問題對命題1展開論證。

圖2 k-核解析局部示意

命題1在給定網(wǎng)絡拓撲上，不斷進行k-核解析，若k核對應的網(wǎng)絡聚集系數(shù)為Ck，k+1核對應的網(wǎng)絡聚集系數(shù)為Ck+1，則有Ck+1＞Ck；若k核對應的網(wǎng)絡直徑為Dk，k+1核對應的網(wǎng)絡直徑為Dk+1，則有Dk＜Dk+1。

證明 首先關于網(wǎng)絡直徑的變化：由k-核解析的定義可知，隨著核數(shù)的增加，k核變?yōu)閗+1核時，網(wǎng)絡中節(jié)點數(shù)目是減少的，且節(jié)點間的連邊也是只有減少沒有新增。所以網(wǎng)絡中兩點間最大跳數(shù)不可能增加，即Dk＜Dk+1。其次關于聚集系數(shù)的變化，對式(1)進行變形

在任意結構中，k-核內(nèi)節(jié)點i的鄰居節(jié)點數(shù)ki為常數(shù)，能影響k-核結構中節(jié)點i聚集系數(shù)的因素為Ei(k)。此外通過式(4)可以看出k核中節(jié)點i的聚集系數(shù)CCi(k)與k核拓撲中節(jié)點i的鄰居節(jié)點間連邊數(shù)目呈離散線性方程關系，其中，Ki(k)為k核中節(jié)點i對應方程系數(shù)。

圖3為拓撲由k-核向k+1-核解析的示意，k-核內(nèi)節(jié)點I、J的度值為dJ(k)與dI(k)，且 dJ(k)＜dI(k)。節(jié)點I為J的鄰居節(jié)點，在該次解析過程中按照k-核解析的原則將被去除，且J節(jié)點能夠保留在更高核內(nèi)。當節(jié)點I被去除時，對于拓撲中其他剩余節(jié)點對應聚集系數(shù)將會有2種結果：保持不變或改變。

圖3 k-核向k+1-核解析示意

本文主要討論節(jié)點I被去除后聚集系數(shù)發(fā)生變化的節(jié)點。例如以圖3中的節(jié)點J為例，節(jié)點I為J的鄰居節(jié)點，且節(jié)點I與J的其他鄰居節(jié)點存在連邊，則I的去除將會影響節(jié)點J的聚集系數(shù)。由于給定拓撲的聚集系數(shù)與拓撲內(nèi)部連邊數(shù)目呈過原點的線性關系，如圖4所示，因此，只需要確定式(4)線性方程中的Ki(k)即可確定k-核與k+1-核對應的線性圖。從圖4中可以看出，若k-核解析后節(jié)點J的鄰居節(jié)點間連邊數(shù)目相等，即EJ(k)=EJ(k+1)，則k+1核中節(jié)點J對應的網(wǎng)絡聚集系數(shù)大于k核中節(jié)點J對應的網(wǎng)絡系數(shù)。

圖4 聚集系數(shù)與Ei的線性方程

然而由于k-核解析，I節(jié)點被去除后，導致了k+1核中連邊數(shù)目發(fā)生了減少，即I被去除后，KJ(k)＜KJ(k+1)，但是EJ(k)＞EJ(k+1)，難以確定最終節(jié)點J聚集系數(shù)的變化。對于圖3給出的拓撲結構，按照k-核解析的原則可以得出如下推論。

1) 由于k-核中節(jié)點J的度值為dJ(k)，因此，k-核中節(jié)點I的度值dI(k)最大為dJ(k)-2，因為若dI(k)=dJ(k)-1，則當I被去除后節(jié)點J的度值也將變成dJ(k)-1，依照k-核解析定義，J節(jié)點也將被去除，這與原設定不符。

2) 當k-核內(nèi)節(jié)點I被去除后，(k+1)-核中節(jié)點J鄰居節(jié)點連邊數(shù)目相對于k-核中節(jié)點J鄰居節(jié)點連邊數(shù)最多減少dJ(k)-3條，即EJ(k)-EJ(k+1)＜=dJ(k)-3，因為即使節(jié)點I在k-核內(nèi)取最大度值dJ(k)-2，節(jié)點J鄰居節(jié)點連邊數(shù)目中I節(jié)點的所占據(jù)的連邊數(shù)目應為I的度值減去I與J之間的一條連邊，即為dJ(k)-2-1。

3) 當k-核內(nèi)節(jié)點I被去除后，k+1-核內(nèi)每個節(jié)點度值最小為dI(k)-1，因為若某個節(jié)點度值為dI(k)-2，則該節(jié)點將與節(jié)點I一起被去除。

圖 4中給出了k-核、(k+1)-核中聚集系數(shù)的函數(shù)直線，可以看出，EJ(k)與EJ(k+1)的差值若可以取任意值，則CCJ(k)與CCJ(k+1)的大小無法確定。但是通過上述結論可知EJ(k)與EJ(k+1)的差值最高為dJ(k)-3，在這個限制下CCJ(k)與CCJ(k+1)存在何種大小關系呢？

從圖 4中可以看出在給定某個EJ(k)值的前提下，隨著EJ(k)與EJ(k+1)的差值由零逐步變大，將會依 次 出 現(xiàn)CCJ(k)＜CCJ(k+1)、CCJ(k)=CCJ(k+1)和CCJ(k)＞CCJ(k+1)的關系。EJ(k)與EJ(k+1)的差值越小，則CCJ(k)＞CCJ(k+1)越不可能出現(xiàn)。因此，若當EJ(k)-EJ(k+1)=dJ(k)-3 時，CCJ(k)＜CCJ(k+1)，則可以得出結論：無論EJ(k)取何值，k+1-核對應的聚集系數(shù)將大于k核對應的聚集系數(shù)。當EJ(k)-EJ(k+1)=dJ(k)-3時，假設式(5)成立

又因為圖3中節(jié)點J的度值就是節(jié)點J鄰居節(jié)點的個數(shù)，因此dJ(k)=lJ(k)，所以式(6)可以演化為

由于節(jié)點I取得度值為dJ(k)-2，所以在k+1-核內(nèi)每個節(jié)點的度值最小為dJ(k)-1，去除與節(jié)點J的連邊。則在k+1-核內(nèi)，節(jié)點J的鄰居節(jié)點共有dJ(k)-1個，每個節(jié)點度值最小為dJ(k)-2。通過拓撲學不難得出，這dJ(k)-1個度值最小為dJ(k)-2的鄰居節(jié)點，構成的拓撲就是全連通拓撲結構，此時的EJ(k+1)為

式(8)證明了式(7)的成立，因此假設成立，即CCJ(k)＜CCJ(k+1)。

通過上述證明可以得出2點結論。

1) 在k-核解析過程中若被去除節(jié)點I的度值為dJ(k)-2，則k+1核中節(jié)點J的鄰居節(jié)點間將為全連通結構。

2) 在給定拓撲結構中進行k-核解析使拓撲結構由k-核變?yōu)閗+1-核，當去除一個低度值節(jié)點I時，若I節(jié)點的去除對原拓撲結構中節(jié)點J的聚集系數(shù)產(chǎn)生影響，且節(jié)點J保留至高核中時，則節(jié)點J在k+1-核中對應的聚集系數(shù)大于k-核中對應的聚集系數(shù)。即隨著k-核解析的進行，高核節(jié)點的聚集系數(shù)保持不變或者增高。

由上述結論不難看出，隨著低核節(jié)點的逐個去除，一方面導致高核中節(jié)點數(shù)目的降低，另一方面保留在高核中各個節(jié)點的聚集系數(shù)只增不減，因此高核拓撲結構最終對應的網(wǎng)絡聚集系數(shù)將會增加，即命題1成立。至此，關于命題1的證明結束。

4 實驗及仿真

為了檢驗命題1的正確性，本文設計了一個實驗，首先實現(xiàn)了Les Miserables網(wǎng)絡生成方法[12]，生成了一個復雜網(wǎng)絡，構建了網(wǎng)絡拓撲結構布局，然后借助于Gephi復雜網(wǎng)絡性能分析平臺，逐步進行k-核解析，統(tǒng)計每一個k值對應的網(wǎng)絡聚集系數(shù)。若隨著k值的增加，網(wǎng)絡聚集系數(shù)呈增長趨勢，則能夠驗證命題1的正確性。實驗相關的設置如表1所示。

表1 網(wǎng)絡仿真參數(shù)設置

圖5顯示了表1仿真環(huán)境下，不同k值設定下的網(wǎng)絡拓撲結構分解圖，可以看出，隨著k值的增加，網(wǎng)絡中節(jié)點越來越少，當k=10時，網(wǎng)絡消失，因此表1給出的網(wǎng)絡拓撲最高核為9。此外當k=5與k=6時，網(wǎng)絡拓撲結構沒有發(fā)生變化，因此當k=5時的網(wǎng)絡拓撲結構中所有節(jié)點度值均大于6。

圖5 k-1核解析分解

各個k值對應的網(wǎng)絡聚集系數(shù)如表2所示。

表2 k值與網(wǎng)絡聚集系數(shù)的對照

從表 2可以看出，隨著k-核的不斷解析、k值的不斷增加，網(wǎng)絡聚集系數(shù)呈現(xiàn)逐步增加的趨勢，該仿真測試結果與定理1相吻合。

5 結束語

本文主要對k-核解析與網(wǎng)絡聚集系數(shù)之間的關聯(lián)進行了論證研究。k-核解析是一種復雜圖分解的常見方法，但是隨著k-核的不斷分解，高核結構所體現(xiàn)出的特性到底如何變化是一項研究空白，本文針對網(wǎng)絡聚集系數(shù)這一特性，展開了研究。通過理論推導與證明，明確了k-核分解與網(wǎng)絡聚集系數(shù)之間的關聯(lián)，即越高核對應的網(wǎng)絡聚集系數(shù)越高，在此基礎上設計了實驗檢驗理論證明。本文得出的結論可以與現(xiàn)有宏觀統(tǒng)計分析方法相結合，為復雜網(wǎng)絡應用提供相應的理論基礎，例如重要節(jié)點或者結構發(fā)掘研究、網(wǎng)絡抗毀性研究等。以文中實驗為例，當9-核網(wǎng)絡對應的聚集系數(shù)為0.952，這表明該網(wǎng)絡中的小世界性很高，具有高傳播性和高抗毀性，對病毒預防領域中，該結構的危險性最高，通過本文后續(xù)研究能夠找出最優(yōu)結構調(diào)整策略，在微小刪邊代價下重構9-核，將能大大提高網(wǎng)絡病毒免疫能力。

在后續(xù)工作中，本文將重點研究網(wǎng)絡節(jié)點、邊的價值屬性，即當刪除/添加一個節(jié)點或者一條邊對網(wǎng)絡的聚集系數(shù)以及其他特征參數(shù)所產(chǎn)生的影響。k-核解析在某種意義上也是一種節(jié)點、邊的刪除行為，但是本文只是通過推導證明了k-核分解會造成網(wǎng)絡聚集系數(shù)的增加，但是并沒有給出具體增加的幅度。通過后續(xù)工作的研究，能夠為k-核解析提供一種全新的量化視角。

[1] 汪小帆， 李翔， 陳關榮. 復雜網(wǎng)絡理論及其應用[M]. 北京：清華大學出版社， 2006.49-70.WANG X F， LI X， CHEN G R. Theory and Applications of Complex Network[M]. Beijing： Tsinghua University Press， 2006.49-70.

[2] SONG C， HAVLIN S， MAKSE H A. Origins of fractality in the growth of complex network[J]. Nature Physics， 2006， 2(4)： 275-281.

[3] GOH K I， SALVI G， KAHNG B，et al. Skeleton and fractal scaling in complex networks[J]. Physical Review Letters， 2006， 96： 018701.

[4] GUO Q Z，et al. Exploring the local connectivity preference in Internet AS level topology[J]. Piscataway， 2007， 13(1)： 6439-6445.

[5] ZEGURA E W， CALVERT K L， DONAHOO M I. A quantitative comparison of graph-based models for internet topology[J].IEEE/ACM Trans on Networking， 1997， 5(6)：770-783.

[6] ONNELA， J. SARAMAKI， HYVONEN J. Structure and tie strengths in mobile commutation networks[J]. PNAS， 2007，104(18)： 7332- 7336.

[7] BARCELó J M， NIETO-HIPóLITO J I， GARCIA-VIDAL J. Study of Internet autonomous system interconnectivity from BGP routing tables[J]. Computer Networks， 2004， 45(3)：333-344.

[8] DIMITROPOULOS X， KRIOUKOV D， FOMENKOV M，et al. AS relationships： inference and validation[J]. SIGCOMM Computer Communications Review， 2007， 37(1)：29-40.

[9] PARK S T， PENNOCK D M， GILES C L. Comparing static and dynamic measurements and models of the Internet's topology[A]. Proceedings of the 23rd Annual Joint Conference of the IEEE Computer and Communications Societies[C]. 2004.1616-1627.

[10] ZHOU S， MONDRAGON R J. The rich-club phenomenon in the Internet topology[J]. IEEE Communication Letters， 2004， 8(3)：180-182.

[11] ZHOU S， MONDRAGON R J. Structural constraints in complex networks[J]. New Journal of Physics， 2007， 9(172)：1-11.

[12] KNUTH D E. The Stanford GraphBase： A Platform for Combinatorial Computing[M]. Addison-Wesley， Reading， MA， 1993.