傅春花 徐秀蓮 何大韌

摘? 要： 在大數(shù)據(jù)背景下，文章實(shí)證地研究了一類合作競(jìng)爭(zhēng)網(wǎng)絡(luò)的集群系數(shù)對(duì)頂點(diǎn)度的依賴關(guān)系，結(jié)果顯示兩者的依賴關(guān)系函數(shù)c（k）形式是多樣的，有指數(shù)形式、泊松形式和冪律形式。通過廣義合作網(wǎng)絡(luò)模型，在項(xiàng)目大小分布分別是指數(shù)分布、泊松分布和冪律分布的三種情況下，數(shù)值模擬了集群系數(shù)對(duì)頂點(diǎn)度的依賴關(guān)系。得到的結(jié)果與實(shí)證統(tǒng)計(jì)的結(jié)果相同，即c（k）有指數(shù)形式、泊松形式、冪律形式及SPL等多種形式，并得出隨機(jī)選擇舊節(jié)點(diǎn)連接的概率p越大，所得網(wǎng)絡(luò)的集群系數(shù)對(duì)頂點(diǎn)度的依賴關(guān)系越遠(yuǎn)離冪律形式，越接近均勻情況即指數(shù)形式或者泊松形式。

關(guān)鍵詞： 集群系數(shù); 頂點(diǎn)度; 實(shí)證統(tǒng)計(jì); 數(shù)值模擬; 隨機(jī)概率

中圖分類號(hào)：N93? ? ? ? ? 文獻(xiàn)標(biāo)志碼：A? ? ?文章編號(hào)：1006-8228（2019）01-21-04

Abstract： In the background of large data， this paper empirically studies the dependency of clustering coefficient on the degree of a vertex in a class of cooperative competition network. The results show that the dependency function c（k） of the two has various forms， such as exponential form， Poisson form and power law form. Based on the generalized cooperative network model， the dependence of cluster coefficients on vertex degree is numerically simulated in three cases： exponential distribution， Poisson distribution and power law distribution. The results are the same as those of empirical statistics， that is， c（k） has many forms， such as exponential form， Poisson form， power law form and SPL. The greater the probability P of random selection of old node connections， the farther the dependence of cluster coefficients on vertex degree of the network is from the power law form， but the closer to the uniform situation， i.e. exponential form or Poisson form.

Key words： clustering coefficient; degree of a vertex; empirical statistics; numerical simulation; probability

0 引言

復(fù)雜網(wǎng)絡(luò)，一個(gè)引起幾乎一切基礎(chǔ)學(xué)科和應(yīng)用學(xué)科注意的熱門研究領(lǐng)域，開始于1998年。它的研究和發(fā)展以圖論作為重要基礎(chǔ)，圖論的大量知識(shí)在網(wǎng)絡(luò)研究過程中得到了廣泛的應(yīng)用。之后，許多物理學(xué)家把統(tǒng)計(jì)物理學(xué)引入到復(fù)雜網(wǎng)絡(luò)的研究中，大家才知道，許多實(shí)際網(wǎng)絡(luò)的一些性質(zhì)：例如集群系數(shù)（clustering coefficient）、度（degree）分布、平均距離（averaged distance）等。

頂點(diǎn)度（degree of a vertex），用k表示，是復(fù)雜網(wǎng)絡(luò)研究中的一個(gè)重要的統(tǒng)計(jì)性質(zhì)。一般地，假設(shè)網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)i有ki條邊將它和其他節(jié)點(diǎn)相連，那么這ki個(gè)節(jié)點(diǎn)就是節(jié)點(diǎn)i的鄰點(diǎn)。某一節(jié)點(diǎn)i的頂點(diǎn)度ki，就定義為與該節(jié)點(diǎn)相連接的領(lǐng)點(diǎn)的總數(shù)，即節(jié)點(diǎn)的度表示為該節(jié)點(diǎn)的鄰點(diǎn)個(gè)數(shù)的總和。直觀上看，度越大的節(jié)點(diǎn)意味著它在某種意義上顯得越“重要”。

集群系數(shù)（clustering coefficient），用c表示，是復(fù)雜網(wǎng)絡(luò)研究中的另一重要統(tǒng)計(jì)性質(zhì)和概念。它表示網(wǎng)絡(luò)中某一節(jié)點(diǎn)的鄰點(diǎn)之間聯(lián)系的緊密程度。例如，在你的朋友關(guān)系網(wǎng)絡(luò)中，你的兩個(gè)朋友彼此間也是朋友的可能性大小。假設(shè)網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)i有ki條邊將它和其他節(jié)點(diǎn)相連，顯然，在這ki個(gè)節(jié)點(diǎn)之間最多可能有ki（ki-1）/2條邊，實(shí)際存在的邊數(shù)記為Ei。那么，節(jié)點(diǎn)i的集群系數(shù)ci定義為。與此等價(jià)的另一定義為，其中，與節(jié)點(diǎn)i相連的三元組是指包括節(jié)點(diǎn)i的三個(gè)節(jié)點(diǎn)，并且至少存在從節(jié)點(diǎn)i到其他兩個(gè)節(jié)點(diǎn)的兩條邊。整個(gè)網(wǎng)絡(luò)的集群系數(shù)c，就是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集群系數(shù)的平均值。很顯然，c的取值介于0到1之間。當(dāng)c=0時(shí)，說明網(wǎng)絡(luò)中所有節(jié)點(diǎn)均為孤立節(jié)點(diǎn)，即節(jié)點(diǎn)之間沒有任何連邊;c=1時(shí)，說明網(wǎng)絡(luò)中的任意兩個(gè)節(jié)點(diǎn)都直接相連。一般情況下，c的取值是在0到1之間的某個(gè)中間值。

Erzsébet Ravasz 和 Albert-László Barabási曾研究過復(fù)雜網(wǎng)絡(luò)的層次結(jié)構(gòu)與該網(wǎng)絡(luò)集群系數(shù)對(duì)頂點(diǎn)度的依賴關(guān)系密切相關(guān)[1]。他們提出，如果集群系數(shù)對(duì)頂點(diǎn)度的依賴關(guān)系函數(shù)c（k）是冪函數(shù)關(guān)系，即，則表明該網(wǎng)絡(luò)具有層次結(jié)構(gòu)。反之若c（k）不滿足冪函數(shù)關(guān)系，則該網(wǎng)絡(luò)無明顯的層次結(jié)構(gòu)。通過實(shí)證調(diào)研，我們也發(fā)現(xiàn)很多實(shí)際網(wǎng)絡(luò)的c（k）并不是很好的冪函數(shù)關(guān)系，甚至有些實(shí)際網(wǎng)絡(luò)的集群系數(shù)與頂點(diǎn)度是無相關(guān)的[2-5]。

本文研究目的在于討論復(fù)雜網(wǎng)絡(luò)中集群系數(shù)與頂點(diǎn)度的依賴關(guān)系。接下來將極其簡(jiǎn)要地介紹我們所研究的一些實(shí)際系統(tǒng)，以及這些實(shí)際系統(tǒng)的網(wǎng)絡(luò)構(gòu)成，重要的是給出我們所研究的這些實(shí)際網(wǎng)絡(luò)的集群系數(shù)對(duì)頂點(diǎn)度的依賴關(guān)系。之后將給出我們廣義合作網(wǎng)絡(luò)模型的數(shù)值模擬結(jié)果，并對(duì)結(jié)果進(jìn)行了粗淺的分析。最后將給出本文的一些簡(jiǎn)單的結(jié)論，期望對(duì)復(fù)雜網(wǎng)絡(luò)的研究具有一定的價(jià)值。

1 實(shí)證統(tǒng)計(jì)結(jié)果

統(tǒng)計(jì)調(diào)研了10個(gè)實(shí)際系統(tǒng)。表1為這10個(gè)實(shí)際網(wǎng)絡(luò)的具體描述。圖1至圖10為10個(gè)實(shí)際網(wǎng)絡(luò)的集群系數(shù)與頂點(diǎn)度的依賴關(guān)系。

2 模型數(shù)值模擬

2.1 廣義合作網(wǎng)絡(luò)模型

下面是我們?cè)趶V義合作網(wǎng)絡(luò)模型[8]的基礎(chǔ)上，對(duì)模型作了一定的修改，然后通過數(shù)值模擬得到了數(shù)值結(jié)果。設(shè)初始t=0時(shí)有m0個(gè)頂點(diǎn)，已經(jīng)聯(lián)接成若干個(gè)完全圖項(xiàng)目，它們的項(xiàng)目度hi0之和為h0。每步時(shí)間演化過程增加一個(gè)新頂點(diǎn)，然后，以一定的概率p隨機(jī)連接、以其余的概率（1-p）優(yōu)選連接，選取T-1個(gè)舊頂點(diǎn)，把這T-1個(gè)舊頂點(diǎn)和這個(gè)新頂點(diǎn)（共T個(gè)頂點(diǎn)）中兩兩之間尚未連接的邊都連上，構(gòu)成一個(gè)新的完全圖項(xiàng)目。共演化得到5000個(gè)項(xiàng)目，5000個(gè)節(jié)點(diǎn)。我們對(duì)項(xiàng)目大小（T）分別為泊松分布、指數(shù)分布和冪律分布時(shí)的三種情況進(jìn)行了數(shù)值模擬，結(jié)果將在后文詳細(xì)報(bào)道。

2.2 數(shù)值結(jié)果分析

下面是我們通過數(shù)值模擬得到的數(shù)值結(jié)果，圖11、圖12、圖13分別為項(xiàng)目大?。═）為泊松分布、指數(shù)分布和冪律分布時(shí)，當(dāng)網(wǎng)絡(luò)演化過程中新節(jié)點(diǎn)連接舊節(jié)點(diǎn)的選擇概率p取不同值時(shí)的情況得到的數(shù)值模擬結(jié)果。

2.2.1 項(xiàng)目大小為泊松分布（如圖11）

2.2.2 項(xiàng)目大小為指數(shù)分布（如圖12）

2.2.3 項(xiàng)目大小為冪律分布（如圖13）

3 結(jié)束語

本文對(duì)十個(gè)實(shí)際系統(tǒng)進(jìn)行了實(shí)證統(tǒng)計(jì)調(diào)研，主要研究了這十個(gè)系統(tǒng)的集群系數(shù)對(duì)頂點(diǎn)度的依賴關(guān)系，通過我們的研究發(fā)現(xiàn)，這些系統(tǒng)的c（k）關(guān)系函數(shù)形式是多樣的，有指數(shù)函數(shù)、泊松函數(shù)等，甚至還有線性函數(shù)。為了能找出這些實(shí)證結(jié)果的合理解釋，我們通過廣義合作網(wǎng)絡(luò)模型進(jìn)行了數(shù)值模擬。通過對(duì)模型數(shù)值模擬結(jié)果的分析比較，發(fā)現(xiàn)在網(wǎng)絡(luò)演化過程中，新節(jié)點(diǎn)選擇舊節(jié)點(diǎn)的隨機(jī)概率p越大，按照節(jié)點(diǎn)的項(xiàng)目度優(yōu)選的概率（1-p）越小，演化所得網(wǎng)絡(luò)的c（k）關(guān)系越遠(yuǎn)離冪律分布，越接近相對(duì)均勻的分布，即我們此處所述指數(shù)分布或泊松分布，而與網(wǎng)絡(luò)本身的項(xiàng)目大小分布是什么情況無關(guān)。

參考文獻(xiàn)（References）：

[1] Erzsébt Ravasz and Albert-László Barabási.Hierarchical organization in complex networks. Phys. Rev. E 67 026112，2003.

[2] Parongama Sen， Subinay Dasgupta et al. Phys. Rev. E 67036106，2003.

[3] Anjan Kumar Chandra and Subinay Dasgupta. Physica A，2005：357-436

[4] S. Battiston and M. Catanzaro. Eur. Phys. J. B 38 345（2004）.

[5] Wang Ru and Cai Xu. Chin.Phys.Lett，2005.22（10）：2715

[6] 劉愛芬，付春花，張?jiān)銎剑；郏未箜g.中國(guó)大陸電影網(wǎng)絡(luò)的實(shí)證統(tǒng)計(jì)研究[J].復(fù)雜系統(tǒng)與復(fù)雜性科學(xué)，2007.4（3）：10-16

[7] Fu C-H， Zhang Z-P， Chang H， Tao J-R， Chen Z-H， DaiY-L， Zhang W， He D-R. A kind of collaboration-competition networks[J]. Physica A， 2008.387：1411-1420

[8] Zhang P P， Chen K， He Y， Zhou T， Su B B， Jin Y， Chang?H， Zhou Y-P， Sun L-C， Wang B-H， He D-R. Model and empirical study on some collaboration networks[J]. Physica A，2006.360：599-616