考研復(fù)雜網(wǎng)絡(luò)基礎(chǔ)知識(shí)點(diǎn)

復(fù)雜網(wǎng)絡(luò)的基本概念復(fù)雜網(wǎng)絡(luò)是對(duì)復(fù)雜系統(tǒng)的一種抽象描述，用節(jié)點(diǎn)和邊來(lái)表示系統(tǒng)中的個(gè)體及其相互關(guān)系。節(jié)點(diǎn)代表系統(tǒng)中的個(gè)體元素，比如在社交網(wǎng)絡(luò)中，節(jié)點(diǎn)可以是人；在電力網(wǎng)絡(luò)中，節(jié)點(diǎn)可以是發(fā)電站或變電站。邊則表示節(jié)點(diǎn)之間的某種聯(lián)系，例如社交網(wǎng)絡(luò)中的好友關(guān)系，電力網(wǎng)絡(luò)中的輸電線路。網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是指節(jié)點(diǎn)和邊的連接方式。常見(jiàn)的拓?fù)浣Y(jié)構(gòu)有規(guī)則網(wǎng)絡(luò)、隨機(jī)網(wǎng)絡(luò)和小世界網(wǎng)絡(luò)、無(wú)標(biāo)度網(wǎng)絡(luò)等。規(guī)則網(wǎng)絡(luò)中節(jié)點(diǎn)的連接具有高度的規(guī)律性，如晶格網(wǎng)絡(luò)；隨機(jī)網(wǎng)絡(luò)是節(jié)點(diǎn)之間隨機(jī)連接形成的；小世界網(wǎng)絡(luò)具有較短的平均路徑長(zhǎng)度和較高的聚類系數(shù)；無(wú)標(biāo)度網(wǎng)絡(luò)則具有冪律度分布特性，即少數(shù)節(jié)點(diǎn)擁有大量連接，而多數(shù)節(jié)點(diǎn)連接較少。度與度分布度是描述節(jié)點(diǎn)在網(wǎng)絡(luò)中連接情況的基本屬性，指與該節(jié)點(diǎn)相連的邊的數(shù)量。對(duì)于有向網(wǎng)絡(luò)，度又分為入度和出度，入度表示指向該節(jié)點(diǎn)的邊的數(shù)量，出度表示從該節(jié)點(diǎn)出發(fā)的邊的數(shù)量。度分布描述了網(wǎng)絡(luò)中節(jié)點(diǎn)度的概率分布情況。在隨機(jī)網(wǎng)絡(luò)中，度分布通常服從泊松分布；而在無(wú)標(biāo)度網(wǎng)絡(luò)中，度分布滿足冪律分布，即\(P(k)\simk^{-\gamma}\)，其中\(zhòng)(P(k)\)是節(jié)點(diǎn)度為\(k\)的概率，\(\gamma\)是冪律指數(shù)，一般在2到3之間。冪律分布意味著網(wǎng)絡(luò)中存在少數(shù)度值很大的節(jié)點(diǎn)（稱為樞紐節(jié)點(diǎn)），它們對(duì)網(wǎng)絡(luò)的結(jié)構(gòu)和功能起著關(guān)鍵作用。路徑長(zhǎng)度與聚類系數(shù)路徑長(zhǎng)度是指網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間最短路徑所包含的邊的數(shù)量。平均路徑長(zhǎng)度是網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間路徑長(zhǎng)度的平均值，它反映了網(wǎng)絡(luò)中信息傳播的效率。小世界網(wǎng)絡(luò)和無(wú)標(biāo)度網(wǎng)絡(luò)通常具有較短的平均路徑長(zhǎng)度，這意味著信息能夠在網(wǎng)絡(luò)中快速傳播。聚類系數(shù)衡量節(jié)點(diǎn)的鄰居節(jié)點(diǎn)之間相互連接的程度。對(duì)于一個(gè)節(jié)點(diǎn)\(i\)，其聚類系數(shù)\(C_i\)定義為其鄰居節(jié)點(diǎn)之間實(shí)際存在的邊數(shù)與所有可能邊數(shù)的比值。網(wǎng)絡(luò)的平均聚類系數(shù)是所有節(jié)點(diǎn)聚類系數(shù)的平均值。高聚類系數(shù)表明網(wǎng)絡(luò)中存在緊密連接的子結(jié)構(gòu)，如社交網(wǎng)絡(luò)中的朋友圈子。網(wǎng)絡(luò)的連通性網(wǎng)絡(luò)的連通性描述了網(wǎng)絡(luò)中節(jié)點(diǎn)之間的可達(dá)性。如果網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間都存在路徑相連，則稱該網(wǎng)絡(luò)是連通的；否則，網(wǎng)絡(luò)是不連通的，由多個(gè)連通分支組成。連通度是衡量網(wǎng)絡(luò)連通性的一個(gè)重要指標(biāo)，分為點(diǎn)連通度和邊連通度。點(diǎn)連通度是指為了使網(wǎng)絡(luò)不連通而需要?jiǎng)h除的最少節(jié)點(diǎn)數(shù)；邊連通度是指為了使網(wǎng)絡(luò)不連通而需要?jiǎng)h除的最少邊數(shù)。網(wǎng)絡(luò)的連通性對(duì)于其功能的實(shí)現(xiàn)至關(guān)重要，例如在通信網(wǎng)絡(luò)中，連通性保證了信息的正常傳輸。網(wǎng)絡(luò)的中心性中心性用于衡量節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要程度。常見(jiàn)的中心性指標(biāo)有度中心性、介數(shù)中心性和接近中心性。度中心性直接基于節(jié)點(diǎn)的度，度越大的節(jié)點(diǎn)，度中心性越高，表明該節(jié)點(diǎn)在局部連接方面越重要。介數(shù)中心性考慮節(jié)點(diǎn)在網(wǎng)絡(luò)中所有最短路徑上的作用。一個(gè)節(jié)點(diǎn)的介數(shù)中心性越高，說(shuō)明它在信息傳播和資源流動(dòng)中起到的橋梁作用越大。接近中心性衡量節(jié)點(diǎn)與網(wǎng)絡(luò)中其他所有節(jié)點(diǎn)的接近程度，接近中心性高的節(jié)點(diǎn)能夠快速地與其他節(jié)點(diǎn)進(jìn)行信息交互。網(wǎng)絡(luò)的演化模型隨機(jī)圖模型是最早提出的網(wǎng)絡(luò)演化模型，由埃爾德什（Erd?s）和雷尼（Rényi）提出。在該模型中，給定\(N\)個(gè)節(jié)點(diǎn)，以固定概率\(p\)隨機(jī)連接節(jié)點(diǎn)形成邊。隨機(jī)圖模型可以生成具有泊松度分布的隨機(jī)網(wǎng)絡(luò)。小世界網(wǎng)絡(luò)模型由瓦特（Watts）和斯托加茨（Strogatz）提出，該模型在規(guī)則網(wǎng)絡(luò)的基礎(chǔ)上，通過(guò)以一定概率隨機(jī)重連邊，引入了少量的長(zhǎng)程連接，從而使網(wǎng)絡(luò)同時(shí)具備高聚類系數(shù)和短平均路徑長(zhǎng)度的小世界特性。無(wú)標(biāo)度網(wǎng)絡(luò)模型由巴拉巴西（Barabási）和阿爾伯特（Albert）提出，簡(jiǎn)稱BA模型