傅春花 徐秀蓮 何大韌

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

關鍵詞： 集群系數; 頂點度; 實證統計; 數值模擬; 隨機概率

中圖分類號：N93? ? ? ? ? 文獻標志碼：A? ? ?文章編號：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 引言

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

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

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

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

本文研究目的在于討論復雜網絡中集群系數與頂點度的依賴關系。接下來將極其簡要地介紹我們所研究的一些實際系統，以及這些實際系統的網絡構成，重要的是給出我們所研究的這些實際網絡的集群系數對頂點度的依賴關系。之后將給出我們廣義合作網絡模型的數值模擬結果，并對結果進行了粗淺的分析。最后將給出本文的一些簡單的結論，期望對復雜網絡的研究具有一定的價值。

1 實證統計結果

統計調研了10個實際系統。表1為這10個實際網絡的具體描述。圖1至圖10為10個實際網絡的集群系數與頂點度的依賴關系。

2 模型數值模擬

2.1 廣義合作網絡模型

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

2.2 數值結果分析

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

2.2.1 項目大小為泊松分布（如圖11）

2.2.2 項目大小為指數分布（如圖12）

2.2.3 項目大小為冪律分布（如圖13）

3 結束語

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

參考文獻（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] 劉愛芬，付春花，張增平，?；郏未箜g.中國大陸電影網絡的實證統計研究[J].復雜系統與復雜性科學，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