索 琪， 郭進利(.上海理工大學管理學院，上海 200093；2. 青島科技大學經(jīng)濟與管理學院，山東 青島 26606)

“隨機”與“擇優(yōu)”
——超網(wǎng)絡(luò)演化的內(nèi)在驅(qū)動力

索 琪1,2， 郭進利1
(1.上海理工大學管理學院，上海 200093；2. 青島科技大學經(jīng)濟與管理學院，山東 青島 266061)

基于“隨機連接”和“擇優(yōu)選擇”的演化機制，構(gòu)建了一個隨機-擇優(yōu)混合超網(wǎng)絡(luò)演化模型。使用Poisson 過程理論和連續(xù)化方法對模型進行分析，獲得超度分布的解析表達式，分析表明網(wǎng)絡(luò)的穩(wěn)態(tài)平均超度分布服從漂移的冪律分布。該模型可以退化到復雜網(wǎng)絡(luò)和超網(wǎng)絡(luò)中的標準模型，具有一定的普適性。通過調(diào)節(jié)機制系數(shù)，模型可以體現(xiàn)混合連接機制。并對3個實證數(shù)據(jù)進行了分析，該模型能有效刻畫不同數(shù)據(jù)的演化機理。

復雜網(wǎng)絡(luò)；超圖；超網(wǎng)絡(luò)

0 引言

1999年，Barabási通過對社會、經(jīng)濟、技術(shù)等大量系統(tǒng)統(tǒng)計發(fā)現(xiàn)，多數(shù)復雜網(wǎng)絡(luò)的度分布服從冪律分布。他們提出了經(jīng)典的BA模型，認為增長和擇優(yōu)連接機制是驅(qū)動這種無標度網(wǎng)絡(luò)演化的重要機制[1]。此外，他們認為當新節(jié)點隨機連接老節(jié)點時，度分布呈指數(shù)分布。此后，在BA模型的基礎(chǔ)上，學者建立了各種網(wǎng)絡(luò)模型刻畫網(wǎng)絡(luò)的拓撲性質(zhì)及演化機理。復雜網(wǎng)絡(luò)基于普通圖的拓撲結(jié)構(gòu)，即用節(jié)點代表實際系統(tǒng)中不同的個體，用連邊代表節(jié)點之間的關(guān)系，且一條連邊只能關(guān)聯(lián)2個節(jié)點。但是，現(xiàn)實網(wǎng)絡(luò)的很多特征無法用它全面有效地描述[2]。如科研合作網(wǎng)絡(luò)只能描述兩兩作者之間的合作情況。此外，文獻[3]討論了含有用戶、商品以及標簽3類節(jié)點的推薦系統(tǒng)，普通圖很難刻畫這種多元關(guān)系。Berge[4]給出了超圖理論的基本概念和性質(zhì)，由于超圖中的一條超邊可以包含多個節(jié)點，基于超圖理論的超網(wǎng)絡(luò)能夠更有效地描述各個節(jié)點之間的相互作用和影響。如將作者視為節(jié)點，由若干個作者共同合作完成的論文視為超邊，可以構(gòu)建科研合作超網(wǎng)絡(luò)?；谠摮W(wǎng)絡(luò)可以獲得一篇論文是否由3個或更多的作者合作完成、以及每個作者發(fā)表的論文數(shù)量等信息。如供應鏈超網(wǎng)絡(luò)中，將供應商、制造商和消費者等視為節(jié)點，商貿(mào)對象之間存在的一次供需合作關(guān)系對應于一條超邊，可描述不同類型實體之間的多元合作關(guān)系?？梢?，超網(wǎng)絡(luò)方法作為一種全面、準確描述現(xiàn)實網(wǎng)絡(luò)的重要工具，必然引發(fā)未來的研究熱潮。

對復雜系統(tǒng)進行建?？梢杂行Ы沂酒鋬?nèi)在演化機理。目前，學者針對超網(wǎng)絡(luò)動態(tài)演化模型提出了不同的構(gòu)建方法。Zhang等[5]建立了一種基于用戶背景知識和對象、標簽雙重優(yōu)先連接機制的超圖增長模型。裴偉東等[6]研究了基于一類三角形結(jié)構(gòu)的動態(tài)網(wǎng)絡(luò)演化模型，利用平均場方法給出了這一類網(wǎng)絡(luò)結(jié)構(gòu)的理論解。基于增長和擇優(yōu)連接機制，Wang等[7]構(gòu)建的模型每次進入m個新節(jié)點，選擇1個老節(jié)點結(jié)合生成超邊；Hu等[8]構(gòu)造了另一類動態(tài)演化模型，每次進入1個新節(jié)點，選擇m個老節(jié)點生成超邊。上述兩個模型每個時間步只增加一條超邊。Yang等[9]探討了基于超邊增長和局域世界擇優(yōu)連接機制的超網(wǎng)絡(luò)演化模型。文獻[10]在超網(wǎng)絡(luò)中建立了一個將文獻[7]、[8]中的模型及BA模型統(tǒng)一的無標度模型。文獻[11]建立了非線性擇優(yōu)連接的非均齊超網(wǎng)絡(luò)演化模型。

現(xiàn)有超網(wǎng)絡(luò)模型的共同特點是基于“點超度擇優(yōu)”機制，即擇優(yōu)概率與被選節(jié)點的超度成正比。新節(jié)點傾向于連接到超度較大的節(jié)點，這種擇優(yōu)連接機制導致老節(jié)點的平均超邊數(shù)必然高于新節(jié)點，導致了“富者越富”現(xiàn)象。然而，很多真實網(wǎng)絡(luò)并未展現(xiàn)出冪律分布特征，因此其演化過程并不能很好地用上述機制描述。實際網(wǎng)絡(luò)中有些個體之間的連接是完全隨機的，Liu等[12]最早在復雜網(wǎng)絡(luò)中提出了隨機和擇優(yōu)混合模型，隨后學者也相繼研究了和隨機連接相關(guān)的演化模型[13-15]。能否構(gòu)建一個超網(wǎng)絡(luò)演化模型，考慮到超網(wǎng)絡(luò)演化過程中的隨機連接和擇優(yōu)選擇的增長機制，使得模型與實際網(wǎng)絡(luò)更好地吻合；并研究隨機概率對網(wǎng)絡(luò)結(jié)構(gòu)的影響，為真實網(wǎng)絡(luò)的演化過程提供某種解釋，是本文關(guān)注的重點。

1 隨機-擇優(yōu)混合超網(wǎng)絡(luò)演化模型

1.1 超網(wǎng)絡(luò)的概念

1.2 模型的構(gòu)造

隨機-擇優(yōu)混合超網(wǎng)絡(luò)模型滿足如下規(guī)則：

1) 初始化。網(wǎng)絡(luò)開始時有較少的節(jié)點(m0)，這m0個節(jié)點形成一條超邊。

2) 網(wǎng)絡(luò)增長?，F(xiàn)存文獻假設(shè)節(jié)點在等時間間隔離散地進入系統(tǒng)，為獲得網(wǎng)絡(luò)的統(tǒng)計信息，其研究中包含連續(xù)性假設(shè)，即將離散問題連續(xù)化。由于現(xiàn)實世界中網(wǎng)絡(luò)的增長是連續(xù)的，因此采用節(jié)點按Poisson過程隨機增長的網(wǎng)絡(luò)可以更好地刻畫現(xiàn)實。假設(shè)節(jié)點的到達過程是具有常數(shù)為λ的Poisson過程。在時刻t，當一批新節(jié)點(m1個)進入網(wǎng)絡(luò)時，這m1個新節(jié)點與已經(jīng)存在的m2(≤m0)個老節(jié)點形成一條超邊，共形成m(≤m0)條超邊，且不出現(xiàn)重超邊。

3) 連接機制。新節(jié)點在選擇網(wǎng)絡(luò)中已有的節(jié)點i時，以概率p隨機連接；以概率1-p依據(jù)超度擇優(yōu)連接，即老節(jié)點i被選中的概率W為

(1)

其中，ti表示第i批節(jié)點進入網(wǎng)絡(luò)的時刻，hj(t,ti)表示第i批進入的第j個節(jié)點在時刻t的超度，n(t)表示時刻t網(wǎng)絡(luò)中的節(jié)點數(shù)。以科研合作超網(wǎng)絡(luò)為例，將作者視為節(jié)點，由若干個作者共同合作完成的論文視為超邊。節(jié)點的超度越大，代表該作者參與撰寫的論文越多。點超度大的節(jié)點可能是本領(lǐng)域的專家，當新的作者進入網(wǎng)絡(luò)時會傾向于與專家合作，以提高自身的知名度，這體現(xiàn)為式(1)右端的第一項，即擇優(yōu)連接。另一方面，新的作者也可能以一定的概率隨機從網(wǎng)絡(luò)中選擇幾個作者進行合作，這體現(xiàn)為式(1)右端的第二項，即隨機連接。

2 演化模型理論分析

記N(t)={時刻t網(wǎng)絡(luò)的節(jié)點數(shù)}-m0=n(t)-m0， 根據(jù)Poisson過程理論，E[N(t)]≈λt。假定hj(t,ti)是連續(xù)實值變量，由于hj(t,ti)的變化率正比于概率W(hj(t,ti))，從而，由連續(xù)化方法可知hj(t,ti)滿足動態(tài)方程

(2)

(3)

由于hj(ti,ti)=m，解方程(3)，得

(4)

由式(4)，有

(5)

由Poisson過程理論，節(jié)點的到達時間ti服從參數(shù)為i與λ的Gamma分布Γ(i,λ)，有

(6)

將式(6)帶入式(5)，得：

(7)

(8)

由式(8)可知，該超網(wǎng)絡(luò)演化模型的穩(wěn)態(tài)平均超度分布為

(9)

(10)

文獻[15]提出了漂移的冪律分布(Shiftedpowerlaw，SPL)的概念，即P(k)∝(k+α)η，其中η和α是常量。SPL分布是介于指數(shù)函數(shù)和冪律分布之間的一種分布，α代表了該分布偏離冪函數(shù)的程度，α越大越偏離冪函數(shù)。由式(10)可知，隨機-擇優(yōu)混合超網(wǎng)絡(luò)演化模型的穩(wěn)態(tài)平均超度分布服從漂移的冪律分布。

當λ=m1=m2=1時，該超網(wǎng)絡(luò)模型退化到復雜網(wǎng)絡(luò)的混合模型。

當p→1時，α→∞，該超網(wǎng)絡(luò)模型的超度分布趨向于指數(shù)分布。由式(1)可知，此時的連接機制為完全隨機連接，導致了點超度呈指數(shù)分布。

當p介于0和1之間時，由式(1)可知，“隨機連接”和“擇優(yōu)選擇”兩種機制共同驅(qū)動了超網(wǎng)絡(luò)的演化。p值越大，“隨機連接”的驅(qū)動機制更明顯，點超度越趨向于指數(shù)分布；反之，“擇優(yōu)選擇”的驅(qū)動機制更明顯，點超度越趨向于冪律分布。通過調(diào)節(jié)參數(shù)p，超網(wǎng)絡(luò)模型的演化動力機制中的3種趨勢：隨機連接、擇優(yōu)選擇、以及兩者之間的混合連接機制可以體現(xiàn)出來，可以獲得具有特定超度分布的超網(wǎng)絡(luò)演化模型，因此該模型具有較強的適用性。

3 實證數(shù)據(jù)分析

3.1 電視節(jié)目競爭超網(wǎng)絡(luò)

數(shù)據(jù)來源于中央電視臺官方網(wǎng)站(http://cctv.cntv.cn，http://tv.cntv.cn/epg)。以中央電視臺的為例，為搶占收視率市場，在同一時間段播出的電視節(jié)目之間存在著激烈的競爭關(guān)系。由于每周播出的電視節(jié)目相對穩(wěn)定，因此以周為單位可以更完整地分析電視節(jié)目超網(wǎng)絡(luò)的整體特點。為方便統(tǒng)計，以2h為一單位對每天的播出時間離散化處理，分段初始點從周一0點開始，結(jié)束點為周日的22點，一周共分為84個播出時間段?；?5個中文頻道的227個播出時間相對穩(wěn)定的節(jié)目數(shù)據(jù)分析。將播出時間段定義為超邊，則該超網(wǎng)絡(luò)含有84條超邊；將電視節(jié)目定義為節(jié)點，則含有227個節(jié)點。電視節(jié)目在某個時間段播出，則稱該節(jié)點包含于該超邊中。

點超度的大小反映了一個節(jié)目在一周內(nèi)的播出次數(shù)，統(tǒng)計結(jié)果表明平均點超度為6.5，即平均每個節(jié)目每周播放6.5次。獲得點超度的累計分布如圖1所示，對數(shù)據(jù)進行SPL擬合，p(k)∝(x+45.78)-8.49，即α=45.78,p=0.77。說明驅(qū)動電視節(jié)目超網(wǎng)絡(luò)演化的因素既有擇優(yōu)機制，又有隨機機制。新節(jié)目進入網(wǎng)絡(luò)時，以概率0.23進行擇優(yōu)選擇，以概率0.77隨機連接。這與現(xiàn)實情況相吻合，由于黃金時段的收視率高，新的電視節(jié)目進入網(wǎng)絡(luò)時，會優(yōu)先考慮在黃金時段播出，即與該超邊所包含的節(jié)點構(gòu)成擇優(yōu)連接關(guān)系。但是，如果完全采用擇優(yōu)方式連接，這樣的網(wǎng)絡(luò)會存在弊端，會出現(xiàn)很多節(jié)目在黃金時段播出，而很多時段沒有節(jié)目播出的情況，這是不符合實際的，也無法從總體上滿足觀眾的收視需求。在電視節(jié)目的實際編排中，會根據(jù)電視觀眾的特征、收視的時間規(guī)律及收視內(nèi)容偏好，采取差異化的節(jié)目編排策略，進而全天候滿足不同觀眾不斷變化的收視需求。由于需要考慮的具體因素較多，節(jié)點之間的關(guān)聯(lián)相當于隨機選取。在這種混合的連接機制驅(qū)動下，可以獲得相對均勻的節(jié)目編排。

3.2 國內(nèi)電影演員合作超網(wǎng)絡(luò)

數(shù)據(jù)來源于Mtime時光網(wǎng)(http://www.mtime.com/)，以國內(nèi)電影為檢索詞，獲得了8 480部電影信息，及其主演信息。將電影定義為超邊，則該超網(wǎng)絡(luò)含有8 480條超邊；將演員定義為節(jié)點，則含有9 007個節(jié)點。如果該演員參演了某部電影，則稱節(jié)點包含于超邊中。點超度分布如圖2所示，對數(shù)據(jù)進行SPL擬合，p(k)∝x-2.08，即α=0,p=0，說明驅(qū)動該超網(wǎng)絡(luò)演化的機制是完全擇優(yōu)連接。這種機制導致點超度分布服從冪律分布。由圖2可見，數(shù)據(jù)存在明顯的胖尾現(xiàn)象，說明演員參演的電影數(shù)量是非均勻的。即大部分演員只參演了較少的幾部電影，而只有少量演員參與了多部電影的演出。網(wǎng)絡(luò)中最小點超度為1，最大點超度為82。平均點超度為2.56，即平均每個演員參演了2.56部電影。點超度大的節(jié)點代表該演員參與了多部電影的演出，對應于知名演員。在演員合作超網(wǎng)絡(luò)的演化過程中，當新演員進入網(wǎng)絡(luò)參演電影時，為了提高影片的票房，一般會選擇知名演員合作，利用其良好的口碑提高電影的競爭力；而知名演員也獲得了更多的參演機會，導致了“富者越富”現(xiàn)象。

3.3 豆瓣數(shù)據(jù)評論超網(wǎng)絡(luò)

豆瓣是中國最大的在線社交網(wǎng)站 (http://www.douban.com)之一，該網(wǎng)站允許注冊用戶描述其消費體驗，用戶可以對其體驗(或正在體驗)的資源 (包括圖書、電影、音樂等)進行評分和評論，也可以閱讀到其他用戶的信息和評論狀態(tài)。數(shù)據(jù)集記錄了383 033個用戶對80 008本圖書的評論數(shù)據(jù)，共3 648 105條記錄。將用戶定義為節(jié)點，將圖書評論關(guān)系定義為超邊，如果某個用戶對某本圖書進行了評論，則稱該節(jié)點包含于超邊中。點超度分布如圖3所示，對數(shù)據(jù)進行SPL擬合，p(k)∝(x+3.19)-2.59，即α=3.19,p=0.13。由圖3可見，數(shù)據(jù)存在明顯的胖尾現(xiàn)象，即用戶參與評論的圖書數(shù)量具有明顯的異質(zhì)性，大部分用戶只閱讀和評論了較少的圖書。最小點超度為2，最大點超度為4 110。平均點超度為9.52，說明每個用戶參與評論的平均圖書數(shù)量為9.52。驅(qū)動該超網(wǎng)絡(luò)演化的因素既有擇優(yōu)機制，又有隨機機制。新用戶進入網(wǎng)絡(luò)時，以概率0.87進行擇優(yōu)選擇，以概率0.13隨機連接。說明用戶在選擇圖書時，會優(yōu)先選擇一些優(yōu)質(zhì)圖書或暢銷圖書閱讀并評論，即與參與評論該圖書的用戶形成了擇優(yōu)選擇關(guān)系。此外，用戶還會根據(jù)自己的興趣愛好選擇圖書閱讀并評論，與網(wǎng)絡(luò)中的老用戶隨機連接。這兩種混合機制共同驅(qū)動了超網(wǎng)絡(luò)的演化。

上述3個實證結(jié)果顯示，超度分布均可以用式(10)中的漂移的冪律分布形式擬合，分布參數(shù)的大小可以表示出分布結(jié)果的不均勻性，也揭示了驅(qū)動超網(wǎng)絡(luò)演化的根本機制。

4 總結(jié)與展望

本文構(gòu)建了隨機-擇優(yōu)混合超網(wǎng)絡(luò)演化模型。對真實網(wǎng)絡(luò)研究發(fā)現(xiàn)，新節(jié)點在選擇老節(jié)點連接時，既存在擇優(yōu)選擇，又存在隨機連接的情形。因此，在連接機制的設(shè)置上，點超度擇優(yōu)和隨機選擇是驅(qū)動網(wǎng)絡(luò)演化的兩個重要因素。該連接機制可以更好地反映節(jié)點在競爭環(huán)境中的演化規(guī)律，能夠更真實地反映節(jié)點間競爭獲得超邊的本質(zhì)特點。通過理論分析發(fā)現(xiàn)了隨機-擇優(yōu)混合超網(wǎng)絡(luò)的演化規(guī)律，獲得穩(wěn)態(tài)平均超度分布的解析結(jié)果。通過合適的參數(shù)選取，模型可以退化到復雜網(wǎng)絡(luò)中的混合模型和超網(wǎng)絡(luò)中的無標度模型，該特性顯示了模型的普適性。同時，該模型也能有效刻畫實證數(shù)據(jù)的演化機理。

目前對于超網(wǎng)絡(luò)的拓撲特征和演化機制的研究剛剛起步?，F(xiàn)有研究簡化了節(jié)點和超邊的關(guān)系和特征，對于超邊帶有邊權(quán)的加權(quán)超網(wǎng)絡(luò)、節(jié)點間連邊關(guān)系具有方向的有向超網(wǎng)絡(luò)、帶有壽命的節(jié)點老化超網(wǎng)絡(luò)、以及考慮退出機制的超網(wǎng)絡(luò)等問題都是未來亟待解決的研究方向。

[1]Barabási A L, Albert R. Emergence of scaling in random networks [J]. Science, 1999, 286 (5439): 509-512.

[2]王眾托. 關(guān)于超網(wǎng)絡(luò)的一點思考[J]. 上海理工大學學報, 2011, 33(3): 229-237. Wang Zhongtuo. Reflection on supernetwork [J]. University of Shanghai for Science and Technology, 2011, 33(3):229-237.

[3]Lü L, Medo M, Yeung C H, et al. Recommender systems [J]. Physics Reports, 2012, 519(1): 1-49.

[4]Berge C. Graphs and Hypergraphs[M]. Amsterdam: North-Holland Publishing Company, 1973.

[5]Zhang Z K, Liu C. A hypergraph model of social tagging networks [J]. Journal of Statistical Mechanics: Theory and Experiment, 2010, (10): P10005.

[6]裴偉東, 夏瑋, 王全來，等. 多三角形結(jié)構(gòu)動態(tài)復雜網(wǎng)絡(luò)演化模型及其穩(wěn)定性分析[J]. 計算機工程與應用, 2011, 47(23): 41-44. Pei Weidong, Xia Wei, Wang Quanlai, et al. Study of dynamic complex network evolving models with multi-triangular structure [J].Computer Engineering and Applications, 2011, 47(23): 41-44.

[7]Wang J W, Rong L L, Deng Q H, et al. Evolving hypernetwork model [J]. The European Physical Journal B-Condensed Matter and Complex Systems, 2010, 77(4): 493-498.

[8]胡楓, 趙海興, 馬秀娟. 一種超網(wǎng)絡(luò)演化模型構(gòu)建及特性分析[J]. 中國科學, 2013, 43(1): 16-22. Hu Feng, Zhao HaiXing, Ma XiuJuan. An evolving hypernetwork model and its properties [J]. Scientia Sinica:Physica, Mechanica & Astronomica, 2013, 43 (1): 16-22.

[9]Yang G Y, Hu Z L, Liu J G. Knowledge diffusion in the collaboration hypernetwork [J]. Physica A: Statistical Mechanics and its Applications, 2015, 419: 429-436.

[10] 郭進利, 祝昕昀.超網(wǎng)絡(luò)中標度律的涌現(xiàn)[J]. 物理學報, 2014, 63(9): 90207. Guo Jinli, Zhu Xinyun. Emergence of Scaling in Hypernetworks [J]. Acta Physica Sinica, 2014, 63(9): 90207.

[11] 郭進利. 非均齊超網(wǎng)絡(luò)中標度律的涌現(xiàn)——富者愈富導致冪律分布嗎[J]. 物理學報, 2014, 63(20): 208901. Guo Jinli. Emergence of scaling in non-uniform hypernetworks——does “the rich get richer” lead to a power-law distribution [J]. Acta Physica Sinica, 2014, 63(20): 208901.

[12] Liu Z, Lai Y C, Ye N, et al. Connectivity distribution and attack tolerance of general networks with both preferential and random attachments [J]. Physics Letters A, 2002, 303(5): 337-344.

[13] Li X, Chen G. A local-world evolving network model [J]. Physica A: Statistical Mechanics and its Applications, 2003, 328(1): 274-286.

[14] Zhang P P, Chen K, He Y, et al. Model and empirical study on some collaboration networks [J]. Physica A: Statistical Mechanics and its applications, 2006, 360(2): 599-616.

[15] Fu C H, Zhang Z P, Chang H, et al. A kind of collaboration-competition networks [J]. Physica A: Statistical Mechanics and its Applications, 2008, 387(5): 1411-1420.

[16] Estrada E, Rodriguez-Velazquez J A. Subgraph centrality in complex networks [J]. Physical Review E, 2005, 71(5): 056103.

[17] Estrada E, Rodriguez-Velazquez J A. Subgraph centrality and clustering in complex hyper-networks [J]. Physica A：Statistical Mechanics and its Applications, 2006, 364: 581-594.

(責任編輯 耿金花)

Both Random and Preferential Attachment—the Inner Motivation in the Evolution of Hypernetworks

SUO Qi1, 2, GUO Jinli1

(1.Business School, University of Shanghai for Science and Technology, Shanghai 200093，China;2. School of Economics and Management, Qingdao University of Science and Technology, Qingdao 266061,China)

An evolving hypernetwork model is constructed with both preferential and random attachment. We analyze the model by using Poisson process theory and a continuous technique, and obtain the stationary average hyperdegree distribution of the hypernetwork. The analytical result shows that the stationary average hyperdegree distribution can be described with “shifted power law” (SPL) function form. Our model is also universal, in that the standard model in complex networks and scale-free model in hypernetworks can all be seen as degenerate cases of the model. By adjusting the parameter, the model can reflect the mixed-connection mechanism. In addition, three empirical data are analyzed, and can be effectively described by the model.

complex network; hypergraph; hypernetwork

10.13306/j.1672-3813.2016.04.007

2014-12-17；

2015-05-14

國家自然科學基金(71571119)；教育部人文社會科學研究項目(16YJC870012)；國家統(tǒng)計科學研究項目(2015LZ49)；青島市社會科學規(guī)劃研究項目(QDSKL150462)

索琪(1980-)，女，黑龍江哈爾濱人，博士研究生，講師，主要研究方向為復雜網(wǎng)絡(luò)、超網(wǎng)絡(luò)。

郭進利(1960-)，男，陜西西安人，博士，教授，主要研究方向為復雜網(wǎng)絡(luò)、人類行為動力學。

T94

A