“隨機”與“擇優”
——超網絡演化的內在驅動力

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

“隨機”與“擇優”
——超網絡演化的內在驅動力

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

基于“隨機連接”和“擇優選擇”的演化機制，構建了一個隨機-擇優混合超網絡演化模型。使用Poisson 過程理論和連續化方法對模型進行分析，獲得超度分布的解析表達式，分析表明網絡的穩態平均超度分布服從漂移的冪律分布。該模型可以退化到復雜網絡和超網絡中的標準模型，具有一定的普適性。通過調節機制系數，模型可以體現混合連接機制。并對3個實證數據進行了分析，該模型能有效刻畫不同數據的演化機理。

復雜網絡；超圖；超網絡

0 引言

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

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

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

1 隨機-擇優混合超網絡演化模型

1.1 超網絡的概念

1.2 模型的構造

隨機-擇優混合超網絡模型滿足如下規則：

1) 初始化。網絡開始時有較少的節點(m0)，這m0個節點形成一條超邊。

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

3) 連接機制。新節點在選擇網絡中已有的節點i時，以概率p隨機連接；以概率1-p依據超度擇優連接，即老節點i被選中的概率W為

(1)

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

2 演化模型理論分析

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

(2)

(3)

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

(4)

由式(4)，有

(5)

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

(6)

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

(7)

(8)

由式(8)可知，該超網絡演化模型的穩態平均超度分布為

(9)

(10)

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

當λ=m1=m2=1時，該超網絡模型退化到復雜網絡的混合模型。

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

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

3 實證數據分析

3.1 電視節目競爭超網絡

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

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

3.2 國內電影演員合作超網絡

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

3.3 豆瓣數據評論超網絡

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

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

4 總結與展望

本文構建了隨機-擇優混合超網絡演化模型。對真實網絡研究發現，新節點在選擇老節點連接時，既存在擇優選擇，又存在隨機連接的情形。因此，在連接機制的設置上，點超度擇優和隨機選擇是驅動網絡演化的兩個重要因素。該連接機制可以更好地反映節點在競爭環境中的演化規律，能夠更真實地反映節點間競爭獲得超邊的本質特點。通過理論分析發現了隨機-擇優混合超網絡的演化規律，獲得穩態平均超度分布的解析結果。通過合適的參數選取，模型可以退化到復雜網絡中的混合模型和超網絡中的無標度模型，該特性顯示了模型的普適性。同時，該模型也能有效刻畫實證數據的演化機理。

目前對于超網絡的拓撲特征和演化機制的研究剛剛起步。現有研究簡化了節點和超邊的關系和特征，對于超邊帶有邊權的加權超網絡、節點間連邊關系具有方向的有向超網絡、帶有壽命的節點老化超網絡、以及考慮退出機制的超網絡等問題都是未來亟待解決的研究方向。

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

[2]王眾托. 關于超網絡的一點思考[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]裴偉東, 夏瑋, 王全來，等. 多三角形結構動態復雜網絡演化模型及其穩定性分析[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]胡楓, 趙海興, 馬秀娟. 一種超網絡演化模型構建及特性分析[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] 郭進利, 祝昕昀.超網絡中標度律的涌現[J]. 物理學報, 2014, 63(9): 90207. Guo Jinli, Zhu Xinyun. Emergence of Scaling in Hypernetworks [J]. Acta Physica Sinica, 2014, 63(9): 90207.

[11] 郭進利. 非均齊超網絡中標度律的涌現——富者愈富導致冪律分布嗎[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)；國家統計科學研究項目(2015LZ49)；青島市社會科學規劃研究項目(QDSKL150462)

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

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

T94

A