超網絡中有壽命節點的進入、老化與退出機制

馬濤

（上海工程技術大學管理學院，上海 201620）

0 引言

增長與擇優連接是BA 模型的兩個特征，該模型認為網絡可以無限增長，而且認為節點的壽命也是無限的，不考慮節點壽命長短。然而，現實中的許多網絡中，節點是具有壽命的，不同節點的壽命有長短區別，新節點進入到網絡后，都會經歷這個過程，包括：成長、老化和死亡，例如：市場營銷渠道網絡中會有新公司進入，也會有公司退出，離開該網絡；產業鏈網絡中有的企業可能由于一些原因而被淘汰，也會有企業作為新的一員加入到該產業鏈中；科學家合作網的節點是有壽命的；電影演員合作網的節點是有壽命的；WWW 網基本上每時每刻都有新的網頁進入該系統，也會有網頁離開；在自然界中有新的物種出現，也會有一些物種消失。

目前，國內外學者對復雜網絡中節點老化現象進行了較多的研究，Moinet 等人[1]描述了網絡中節點的老化現象；Goldberg 等人[2]提出節點老化需要在引文網絡模型中得到體現，并使用一些數據對模型進行測試，來驗證模型是否正確；Dorogovtsev 等人[3]也對節點老化模型進行了研究，認為隨著節點壽命的增加，擇優性會衰減；Luo等人[4]在進化的傳感器網絡的拓撲結構中，考慮了能量意識機制，還討論了網絡中的節點和鏈接的變化；Sarshar等人[5]提出了一種日益增長的網絡研究模型，主要包括：新節點和鏈接的進入，現有鏈接的重組，以及節點的退出和補償連接機制。此外，目前也有對復雜網絡中的有壽命節點的進入退出機制進行研究的文獻，包括：節點具有壽命的企業生產物流系統復雜網絡模型[6]和M-G-P 型復雜網絡中有壽命節點的進入退出機制[7]。

綜上所述，對超網絡中有壽命節點的進入、老化與退出機制分析和描述的文獻很少。目前，劉艷等人[8]構建了一種基于超圖的復雜網絡的動態演化模型，在該模型演化過程中，既有新節點和新邊增加，也有舊節點和舊邊離開，而且不僅新添加的節點可生成新邊，網絡中的舊節點之間也可生成新邊。然而，文獻[8]的研究中沒有考慮節點的壽命，也沒有考慮節點的老化問題。因此，為了更好地理解真實網絡的變化，本文考慮到網絡中節點是有壽命的，在文獻[8]的基礎上提出了超網絡中有壽命節點的進入、老化與退出機制，新節點被增加到網絡之后，都要經歷成長、老化和死亡，即新節點進入、進入的節點會老化、老的節點會退出網絡。

1 基于超圖的超網絡

超網絡是一般網絡的一種自然推廣，超網絡可以被認為是一種特殊的復雜網絡。超網絡分為兩類：基于超圖的超網絡和基于網絡的超網絡。本文研究的是基于超圖的超網絡。超圖的圖形如圖1 所示。

圖1 超圖示例

超圖表示為：H=(V,E)，共有兩個集。V 是一個有限集，V={v1,v2,…,vn} 為節點集；E 為超邊集，E={E1,E2,…,Em} ，設Ei≠?(i=1,2,…,m)，超圖示例如圖1 所示，節點集V={v1,v2,v3,v4,v5,v6,v7} ，超邊集E={E1,E2,E3} ，其 中 ，E1={v1,v2,v3} ,E2={v4,v5} ,E3={v6,v7} 。

基于超圖的超網絡拓撲結構特征的研究中，對超網絡拓撲結構進行衡量的指標包括：節點的度、節點超度、超邊度、超邊超度及其分布、集聚系數、平均距離等。中心性被用來測量網絡中節點處于中心位置的程度。超網絡中節點中心性的測量包括：度中心性、介數中心性和接近中心性等。

2 超網絡中有壽命節點的進入、老化與退出機制

本文建立了Poisson 連續時間增長節點具有壽命的超網絡模型的新節點進入、節點老化和老節點退出的機制。機制的建立描述了超網絡的動態變化過程，對用超網絡刻畫的復雜系統的描述具有借鑒意義。因此，以BA 模型為基礎，我們提出了一個節點具有壽命的超網絡模型，即節點是具有壽命的，新的節點進入網絡、進入的節點會逐漸老化、老的節點會退出網絡。超網絡中新節點的進入可以形成新的超邊，超網絡中的舊節點之間的超邊可能消失，也可能會產生新的超邊。超網絡結構在不斷地變化，使得超網絡表現為一種動態而復雜的網狀結構。本文中舊節點和老節點的含義是不一樣的，超網絡中已有的節點被稱為舊節點，而隨著節點的老化，該老節點可能被刪除。

通過上述分析可知，超網絡表現出明顯的復雜性和動態性。為了有效研究超網絡，我們進行抽象化描述，新的節點進入網絡中，還會有新的連邊生成，而且，新進入的節點會老化，已存在于網絡中的一些老節點也會以一定概率被刪除，退出系統。新進入系統的節點在選擇舊節點形成新超邊時，會有某種傾向性存在，具有連接的偏好特性。舊節點之間的舊超邊可能消失，同樣舊節點之間連接形成新超邊時，在舊節點的選取上，也具有某種傾向性。根據假設條件，我們對Poisson 連續時間增長節點具有壽命的超網絡模型的新節點進入、老化與退出的機制描述如下。

2.1 新節點進入和節點老化

（1）泊松增長：網絡從少量的節點數量m0開始。在這個過程中，節點以批次的形式分批到達網絡，新節點批的到達過程是一個具有強度為λ的Poisson 過程。在時刻t，當一批新節點到達超網絡時，從服從分布F(η)的正整數中提取ηN(t)，ηN(t)是一個可變化的值，這ηN(t)個新節點與超網絡中已有的m1個舊節點形成一條新超邊，新超邊包含的節點中有m1個舊節點，ηN(t)個新節點。如果m1=0，新超邊中的所有節點都是新節點；如果ηN(t)=0，新超邊中的所有節點都是舊節點。每一條新超邊中包含的舊節點數m1是變化的，所包含的新節點數ηN(t)也是一個變化的值。

（2）擇優連接：為新節點選擇連接時，假設新節點連接到舊節點vi的概率∏(dH(vi))取決于舊節點vi的超度dH(vi)和它的年齡τi，即滿足：

其中，ti是節點vi進入網絡的時刻，τi=t-ti為節點vi的年齡。

上面公式（1）說明，隨著節點年齡的增長，其擇優性在減弱。隨著時間的增加，節點逐漸老化，則被新節點選擇的概率會降低。當節點達到一定的年齡（老齡化）時，新進入的節點將不再連接它。

2.2 老節點退出

刪除網絡中的某個老節點vl的概率為p(dH(vl))。刪除老節點依據概率：

選擇節點vl，dH(vl)是節點vl的超度；n≥0，稱為飽和因子，n 是與節點的年齡(t-ti)有關的，(t-ti)越大，n 越大，節點被刪除的可能性越大。

3 超網絡中有壽命節點的進入、老化與退出的演化模型

Barabasi 和 Albert［9］對 BA 模型進行了推廣，構建了一個更具有一般性的無標度網絡，即網絡不僅由于添加新節點而產生新邊外，網絡中的舊節點之間的連接既可能消失也可能會建立新的連接。在很多現實網絡中，邊可以通過連接新節點的方式增加，也可以在網絡中的舊節點之間創建新的連接。例如：在演員合作網絡中，節點表示演員，連邊表示影片。一部新的影片可以通過一些新演員和已有演員之間的合作來完成，也可以通過已有演員之間的合作來完成。

本文根據第3 部分的超網絡中的有壽命節點的進入、老化與退出機制，構建了基于超圖的超網絡動態變化模型：在變化過程中，不僅有新節點和新超邊進入超網絡，節點也會老化，也有老節點退出超網絡，除了新添加的節點與舊節點可以生成新超邊之外，并且超網絡中的舊節點之間也可以生成新的超邊，舊超邊也可能退出超網絡。在圖2 的六種動態模型中，前三種主要來自文獻[8]，后三種是本文在文獻[8]的基礎上首次提出。初始時假設超網絡有m0個節點。m 是新超邊含有的節點數，m1是新超邊中包含的舊節點數，ηN(t)是新超邊中包含的新節點數，m2是被刪除的老節點數[9]。圖2 模擬了當m=3，m2=1 時，超網絡動態演化過程，其中（a）是基礎圖，（1）-（6）為超網絡演化過程示意圖。圖 2 中的（1）-（6）是分別在基礎圖形（a）上做演化所得到的。在每個時間步內，下面6 種操作選其一。實際中，超網絡的演化過程有很多種形式，下面的6 種操作只是超網絡演化過程的部分舉例。圖2 中，舊節點用黑色實心圓點表示，新進入超網絡的節點用黑色空心圓點表示，舊超邊用實線圓圈表示，新超邊用虛線圓圈表示。

（1）在原有連接的基礎上，以概率p 增加一條新超邊。從超網絡的已有節點中根據概率擇優選擇m 個舊節點，生成一條新超邊，每次選取的舊節點vi的概率根據公式（1），如圖 2（1）所示。

（2）在原有連接的基礎上，以概率q 增加一條新超邊。首先從超網絡中隨機刪除一條舊超邊，再從超網絡已有節點中根據概率擇優選擇m 個節點，生成一條新超邊，每次選取舊節點vi的概率根據公式（1），如圖2（2）所示。

（3）以概率r增加ηN(t)個新節點和一條新超邊。這ηN(t)個新節點與超網絡中已有的m1個舊節點結合生成一條新超邊。當選擇舊節點vi與新節點相連時，舊節點vi根據擇優概率（1）式選取，如圖 2（3）所示。

（4）在原有連邊的基礎上，以概率s 增加一條新超邊。刪除超網絡中m2個老節點，刪除老節點的概率依據公式（2），然后從超網絡已有節點中根據概率優先選取m 個節點，生成一條新超邊。每次舊節點vi根據擇優概率（1）式選取，如圖 2（4）所示。

（5）在原有連邊的基礎上，以概率w 增加一條新超邊。首先從超網絡中隨機刪除一條舊超邊，同時刪除已有超網絡中m2個老節點，刪除老節點的概率依據公式（2），再從現有超網絡節點中根據概率優先選取m 個節點，生成一條新超邊。每次舊節點vi根據擇優概率（1）式選取，如圖 2（5）所示。

（6）以概率1-p-q-r-s-w 增加ηN(t)個新節點和一條新超邊，同時刪除超網絡中m2個老節點，刪除老節點的概率依據公式（2）。這ηN(t)個新節點與已有超網絡中的m1個舊節點結合生成一條新超邊。當選擇舊節點vi與新節點相連時，舊節點vi根據擇優概率（1）式選取，如圖 2（6）所示。

4 實例分析

企業科技創新團隊合作申請專利超網絡中，節點代表的是企業科技創新團隊人員，超邊代表的是科技創新團隊合作申請專利關系。該超網絡中的節點是有壽命的，這里的壽命不是人的自然壽命，而是指人員合作申請專利的壽命。在企業科技創新團隊合作申請專利超網絡中，可能會有新的人員加入超網絡中，長期不更新專業知識的人員會老化，即節點老化抽象為人員不更新專業知識，所導致的人員老化問題，超網絡中的已有的人員可能由于某些原因離開超網絡，超邊所表示的現有的科技創新團隊可能解散，也可能現有人員之間形成新的科技創新團隊，或者有新的人員加入與已有的人員組成新的科技創新團隊。因此，企業科技創新團隊合作申請專利的過程可以用圖2 描述。如圖3 所示是某高新技術企業科技創新團隊合作申請專利超網絡模型的演化過程圖[10]。

企業科技創新團隊合作申請專利超網絡最開始的初始時間是t=0，該超網絡隨著時間逐步演化，圖3 超網絡演化過程分為6 個時間點，從t=1 到t=6。圖3 是整體超網絡隨著時間發展所進行的逐步演化。圖3 中每一步的演化都是根據圖2 基于超圖的超網絡演化過程示意圖中的6 種操作來完成的。圖3 中，每條新超邊中的節點數都是3，m2是被刪除的老節點數，被刪除的老節點數都是1，每條新超邊中的新節點數、老節點數是變化的。

圖 3 中，t=1 時，以概率 p 在舊節點 v1、v4、v19之間增加一條新超邊E8，每次選取的舊節點vi的概率根據公式（1）；t=2 時，首先從超網絡中隨機刪除一條舊超邊E4，再從超網絡已有節點中根據概率擇優選擇3 個節點 v8、v9、v10，以概率 q 增加一條新超邊 E9，每次選取的舊節點vi的概率根據公式（1）；t=3 時，以概率 r 增加 2 個新節點和1 條新超邊。這2 個新節點v15、v16與超網絡中已有的1 個舊節點v12結合生成一條新超邊E10。當選擇舊節點vi與新節點相連時，舊節點vi根據擇優概率（1）式選取；t=4 時，刪除超網絡中 1 個老節點 v4，刪除老節點的概率依據公式（2），然后從超網絡已有節點中根據概率優先選取 3 個節點 v11、v15、v16，以概率 s 增加一條新超邊E11，每次舊節點vi根據擇優概率（1）式選取；t=5 時，首先從超網絡中隨機刪除一條舊超邊E6，同時刪除已有超網絡中1 個老節點v13，刪除老節點的概率依據公式（2），再從現有超網絡節點中根據概率優先選取 3 個節點 v7、v12、v15，以概率 w 增加一條新超邊 E12，每次舊節點vi根據擇優概率（1）式選取；t=6 時，以概率1-p-q-r-s-w 增加2 個新節點和1 條新超邊，同時刪除超網絡中1 個老節點v5，刪除老節點的概率依據公式（2）。這 2 個新節點 v17、v18與已有超網絡中的 1 個舊節點v16結合生成一條新超邊E13。當選擇舊節點vi與新節點相連時，舊節點vi根據擇優概率（1）式選取。

圖3 企業科技創新團隊合作申請專利超網絡模型演化過程圖

通過圖3 可知，t=0 時，該企業科技創新團隊合作申請專利超網絡中的節點數是15，超邊數是7，經過5個步驟，t=6 時，該企業科技創新團隊合作申請專利超網絡中的節點數是16，超邊數是11，超網絡圖形更加復雜，超網絡的密度增加，以及平均距離減小。從t=1到t=6，超網絡中節點數和超邊數都是變化的，該企業科技創新團隊合作申請專利超網絡是處于動態變化過程中的，以上體現了該企業科技創新團隊合作申請專利的演化過程。通過該演化過程，我們可以知道該超網絡中的人員和科技創新團隊的數量是動態變化的。因此，企業需要關注科技創新團隊人員以及科技創新團隊的變化，采取相應的措施來激勵人員更多地參與到科技創新團隊中，加強對人員的培訓，延長團隊人員的合作申請專利的壽命，同時在企業科技創新團隊的組建過程中，對人員的引進、選擇等方面也要進行充分地考量。

5 結語

本文基于現實網絡的特點，在超圖理論的基礎上，提出Poisson 連續時間增長的超網絡模型中有壽命節點的進入、老化與退出機制，包含：新節點的加入、節點老化和老節點退出。新的節點進入網絡中，還會有新的連邊生成，舊節點之間形成的超邊可能消失，舊節點之間也可能會產生新超邊。本文構建了一種基于超圖的超網絡動態演化模型，最后以某高新技術企業進行實例分析，進一步驗證了前面的假設。近年來，基于現實世界的超網絡特性的研究成果比較少，關于超網絡的演化還需要進一步開展相應研究。由于數據的缺少，所以實證研究需要進一步加強，超網絡演化模型的實證研究是需要繼續研究的問題。