1、關于為什么網絡會加速增長第1頁，共19頁，2022年，5月20日，17點22分，星期四報告提綱一、網絡加速增長現象二、加速增長現象的經濟學解釋三、網絡加速演化模型及其仿真分析四、結論與問題第2頁，共19頁，2022年，5月20日，17點22分，星期四一、網絡加速增長現象表現：平均度隨時間增加（邊比節點的增速更快）加速增長是實際網絡演化中的普遍現象已有數十類網絡被證實具有加速增長特性（因特網、萬維網、引文網、語言網、科學家合作網絡、生物代謝網絡、蛋白質作用網絡）科學家合作網 Barabsi et al. 2002因特網（AS層） Faloutsos et al. 1999第3頁，共19頁，202

2、2年，5月20日，17點22分，星期四網絡加速增長的兩種方式該圖引自： Sen，PRE , 2004方式a：邊只在新老節點之間產生，適用于描述引文網絡等少數網絡（但目前被研究得更多）；方式b：邊可以在老節點內部產生，符合大多數實際網絡的增長情況（目前尚未受到廣泛關注） 。第4頁，共19頁，2022年，5月20日，17點22分，星期四從邊增加的視角理解網絡加速增長在網絡“年輕”時，邊更多地是以連接新節點的形式增加；隨著網絡年齡的增長，越來越多的邊會在老節點之間產生；相對于邊增加的速度，網絡節點增加的速度越來越慢，網絡呈現邊加速增長的趨勢。第5頁，共19頁，2022年，5月20日，17點22分，星

3、期四二、網絡加速增長現象的經濟學解釋為什么一些實際的網絡會有前述這種“初期節點增速快，后期邊增速快”的規律？本文嘗試用經濟學中的效用理論來解釋這一現象產生的原因。微觀經濟學中的效用是用來描述消費品對消費者需求滿足程度的一個概念。根據效用最大化原理和隨機效用原理，效用越大的消費品被選擇的概率也越大。邊際效用遞減理論：在消費者連續消費某種消費品時，隨著所消費的該消費品的數量增加，其總效用雖然相應增加，但消費品的邊際效用（每消費一次所帶來的效用增量）有遞減趨勢。第6頁，共19頁，2022年，5月20日，17點22分，星期四邊際效用遞減導致網絡加速增長如果我們認為網絡是自組織的，那么可以把網絡自身理解

4、為一個消費者，把網絡演化過程中邊的增加理解為一次消費行為，而把邊連接新節點還是老節點理解為兩種消費品。在網絡增加邊的一次“消費行為”中，是選擇連接新節點還是選擇連接老節點，取決于這二者中的哪個會帶給網絡自身更大的“效用”。而根據邊際效用遞減理論，隨著網絡中邊數量的增加，連接新節點帶給網絡的效用會越來越小。因此，網絡會越來越不傾向于連接新節點，而是傾向于在老節點之間建立連接，網絡將呈現出邊加速增長的趨勢。 第7頁，共19頁，2022年，5月20日，17點22分，星期四對一些實際網絡的解釋公交網絡： 圖片來源：科學家合作網絡： 圖片來源：metrix.de第8頁，共19頁，2022年，5月20日，

5、17點22分，星期四三、網絡加速演化模型及其仿真分析根據以上討論，本文構造了一個網絡演化模型來模擬網絡加速增長的過程。它按照如下規則生成一個網絡：Step 1：初始化，令演化時刻 t = 0，創建一個包含n個節點(n2)的完全圖；Step 2：生成一個包含n個節點(n2)的完全圖，以正比于(t) 的概率選擇 m 個新節點(0 (t) 1 ，且(t)是一個減函數)，其余 n-m 個節點從現有網絡中按正比于節點度k 的概率選擇（即擇優連接）；Step 3：令t = t+1，返回Step 2，直到 t = T （給定的最大步長）。第9頁，共19頁，2022年，5月20日，17點22分，星期四對模型的

6、一些說明(1) 以完全圖作為網絡增長的基本單元更符合合作網絡演化的實際情況如果n=2 ，則每步演化加入的是一條邊，可以描述一些非合作網絡的加速增長。(2) 邊際效用遞減律體現在函數(t) 中0 (t) 1 ，且(t)是一個減函數可根據網絡增長特性取線性、指數、冪函數等多種形式(3) 模型的兩個特例(t) 為常數時，退化為RDP 模型 (Ramasco et al，2004) n=2 且(t) =0.5時，退化為BA模型(Barabsi et al , 1999)第10頁，共19頁，2022年，5月20日，17點22分，星期四模型度分布的初步解析如果(t) 為定值（與時間無關），則可用率方程解析

7、得到網絡的節點度分布為：上式為漂移冪律分布（Chang et al，2007），度分布指數（隨 的減小）從- 到 -2 變化。如果(t) 隨時間遞減，尚無法求得解析解，后面將給出度分布的仿真分析結果。第11頁，共19頁，2022年，5月20日，17點22分，星期四模型的仿真分析設定 n = 10, ，每演化100步，對網絡的主要拓撲性質進行一次統計，結果見下表：特征：平均度隨時間增加，平均距離隨時間下降，平均群聚系數隨時間下降*無論(t) 取線性、指數還是冪函數形式，均會出現這一規律第12頁，共19頁，2022年，5月20日，17點22分，星期四與科學家合作網實證數據的對比 平均度隨時間增加

8、平均距離隨時間下降 平均群聚系數隨時間下降數學領域（M）和神經科學領域（NS）科學家合作網從1991年到1998年的主要拓撲特征變化情況（圖引自： Barabsi et al. Physica A, 2002）第13頁，共19頁，2022年，5月20日，17點22分，星期四與城市公交網絡實證數據的對比城市公交線網拓撲特征統計（石家莊市1996-2008 ，每4年統計一次）石家莊市公交網絡的平均度隨演化時間增加而增加，平均群聚系數下降，與模型仿真結果相吻合。但網絡的平均距離卻也隨演化時間增加，這可能是由于公交網絡演化受空間距離約束，缺乏長程連接所導致的結果。第14頁，共19頁，2022年，5月2

9、0日，17點22分，星期四模型與實際網絡度分布的對比仿真模型的節點累積度分布石家莊市公交網絡站點累積度分布數學領域（M）和神經科學領域（NS）科學家合作網度分布（ Barabsi et al. 2002 ）第15頁，共19頁，2022年，5月20日，17點22分，星期四四、結論與問題結論：用經濟學中的效用理論解釋網絡加速增長現象產生的可能原因，認為若自組織網絡增加節點的邊際效用是遞減的，則網絡自身對效用最大化的追求會驅動網絡加速增長。揭示了導致網絡加速增長的一種可能機制。構建了一種加速增長的合作網絡演化模型，仿真分析結果表明，該模型能夠再現實際網絡加速增長的現象，一些關鍵拓撲性質與實證數據能夠較好地吻合。第16頁，共19頁，2022年，5月20日，17點22分，星期四需進一步研究的問題(1) 對模型網絡的拓撲性質進行精確解析由于(t) 隨時間遞減，這一點并不容易做到(2) 邊際效用遞減現象能否自發出現？本文模型的邊際效用遞減規則是人為設定的，能否構造一種模型，使網絡自發出現邊際效用遞減現象？(3)各種實際網絡增長速度的評價與調控增長速度如何影響網絡效率如何優化或引導網絡保持合理增速第17頁，共19頁，2022年