多層網絡模型及其應用孫佩源2017年4月19日1多層網絡模型及其應用孫佩源11.背景現實網絡（社交網絡、引用網絡、腦網絡等）并非完全隨機節點度服從powerlaw（ScaleFree）節點間平均路徑長度很小（SmallWorld）現實網絡動態增長節點加入、撤離；邊的添加、刪除及重連接等仍保持ScaleFree和SmallWorld特性現實網絡通常呈現多層特性節點間存在多種連接關系交通網絡：公路，地鐵，高鐵等層間關系影響網絡的增長21.背景現實網絡（社交網絡、引用網絡、腦網絡等）并非完全隨2.Erdos-RenyiModel假設節點間邊的生成互相獨立整個網絡的似然度為：節點度分布為：泊松分布靜態網路單層網絡32.Erdos-RenyiModel假設節點間邊的生成互Barbieri,Nicola,FrancescoBonchi,andGiuseppeManco."Whotofollowandwhy:linkpredictionwithexplanations."KDD2014.假設網絡由ER生成過程生成（DirichletDistribution,BetaDistribution）通過節點上附著的標簽信息推測邊的存在及生成原因S.W.LindermanandR.P.Adams.Discoveringlatentnetworkstructureinpointprocessdata.ICML2014.假設網絡由ER生成過程生成通過在該網絡上的擴散數據推測邊的存在PeiyuanSun.InferringMultiplexDiffusionNetworkviaMultivariateMarkedHawkesProcess.擴展至多層網絡（仍基于ER生成過程）2.Erdos-RenyiModel泊松分布靜態網路單層網絡4Barbieri,Nicola,FrancescoBo優點簡單高效易與機器學習中概率圖模型結合缺點與現實網絡有出入節點度為泊松分布而非冪律分布不存在小世界現象集群現象也很少見效果一般擴展的Watts-Strogatz網絡滿足SmallWorld和Clustering，但仍為靜態單層網絡2.Erdos-RenyiModel泊松分布靜態網路單層網絡5優點2.Erdos-RenyiModel泊松分布靜態網路3.BAModel每個時刻加入一個節點并引入m條邊網絡中已存在節點i吸引其中一條邊的概率為：該模型生成網絡滿足節點度的冪律分布由生成過程可知為動態網絡模型冪律分布動態網路單層網絡PreferentialAttachment63.BAModel每個時刻加入一個節點并引入m條邊冪律分3.BAModel單個節點的度演化：冪律分布動態網路單層網絡73.BAModel單個節點的度演化：冪律分布動態網路單層3.BAModel整個網絡度分布：冪律分布動態網路單層網絡83.BAModel整個網絡度分布：冪律分布動態網路單層網優點簡單節點度滿足冪律分布，且為動態網絡缺點仍然與現實網絡有出入集群現象很弱現實網絡中節點度分布指數多有出入只能作為一個解釋型模型用于生成隨機網絡如LFRbenchmark即基于此模型的改進生成隨機圖LancichinettiA,FortunatoS.Benchmarksfortestingcommunitydetectionalgorithmsondirectedandweightedgraphswithoverlappingcommunities.[J].PhysicalReviewE,2009.（引用量477）3.BAModel冪律分布動態網路單層網絡9優點3.BAModel冪律分布動態網路單層網絡94.PAModelwithinitialattractiveness每個網絡節點s擁有一個初始的吸引參數：每個時刻加入一個節點并引入m條邊網絡中已存在節點s吸引其中一條邊的概率為：該模型生成網絡滿足節點度的冪律分布由生成過程可知為動態網絡模型冪律分布動態網路單層網絡104.PAModelwithinitialattra4.PAModelwithinitialattractiveness網絡模型中非常有用的套路：DifferenceEquation&GeneratingFunctionMethod該模型的MasterEquation為：冪律分布動態網路單層網絡114.PAModelwithinitialattra4.PAModelwithinitialattractiveness求解該MasterEquation：在t很大時，將差分轉化為微分在t很大時，假設網絡分布極限存在冪律分布動態網路單層網絡124.PAModelwithinitialattra4.PAModelwithinitialattractiveness求解該DifferenceEquation：假設生成函數：以及一些基本推論：冪律分布動態網路單層網絡134.PAModelwithinitialattra4.PAModelwithinitialattractiveness通過GeneratingFunction轉換為如下的DifferentialEquation:這里可以套用教科書中的經典結論求解之對比求解結果中Z的各次項系數可得：冪律分布動態網路單層網絡144.PAModelwithinitialattra4.PAModelwithinitialattractiveness類比該套路可得單節點的度隨時間變化公式：同時可得單節點度指數與整個網絡度分布指數關系：冪律分布動態網路單層網絡154.PAModelwithinitialattra4.PAModelwithinitialattractiveness優點：克服了BAModel中度分布指數為3的局限性得出了單節點度指數與整個網絡度分布指數的關系該模型假設較少，成為很多后續模型的基礎DorogovtsevSN,MendesJF,SamukhinAN.Structureofgrowingnetworkswithpreferentiallinking.[J].PhysicalReviewLetters,2000（引用量1385）缺點：在網絡度分布為2時失效集群現象較弱僅考慮單層冪律分布動態網路單層網絡164.PAModelwithinitialattra5.PopularityversusSimilarityModel生成過程：冪律分布動態網路單層網絡175.PopularityversusSimilarit5.PopularityversusSimilarityModel證明思路：求解圖中紅色區域的半徑落入該區域中節點的期望數為mhyperbolicdistance小于半徑得到網絡中已有節點吸引一條新邊

的概率等價于Model4則單節點度演化及網絡度分布等價

于Model4中結論冪律分布動態網路單層網絡185.PopularityversusSimilarit5.PopularityversusSimilarityModel模型變種：1.將與最近的m個節點連接擴展為

隨機選擇節點并以特定概率連接2.嘗試與每個節點以特定概率連接3.除了新節點加入的m條邊，已有

節點間也以一定概率生成邊冪律分布動態網路單層網絡195.PopularityversusSimilarit5.PopularityversusSimilarityModel擴展的意義：逐步加入缺失的現實因素生成的網絡盡量與現實網絡擬合冪律分布動態網路單層網絡20網絡度分布平均集群系數平均鄰居節點度距離分布平均中間性節點誕生與度分布5.PopularityversusSimilarit5.PopularityversusSimilarityModel坐標求解：根據全局極大似然度得出流行度坐標：節點度越大其出現時間越早根據每個節點的連接關系計算相似度坐標：

應用：根據現實網絡拓撲計算節點的坐標可用于社區檢測和鏈接預測冪律分布動態網路單層網絡21/305.PopularityversusSimilarit5.PopularityversusSimilarityModel社區檢測冪律分布動態網路單層網絡相似度坐標接近的節點地理上屬于同一國家22/305.PopularityversusSimilarit5.PopularityversusSimilarityModel鏈接預測冪律分布動態網路單層網絡在難預測鏈接上性能優于目前已有方法存在于低度節點間且沒有公共鄰居23/305.PopularityversusSimilarit優點：克服了Model4中度分布指數為2時失效的情形可以通過模型參數調節網絡的集群現象強度融入節點的相似度信息PapadopoulosF,KitsakM,SerranoMá,etal.Popularityversussimilarityingrowingnetworks.[J].Nature,2012.（引用量180）缺點：僅考慮單層245.PopularityversusSimilarityModel冪律分布動態網路單層網絡優點：245.PopularityversusSimi6.GrowingMultiplexNetworkModel生成過程：每個時刻網絡加入一個新增節點i該節點在每層均有一個stub節點并引入m條邊α層中j節點吸引其中一條邊的概率為：冪律分布動態網路兩層網絡F為同一節點在兩層中度的線性組合函數25/306.GrowingMultiplexNetworkM6.GrowingMultiplexNetworkModelMasterEquation:設為t時刻第1層節點度為k，第2層節點度為q的節點的數目

函數當k=q時為1，其他為0冪律分布動態網路兩層網絡新加入節點度為（k,q）時t時刻度為（k,q）且發生變化通過吸引一條新加入的邊度變為（k,q）初始條件26/306.GrowingMultiplexNetworkM6.GrowingMultiplexNetworkModel結論:當兩層節點同步到達時，即使關聯系數為0，仍然存在耦合關系當第2層節點到達時間為冪律延遲時，延遲指數

顯著影響層間關聯性

越小，層間關聯性越低

冪律分布動態網路兩層網絡27/306.GrowingMultiplexNetworkM6.GrowingMultiplexNetworkModel優點:首次提出多層網絡增長模型刻畫了節點延遲對層間關聯強度的影響缺點：