合作網絡高階聚集特性研究

楊忠明，梁本來，秦 勇，盧慶武

(1.廣東科學技術職業學院 計算機工程技術學院，廣東 珠海 519090; 2.中山職業技術學院 信息工程學院，廣東 中山 528404; 3.東莞理工大學 計算機學院，廣東 東莞 523808; 4.惠州學院 教育技術中心，廣東 惠州 516007)

合作網絡高階聚集特性研究

楊忠明1，梁本來2，秦 勇3，盧慶武4

(1.廣東科學技術職業學院 計算機工程技術學院，廣東 珠海 519090; 2.中山職業技術學院 信息工程學院，廣東 中山 528404; 3.東莞理工大學 計算機學院，廣東 東莞 523808; 4.惠州學院 教育技術中心，廣東 惠州 516007)

情報學領域的研究表明,研究工作者形成的科研合作關系網絡是一個非連通網絡,但是網絡統計參數呈現出無尺度網絡特性和小世界網絡特性,合作網絡是一種描述科研合作的典型網絡。提出高階聚集系數的概念，以期刊作者的合作網絡數據為計算案例，計算期刊合作者的高階聚集系數C(h)，形成圖表并分析其高階聚集系數C(h)在圖中所表示的意義。通過采集國內計算機類一級學報的大量合作者樣本數據并通過計算分析表明，合作者為20人左右時，合作團隊擁有廣泛的知識面和較高的合作水平，較易做出高水平的創新性成果，也意味著高水平的論文作者通常和學者20人左右直接或者間接保持合作關系。高階聚集系數同樣可用于語言網絡等其他呈現出小世界效應的網絡分析。

合作網絡；小世界網絡；高階聚集系數；平均距離

1 概 述

網絡可以用來描述人與人之間的社會關系、計算機之間的網絡聯接、網頁之間的超鏈接、科研文章之間的引用關系等，而統計物理學是從微觀到宏觀的橋梁。研究網絡中頂點與邊的度值與權值等微觀性質與網絡的幾何性質、效率與穩定性等宏觀性質之間的關系正是復雜網絡研究的核心內容。因而，與圖論的研究有所不同，復雜網絡的研究更側重于從各種實際網絡的現象之上抽象出一般的網絡幾何量，并用這些一般性質指導更多實際網絡的研究，進而通過討論實際網絡上的具體現象發展網絡上模型的一般方法，最后討論網絡本身的形成機制。在模型研究、演化機制與結構穩定性方面的豐富研究經驗是在復雜網絡研究領域得到廣泛應用的原因；而圖論與社會網絡提供的網絡靜態幾何量及其分析方法是復雜網絡研究的基礎，并得到了充分發展。合作網絡屬于復雜網絡中社會網絡的一種，它的提出是復雜網絡系統研究的一個新的方向[1]。小世界網絡中利用聚集度的計算來評價網絡指標、反映網絡性質的合作網絡已成為評價網絡指標的一種重要評價方法。根據權威文獻表明，合作網絡是一種優化評價網絡指標的評價系統，自1993年到2010年，持續多年的研究更表明了合作網絡的評價優化。科學合作的范圍隨著科學的進步而逐漸增長。論文合著是科學合作的表現之一，隨著不同領域的合作者的介入，科學合作成果的質量也越來越好，合作網絡成為更復雜的網絡。

一個典型網絡是由許多節點與連接兩個節點間的一些邊組成的，而復雜網絡簡單來說是呈現高度復雜性的網絡，具有結構復雜、網絡進化、連接多樣性、動力學復雜性、節點多樣性和多種復雜性融合的特點。復雜網絡是具有自組織、自相似、吸引子、小世界、無標度網絡中部分或全部性質的網絡。合作網絡是描述合作關系的網絡，它屬于復雜網絡中社會網絡的一種。

兩個現實的復雜網絡模型被廣泛應用：小世界模型和無尺度模型。文中重點討論小世界網絡，其特征是局部集群連接的長的線，平均距離之間的頂點的對數的增長與網絡中N的大小有關。以日常語言看，它反映的是相互關系的數目可以很小但卻能夠連接世界的事實，且小世界模型社會網絡就是小世界的一種。科研人員合作網絡是描述科研人員合作關系的網絡，通常把每個科研人員作為網絡中的一個頂點(或稱節點)，如果兩個科研人員之間共同發表過一篇論文，這兩個頂點之間就連接一條邊。科研人員之間形成了一個復雜網絡，該網絡的節點的復雜性、網絡演化特性以及網絡的合作行為等問題，所呈現出的密集度可以作為評價期刊的一個指標。研究基于合作網絡的期刊高階聚集特性分析，通過其看聚集度的計算發現目前研究熱點，同時聚集度越大，合作越緊密，可作為評價期刊的一個重要指標。

Watts和Strogatz[2]構造出一種介于規則網絡和隨機網絡之間的網絡(WS網絡)。隨后Newman和Watts[3]給出一種新的網絡構造方法。在NW網絡中，原有的連邊并不會被破壞，而是以一個很小的概率在原來的規則網絡上添加新的連邊，這樣構造出的網絡也同時具有大的簇系數和小的平均距離。BarabasiA[4]對科學合作社會網絡的演化進行研究，認為作者合作社會網絡是復雜網絡的代表。

Watts和Strogatz的研究方法是通過其中一個規則網絡轉化為小世界網絡，這種方法很少或基本沒有改變頂點度的分布和量化參數。小世界網絡中一個重要特征就是與隨機網絡相比有相當高的聚集系數，甚至比任意網絡的都要高。聚集系數的定義如下。頂點v在圖G中有相鄰節點度k(v)，k(v)的相鄰節點可能被連接成k(v)(l(v)-1)/2條邊。實際存在的最大可能的邊的分數數量就是圖G的聚集系數Cv，所有節點v的平均聚集系數就是網絡G的聚集度C。C的值接近于1意味著網絡是高連通的。

國內外學者在合作網絡的構造、靜態統計性質分析和演化模型等方面進行了研究。2006年Cardillo等分析了LosAlamos的2000-2005年間cond-mat數據庫，發現該庫的成長是通過合作網絡圖的連接增長體現的，主要特征體現在度-度相關性以及節點的聚集相關性[7]。周濤等提出了基于二分圖資源的推薦算法[8]。李曉佳等[9]在自建的合作網絡上，實現了層次聚集法和介數聚集法，在Newman的Q函數基礎上討論了聚集過程中的最佳集團數。還有學者從不同角度對社團網絡及其應用做了研究，如范超等[10]利用合作網絡及社會網絡的結構知識對CNM算法作了改進，提高了社團發現的精度。

黃開木等[11]以近30年國內“競爭情報”領域作者合著發表期刊論文為研究對象，分析表明該領域科學家的產量、最大合著群體的產量和所有合著群體的規模都滿足冪律分布。通過對該合著網絡最大連通子圖的統計分析，發現該合著群體具有高聚類和小世界性。

文中采集國內計算機領域一級學報的大量合作者樣本數據，分析期刊作者的合作網絡數據，計算其高階聚集特性，分析期刊的作者合作情況，把高階聚集系數的實驗結果作為評價和衡量期刊作者合作的重要指標。通過采集樣本期刊的合作者數據，計算合作者的高階聚集系數，分析期刊合作者情況，考慮以高階聚集系數作為評價期刊優劣的指標之一。

文中提出的合作網絡高階聚集特征還可用于其他呈現出小世界效應的網絡分析。在復雜網絡的研究中，語言網絡作為一個新的研究方向[12]，大都符合WS小世界模型，大多數節點只需經過少量的邊便可到達。在聚集系數上，與隨機語言網絡相比，真實語言網絡的聚集系數較高。Minett等基于詞典資源，根據漢語詞匯中的共字關系構建了漢字網絡[13]，由漢字構建的網絡表現出明顯的高聚集系數和無尺度特征。劉海濤對中文、英文等15種語言的依存句法網絡進行聚類研究[14]，得出這15種語言網絡均是小世界網絡，但聚集系數存在顯著差異，通過選擇網絡7組特征，對15種語言進行聚類，發現英語和漢語網絡整體上較接近。

2 合作網絡高階聚集特征描述

2.1 聚集系數及其含義

定義一個網絡或圖表G=(V,E)，設V有N個頂點或節點，E有M個邊或線段，每條邊定義為一對頂點(有序配對的有向圖)。讓一個頂點v有相鄰節點k(v)，k(v)的相鄰節點可能被連接成k(v)(l(v)-1)/2條邊。分數最大的邊事實上存在于相鄰的v和聚集系數Cv之間，平均聚集系數對所有v∈V是那個聚集系數C的網絡G。一個網絡C接近1可能包括聚集和有高度的連接，或稀疏的連接在本地群集中。

2.2 高階聚集系數的定義

文中延伸Watts和Strogatz的聚集系數，定義h是相鄰頂點v與頂點G的距離。假設v有鄰節點h和kh(v)，k1(v)與k(v)的定義見2.1。然后最多可以有kh(v)(kh(v)-1)/2條邊連接h的鄰節點v。這個分數Cv(h)允許的邊真實存在于h鄰節點v與聚集系數h之間。假設當kh(v)=1時Cv(h)=1，這也涵蓋了h=0時的特例。平均Cv(h)對所有v∈G，考慮高階聚集系數的概念，聚集系數為h時為C(h)。聚集系數為1時C(1)是聚集系數定義在2.1的C。

頂點為N的網絡有M條邊，可得公式P(0)=1/N，P(1)=2M/N2>1/N。在h=1以外，不能精確地表達該值為P(h)，除了以幾個固定網絡為例。很多網絡(小世界或反之)，P(h)的值與h一起上升直到最大值，然后下降至距離h與網絡直徑D越來越接近。

對于高階聚集系數，這一趨勢開始于聚集度減少，從C(0)=1到C(1)=C，然后是進一步減少。由于事實上h在增加，qh的節點數目按一定距離h的節點在增加，這些節點屬于幾個派系；因此，它們之間存在很多邊是不可能的。在h向D靠攏的過程中，會出現不同的效果。一個極端的例子是其中每個節點在網絡中到距離D的唯一節點(這有一個截然相反的單節點)，導致C(D)=1。同樣的情況，C(D-1)可能廣泛應用于鑒別存在多個直徑和相同的相對的頂點。應注意前面的意思是在h向D靠攏的過程中C(h)會變大，并非C(h)一定要大。

因為P(h)(上升然后下降)和C(h)(下降然后上升)的趨勢是相反的，所以P(h)C(h)應有一個上限值。因為一個常數c經常接近1但很少超過1，得出：

P(h)C(h)≤clogN/N

(1)

在這特例中h=1，方程(1)意味著P(1)C(1)≈logN/N。從小世界網絡中知道P(1)=2M/N2≈logN/N。對于該類網絡符合C(1)=C。

目前最有效的補充證據在方程(1)，利用這個確定性的小世界網絡提出這個模型。事實上，通過這個模型，可以發現這種趨勢表現在方程(1)。反觀確定性模型，這是基于Cayley的圖，提供了模型所需的支撐信息，從而可得該模型的聚集系數：

(2)

模型中，t=log2N和a=(2l-1)/t是自由調整參數，關系到互連密度，從而影響了C的價值。注意那個非常廣泛的網絡(N,t∞)，當a是常數時C趨向a2/(a+1)2。適當選擇a，能獲得不同的聚集系數，同時保持一個小的頂點使at+t-1=(a+1)log2N-1。

不像現實網絡中計算C(h)非常困難，文中提出的確定性模型服從數學分析，能用封閉形式表達一個高階聚集系數。在這個確定性模型中，對于數字m相鄰的頂點之間，在相鄰頂點h的任何頂點給出表達式：

(3)

數字kh(v)的相鄰頂點h的頂點v是有界的：

(4)

鑒于高階聚集系數C(h)與m/(kh(v))2成正比，很容易得到高階聚集系數為：

(5)

因此，定義聚集系數是基于相鄰的節點，高階聚集系數定義了涉及到一個更廣泛的相鄰距離參數h。利用實際上更廣泛的復雜網絡的實驗數據，依據文中提出的確定性小世界網絡模型，將網絡中有關C(h)和P(h)的距離分布，定義為有一定概率的隨機選擇的距離為h的一對頂點。

高階聚集系數是聚集系數的高度概括，并受聚集系統相關公式所控制。通過利用期刊作者所構成的網絡數據進行實驗和分析證明，不等式P(h)C(h)≤clogN/N在小世界網絡中成立。這一結果明顯表明該乘積P(h)C(h)有一個上限值，該上限值小于P(h)和C(h)的最大值。

高階聚集系數的計算可以應用在期刊合作者上。把期刊合作者的數據進行高階聚集系數C(h)的計算，可以得出一組關于頂點距離、階數、高階聚集系數C(h)和Cd*Pd等的數據。通過實驗把數據制作成圖表進行分析。期刊合作者的高階聚集系數能得出一組曲線圖，而這組曲線圖的高峰能表明這時合作者人數在期刊中的普遍性，以及此時的合作者人數能做出較好的科研成果。也可以根據曲線圖的高峰段來判斷合作者的作品情況，可作為期刊的評價方法之一。

3 實 驗

文中主要延伸Watts和Strogatz的聚集系數，計算期刊合作者的高階聚集系數C(h)，形成圖表并分析高階聚集系數C(h)所表示的意義。

通過中國期刊網采集了《計算機研究與發展》(2000-2010)2 610篇論文共2 764位作者數據、《計算機學報》(2000-2010)2 109篇論文共1 647位作者數據和《軟件學報》(2000-2010)2 602篇論文共2 462位作者數據。通過分類整理，分別把《計算機研究與發展》、《計算機學報》和《軟件學報》三大期刊的作者分別輸出，排列整理成文本數據，利用這些數據并通過延伸Watts和Strogatz的聚集系數，形成高階聚集系數C(h)以計算期刊合作者的高階聚集系數。高階聚集系數能反映出期刊作者在不同階段的聚集度。通過高階聚集系數的計算與分析，能從結果中判斷出期刊作者的密集性。通過輸出的結果把三大期刊三組數據分別進行計算并作圖，再進行比較。

3.1 高階聚集系數的計算方法與環境

2.3節推導了高階聚集系數的過程，利用此方法設計程序進行高階聚集系數的計算。對實驗數據首先計算最大連通子圖，計算出頂點數與平均距離，繼而計算各距離的點對數。根據平均距離數計算聚集度。

文中從中國期刊網將《計算機研究與發展》、《計算機學報》和《軟件學報》(2000-2010)的作者信息進行數據采集，分別整理成3個單獨存放作者信息的文檔，再把論文是兩位以上的作者進行分離和融合，形成每行為兩位作者名稱的格式。然后利用高階聚集系數計算程序對3大期刊的作者數據進行計算。最后把數據信息分別整理成圖表。

3.2 實驗結果

計算結果如圖1所示。

圖1 高階聚集系數計算結果

計算得出的圖呈現駝峰分布型，即會出現2次高峰，在3-5的作者點集中均出現1次高峰，在后期點集中會出現2次高峰。此2次高峰將會說明作者合作群的合作關系是比較容易做出高水平創新研究成果的。三大期刊的合作者數據構成了合作網絡，圖2顯示了三大期刊高階聚集系數的分布情況：點集表示期刊合作者的高階聚集系數。

圖2 三大期刊高階聚集系數分布情況

3.3 實驗分析與討論

從圖2中可以看出，圖中出現了兩個高峰。在合作者為2～3人的平均距離實驗結果中出現第一高峰，即2～3人的合作情況比較普遍。隨著合作者數量增加高階聚集系數減小，但是合作者20人左右時出現第二聚集系數高峰。此高峰表明合作者20人左右時，合作團隊擁有廣泛的知識面和較高的合作水平，較易做出高水平的創新性成果，也意味著高水平的論文作者通常和學者20人左右直接或者間接保持合作關系。可以看出，這三組數據的第二高峰都處于相似的階段，證明了高水平的論文作者和學者20人左右直接或間接保持合作關系。

4 結束語

文者提出的高階聚集系數是聚集系數的高度概括，并受聚集系數相關公式所控制。通過利用期刊作者所構成的網絡數據進行了實驗分析，表明高階聚集系數提供了對小世界網絡結構的新見解，為小世界網絡的探索提供了一個新的渠道。

通過實驗數據結果可以看出，高階聚集系數越高，期刊合作者合作關系越緊密，越能做出有水平的研究成果。2～3人的合作網絡比較普遍，但并不意味著2～3人的合作者模式容易做出高水平成果。通過第二聚集系數高峰進行分析更具說服力，在合作者規模為20左右的合作關系比較容易做出高水平創新研究成果。文中所提出的高階聚集系數還可應用于語言網絡等其他呈現小世界效應的網絡分析。

[1] 高 霞,陳凱華.合作創新網絡結構演化特征的復雜網絡分析[J].科研管理,2015,36(6):28-36.

[2] Watts D J,Strogatz S H.Collective dynamics of small word networks[J].Nature,1998,393(6684):440-442.

[3] Newman M E J,Watts D J.Scaling and percolation in the small-world network model[J].Physical Review E,1999,60:7332-7342.

[4] Barabasi A,Jeong H,Neda Z,et al.Evolution of the social network of scientific collaborations[J].Physical A,2002,311(3-4):590-614.

[5] Xiao Wenjun,Parhami B.Cayley graphs as models of deterministic small-world networks[J].Information Processing Letters,2006,97(3):115-117.

[6] 吳金閃,狄增如.從統計物理學看復雜網絡研究[J].物理學進展,2004,24(1):18-46.

[7] Cardillo A,Scellato S,Latora V.A topological analysis of scientific coauthorship networks[J].Physica A Statistical Mechanics & Its Applications,2006,372(2):333-339.

[8] Zhou Tao,Red J,Medo M,et al.Bipartite network projection and personal recommendation[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2007,76(2):70-80.

[9] 李曉佳,張 鵬,狄增如,等.復雜網絡中的社團結構[J].復雜系統與復雜性科學,2008,5(3):19-42.

[10] 范 超,王厚峰.社交網絡中的社團結構挖掘[J].中文信息學報,2014,28(1):56-63.

[11] 黃開木,樊振佳,盧勝軍,等.我國競爭情報領域期刊論文合著網絡研究[J].情報雜志,2015,34(2):142-147.

[12] 韓 普,王東波,路高飛,等.語言網絡研究進展[J].中文信息學報,2014,28(1):9-18.

[13] Minett J W,Peng G,Wang W S.The networks of syllables and characters in Chinese[J].Journal of Quantitative Linguistics,2008,15(3):243-255.

[14] 劉海濤.語言復雜網絡的聚類研究[J].科學通報,2010,55(27-28):2667-2674.

Study on Characteristics of High Order Clustering for Collaboration Network

YANG Zhong-ming1,LIANG Ben-lai2,QIN Yong3,LU Qing-wu4

(1.College of Computer Engineering and Technique,Guangdong Polytechnic of Science and Technology, Zhuhai 519090,China; 2.College of Information Engineering,Zhongshan Polytechnic,Zhongshan 528404,China; 3.College of Computer Science,Dongguan University of Technology,Dongguan 523808,China; 4.Information Technology Center,Huizhou University,Huizhou 516007,China)

The research made in the field of information science shows that scientific collaboration relationship network formed by the researchers is unconnected.While the characteristics of scale-free network and small-world network presented from the network statistical parameter shows that collaboration network is a typical network describing the scientific collaboration research.The concept of high order clustering coefficient is presented.With the use of network data of journal authors,it will calculate journal collaborators’ high order clustering coefficientC(h),andformachartandanalyzethesignificanceofC(h)inthechart.Theanalysisofalargeamountofcollaborator’sampledatacollectedfromthefirst-classdomesticjournalofcomputershowsthatwhenthenumberofcollaboratorsisaround20,thecooperationteamhasextensiveknowledgeandahighlevelofcooperationanditiseasierfortheteamtomakeahighlevelofinnovativeachievement.Thatmeansahigh-levelauthorwillusuallykeepacooperativerelationshipwithabout20scholarsdirectlyorindirectly.

cooperation networks;small world network;high order clustering coefficient;average distance

2016-03-06

2016-06-15

時間：2016-11-22

國家自然科學基金資助項目(61170193)；廣東省工業高新技術領域科技計劃項目(2013B010401036)；廣東省高等學校優秀青年教師培養計劃項目(YQ2014187)；廣東省自然科學基金項目(S2013010015940)；廣東省教育廳科技創新項目(2013KJCX0178)

楊忠明(1980-)，男，碩士，副教授，CCF會員，研究方向為計算機網絡、智能算法。

http://www.cnki.net/kcms/detail/61.1450.TP.20161122.1227.018.html

TP

A

1673-629X(2017)02-0200-05

10.3969/j.issn.1673-629X.2017.02.046