文章目錄

• 網絡與圖
• 網絡基本拓撲性質
• 度相關性與社團結構
• 節點重要性與相似性
• 隨機網絡模型
• 小世界網絡模型
• 無標度網絡模型
• 網絡傳播
• 網絡博弈

網絡與圖

一、網絡的定義
網絡的定義：網絡是由網絡連接設備通過傳輸介質將網絡終端設備連接起來進行數據交換、資源共享的平臺。

網絡的概念：具有獨立功能的計算機通過通信介質連接起來就形成了網絡。

計算機網絡相關知識：https://blog.csdn.net/weixin_43483442/article/details/107629665

二、圖的計算機表示：鄰接矩陣、三元組
最常見的表示圖的基本結構是鄰接矩陣和鄰接表。采用鄰接矩陣的方法來表示一個圖，可以輕易判定任意兩個頂點之間是否有邊相連。圖的矩陣表示的另一個好處就是使得我們可以使用矩陣分析的方法來研究圖的許多性質。

表示稀疏的無權圖的最常用方法是鄰接表，對每個頂點i建立一個單鏈表。

三元組：可以容易地表示一般的加權有向圖。Eg：1 2 3，表示頂點1到頂點2之間有一條權值為3的邊.
1 2 3
1 4 2 //點1到點4之間有權值為2的邊
2 4 3
在無向圖的三元組表示中，每條邊也會出現兩次。
在一些網絡分析軟件，比如Pajek中，鄰接表和三元組也是常用的格式，只是每條邊只出現一次，從而使表示更為緊湊。



簡單路徑：各個頂點都不互相同的路徑稱為是簡單的。
在技術網絡中，有時會有意設計一些圈，以期通過邊的冗余而實現網絡的魯棒性。

三、網絡的連通性：路徑、割集、連通性（強連通、弱聯通）
強弱連通：如果每對頂點之間都至少存在一條路徑，這個無向圖就是連通的，否則不連通。

一個不連通圖是由多個連通片組成的，連通片就是連通的幾個節點+邊。包含頂點數最多的連通片就成為最大連通片。

Menger定理：1、點形式：設頂點s和頂點t為圖G中兩個不相鄰的頂點，則使頂點s和頂點t分別屬于不同的連通片所需去除的頂點的最少數目等于連接頂點s和頂點t的獨立的簡單路徑的最大數目。
2、邊形式：設頂點s和頂點t為圖G中兩個不同的頂點，則使頂點s和頂點t分別屬于不同的連通片所需去除的邊的最少數目等于連接頂點s和頂點t的不相交的簡單路徑的最大數目。

兩個頂點稱為是不相鄰的，是指兩個頂點之間沒有邊直接相連。

連接頂點s和t的兩條簡單路徑稱為是獨立的，是指這兩條路徑的公共頂點只有頂點s和t。
連接s和t的兩條簡單路徑稱為是不相交的，是指這兩條路徑沒有經過一條相同的邊（但可以有共同頂點）。

使得一對頂點分屬于不同的連通片所需去除的一組頂點稱為這對頂點的點割集，使得一堆頂點分屬于不同的連通片所需去除的一組邊稱為這對頂點的邊割集。包含頂點數或邊數最少的割集稱為極小割集。

四、連通
對于有向圖中任意一對頂點u和v，都既存在一條從頂點u到頂點v的路徑，也存在一條從v到u的，稱為強連通。弱連通：把有向邊改為無向邊后，若圖是連通的，則稱為弱連通。

Prim：依次把頂點相連的最小的邊加入，直到全部頂點都加入。
Kruskal：把權值最小的依次加入。如果形成圈就不要這個邊，換下一條。
都是基于貪心算法。

五、二分圖與匹配問題：完全匹配、穩定匹配

匈牙利算法：https://blog.csdn.net/dark_scope/article/details/8880547/

穩定匹配：師生雙選案例（1）如果有學生想要換導師，那么沒有教師愿意接受這名學生。
（2）如果有教師想要換學生，那么沒有學生愿意跟隨這位教師。
那么就稱此師生分配方案是穩定的。

G-S算法定理
定理1： G-S算法在至多 N^2次迭代之后終止，且算法終止時所得到的集合是一個完全匹配。
定理2： G-S算法終止時所得到的集合Ω一定是一個穩定匹配。
定理3： G-S算法所有執行得到的都是對學生最滿意、對教師最不理想的穩定匹配。
定理4 一個左右節點數相同的二分圖存在完全匹配的充要條件是它不包含抑制集。
只要一個二分圖中存在抑制集，那就不存在完全匹配。

網絡基本拓撲性質

一、復雜網絡的連通性：有向網絡的蝴蝶結結構（入部、出部、核）

強連通核未必一定就是蝴蝶結結構中節點最多的部分。

二、節點的度、平均度
無向網絡中節點i的度ki定義為與節點直接相連的邊的數目。網絡中所有節點的度的平均值稱為網絡的平均度。網絡節點的度和網絡邊數M之間的關系：2M=N。
=2M/N

在有向網絡中，網絡的平均出度=平均入度。-----對于系統中每個個體而言不一定成立的性質，卻會在整個系統的層面上成立。

實際的大規模網絡的一個特征就是稀疏性。
=2M/N=(N-1)密度=N密度

三、網絡平均距離長度、直徑

兩個節點之間不存在路徑即距離無限大，從而導致整個網絡的平均路徑長度也無限大。
于是引入了GE-簡諧平均。

簡諧平均越大，說明效率越高，說明平均路徑長度越短。
網絡中任意兩個節點之間的距離的最大值稱為網絡的直徑，記為D。在實際應用中，網絡直徑通常是指任意兩個存在有限距離的節點之間的距離的最大值。

網絡中距離為d的連通的節點對的數量占整個網絡中連通的節點對的數量的比例，記為f（d）。

網絡中距離不超過d的連通的節點對的數量占整個網絡中連通的節點對數量的比例為g（d）。

四、聚類系數

一個網絡的聚類系數C定義為網絡中所有節點的聚類系數的平均值。

C的取值范圍為0-1. C=1的時候，網絡是全局耦合的，網絡中任意兩個節點都直接相連。

五、度分布

六、冪律分布
在一定的數學意義下，冪律分布是唯一一種具有無標度特性的長尾分布。

冪律分布的性質：https://blog.csdn.net/weixin_40614311/article/details/103450913

度相關性與社團結構

一、度相關性：聯合概率分布、同配性、異配性


為了進一步刻畫網絡的拓撲結構，需要考慮包含更多結構信息的高階拓撲特性。
因此：
聯合概率分布：




余平均度表示，網絡中隨機選取的一個節點，這個節點的度為k鄰居節點再被選取的概率。

在不改變節點度分布的情況下，可以使度大的節點傾向于和其它度大的節點連接。網絡中的這個重要的結構特性，稱之為節點之間的相關性(Correlation)。如果網絡中的節點趨于和它近似的節點相連，就稱該網絡是同配的(Assortative)；反之，就稱該網絡是異配的(Disassortative)。

網絡同配性(或異配性)的程度可用同配系數(也稱Pearson Coefficient----皮爾森系數)r來刻畫。r>0表示整個網絡呈現同配性結構，度大的節點傾向于和度大的節點相連；r<0表示整個網絡呈現異配性；r=0表示網絡結構不存在相關性。

二、社團結構與模塊度：模塊度、社團結構的檢測算法

基于模塊度的社團檢測算法：
CNM算法：基于貪婪思想。


CNM和FN的區別就是：CNM中構建的是detaQ的矩陣，FN中的就是鄰接矩陣。

模塊度的局限性，比如有的公認不具有較強社團結構的網絡也會有較大的q值，or公認具有明顯社團結構的網絡有很小的q值。Another：分辨率限制：模塊度無法識別出規模充分小的社團。

節點重要性與相似性

一、重要性指標：度中心性、介數中心性、接近中心性、k-核與k-殼、特征向量中心性

度中心性：

以經過某個節點的最短路徑的數目來刻畫節點重要性的指標就稱為介數中心性 Betweeness Centrality 簡稱介數BC。這個指數刻畫了節點i對于網絡中節點對之間沿著最短路徑傳輸信息的控制能力。

接近中心性：

K-殼分解法：

實際網絡可能出現：度大的節點既可能具有較大的ks值位于k-殼分解的核心內層，也可能具有較小的ks值而位于k-殼分解的外層。

特征向量中心性教學視頻：
https://www.bilibili.com/video/BV1Cr4y1S7qF/?spm_id_from=333.337.search-card.all.click&vd_source=2949e61edef0cf5bdf117691a67dd6c9

二、節點相似性
基于節點相似性進行鏈路預測的一個基本假設就是如果兩個節點之間的相似性越大，他們之間存在鏈接的可能性就越大。

隨機網絡模型

一、 規則網絡模型：網絡結構、網絡拓撲性質

要想構建和維護一個大規模的全耦合網絡的成本是極其高昂的。全耦合網絡作為實際網絡模型的局限性：大型實際網絡一般都是稀疏的，他們的邊的數目一般至多是o（N）而不是o（N平方）。

基本拓撲性質：

二、ER隨機圖：網絡構造算法、拓撲性質、網絡演變
隨機圖：






因此，ER隨機圖也稱為泊松隨機圖。

ER隨機圖的平均度是=p（N-1）=約等于pN

三、廣義隨機圖（配置模型）：構造算法、余平均度

實際網絡中節點的鄰居節點的平均度往往大于網絡節點的平均度。–你的朋友比你擁有更多的朋友。

網絡節點的平均度只是把網絡中每一個節點的度加起來再除以網絡節點數，而在計算網絡節點的鄰居節點的平均度時，度越大的節點的度往往被重復統計的次數也越高，正是這種對度大節點的偏好使得鄰居節點的平均度往往要大于節點的平均度。

小世界網絡模型

一、小世界網絡模型：WS小世界模型構造算法、NW小世界模型構造算法

在WS小世界模型中每個節點的度至少為K/2，而在ER隨機圖中對單個節點的度的最小值沒有任何限制。

二、拓撲性質分析：聚類系數、平均路徑長度和度分布


https://blog.csdn.net/weixin_42374938/article/details/120253526?ops_request_misc=&request_id=&biz_id=102&utm_term=WS小世界拓撲性質&utm_medium=distribute.pc_search_result.none-task-blog-2_allsobaiduweb~default-0-120253526.142^v62pc_search_tree,201^v3control_2,213^v1t3_control1&spm=1018.2226.3001.4449

三、二維Klernberg模型：構造算法

無標度網絡模型

一、BA無標度網絡：特性、構造算法、冪律度分析

ER隨機圖和WS小世界模型忽略了實際網絡的兩個重要特性—增長特性，即網絡的規模是不斷擴大的；優先連接，即新的節點更傾向于與那些具有較高連接度的hub節點連接。富者更富or馬太效應。而在ER隨機圖中，兩個節點之間是否有邊相連是完全隨機確定的，在WS小世界模型中，長程邊的端點也是完全隨機確定的。

二、Price模型：構造算法、度分布分析

三、模型推廣：適應度模型（構造算法）、局域世界演化模型（構造算法）


適應度模型具有以下特征：無標度特征、適者更富、贏者通吃。

網絡傳播

一、經典的傳染病模型：SI、SIR、SIS模型

在經典的傳染病模型中，種群population內的N個個體的狀態可分為如下幾類：
1-易染狀態S，Susceptible。一個個體在感染之前是處于易染狀態的，即該個體有可能被鄰居個體感染。
2-感染狀態I，Infected。一個感染上某種病毒的個體就稱為是處于感染狀態，該個體還會以一定概率感染其鄰居個體。
3-移除狀態R，Removed Refractory or Recovered。也稱為免疫狀態或恢復狀態。當一個個體經歷過一個完整的感染周期后，該個體就不再被感染，因此就可以不再考慮該個體。
經典個體的一個基本假設是完全混合：一個個體在單位時間里與網絡中任一其他個體接觸的機會都是均等的。

SI模型：
https://www.bilibili.com/video/BV1PA411M7Zz/?spm_id_from=333.337.search-card.all.click&vd_source=2949e61edef0cf5bdf117691a67dd6c9

https://blog.csdn.net/qq_37730871/article/details/126532308

在現實世界中，感染個體一般不可能永遠處于感染狀態并永遠傳染別人。
因此以下兩種更常見。

SIR模型：

SIS模型：

二、復雜網絡的免疫策略：隨機免疫、目標免疫、熟人免疫

標度網絡的免疫方法：
（1）隨機免疫：隨機選擇一些節點將其免疫，該方法的臨界值會隨著節點的增大而增大，成本較高
（2）目標節點免疫：選擇一些高度連通的節點將其免疫，該方法的臨界值遠遠小于隨機免疫，效果很好
（3）熟人免疫：隨機選擇一些節點，然后將他們度最大的鄰居免疫，該方法只需要用到局部信息，且效果比隨機免疫效果好。
總結：效率由高到低：目標節點免疫>熟人免疫>隨機免疫，熟人免疫相對于目標免疫而言只需要用到局部信息，不需要用到全局信息，隨機免疫實現簡單，但是效果很差。

網絡博弈

一、博弈模型：囚徒困境、雪堆博弈、鷹鴿博弈、膽小鬼博弈、獵鹿博弈（收益矩陣、納什均衡）

博弈模型：

囚徒困境博弈：

無論對手采取哪種策略，選擇背叛策略都是最佳的。因此理性的個體最終會處于相互背叛的狀態–（D，D）是囚徒困境博弈的納什均衡狀態。但是此時的受益低于兩人同時選擇合作時的受益。

重復囚徒困境：
如果兩個個體僅進行一輪囚徒困境博弈，個體會選擇背叛策略。然而在現實生活中，兩個個體之間經常進行重復的交互。此時個體會樂于幫助那些曾經幫助過自己的個體。

從各類重復困境中獲勝的都是所有程序中最簡單的規則—“針鋒相對”Tit-for-tat-TFT，也稱為“一報還一報or以牙還牙”。

TFT以合作開始，然后模仿對手上一步的策略。其之所以成功主要得益于：1-TFT是善良的，它不會首先背叛對手；2-TFT是可被激怒的，如果對手背叛自己，下一輪它也會做出報復性反應；3-TFT的報復是適當的，如果背叛它的對手知錯能改，重新與TFT合作，TFT會原諒對手。 Eg：棘魚受到大魚威脅時，會組成探查小隊試探，每游近幾厘米，棘魚會觀察其他棘魚是否照做，這個偵查過程就是分階段的重復囚徒困境博弈。

與TFT相比，“兩報還一報Tit-for-two-tat”只有對手連續兩次背叛后才采取報復策略—因為對對手太過寬容而得分低于TFT。“對手背叛后永久報復”的完全不寬容的規則是所有善良規則中得分最低的。

如果兩個TFT相互博弈，中間一次失誤會導致合作與背叛行為交錯發生。因此在噪聲環境中，TFT因為不能糾正對手的失誤而喪失合作優勢。So更有力的規則提出： GTFT慷慨的TFT：考慮個體面對背叛行為時，仍以一定的概率保持合作。GTFT期望收益比TFT收益高。WSLS贏存輸變Win-stay lost-shift：也叫巴甫洛夫規則。WSLS要求個體設一個心理閾值，如果一輪博弈的收入高于閾值，則下一輪將保持上一輪策略不變，反之改變。WSLS是一種確定性的糾錯規則，而GTFT是一種隨機糾錯規則。所以WSLS比TFT和GTFT對待噪聲干擾具有更好的魯棒性。

雪堆博弈：Snowdrift game SG。最佳策略取決于對手，如果對手選擇合作，個體的最佳策略是背叛，反之如果對手是背叛者，個體最好采取合作策略。因此不同于囚徒困境博弈，雪堆博弈中存在兩個純納什均衡：（C，D）（D，C）。在存在多納什均衡的情況下，個體如何抉擇是一個難題，可以根據一些線索比如歷史信息，進行選擇均衡。If沒有線索可利用，個體可以以概率1-r選擇鏟雪，以概率r選擇待在車中，r=c/（2b-c）稱為雙方合作時的損益比cost-to-benefit，此時對對手來說選擇合作或者背叛的期望收益是相同的

鷹鴿博弈-Hawk Dove game：

膽小鬼博弈-Chicken game：

獵鹿博弈Stag-hunting game SH：

X代表選擇合作策略的個體的比例

二、規則網絡上的演化博弈

演化博弈是刻畫群體決策形成和演化的一種基本范式，結合了傳統博弈論與生物進化論。以參與群體為研究對象，通過分析群體策略在選擇和突變作用下的演化過程，從而解釋和預測個體在交互決策情境中的博弈行為。（從系統動態的角度考察個體決策到群體決策的形成機制）

規則網絡上的雪崩博弈：

總結

以上是生活随笔為你收集整理的【网络科学导论】【复杂网络】基础知识总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。