《高級(jí)算法設(shè)計(jì)》課件 第1、2章 線性規(guī)劃;高級(jí)圖算法

高級(jí)算法設(shè)計(jì)與分析線性規(guī)劃基本概念基本概念基本概念線性規(guī)劃的形式：線性規(guī)劃：定義標(biāo)準(zhǔn)型和松弛型標(biāo)準(zhǔn)型和松弛型非標(biāo)準(zhǔn)型目標(biāo)函數(shù)不是最大化，而是最小化約束條件是大于等于約束約束條件是等式約束;存在一些變量沒有非負(fù)約束標(biāo)準(zhǔn)型和松弛型非標(biāo)準(zhǔn)型例子標(biāo)準(zhǔn)型和松弛型標(biāo)準(zhǔn)型和松弛型標(biāo)準(zhǔn)型和松弛型標(biāo)準(zhǔn)型：標(biāo)準(zhǔn)型和松弛型松弛型：在松弛型中，等式左邊的變量x4,x5,x6被稱為基本變量，等式右邊的變量x1,x2,x3被稱為非基本變量矩陣形式：標(biāo)準(zhǔn)型和松弛型圖解法將可行域?yàn)椋篈BCDEF的邊界和內(nèi)部，A,

B,

C,

D,

E,

F稱為極點(diǎn)圖解法單純形法如果我們能夠?qū)⑸鲜瞿繕?biāo)函數(shù)的所有變量的系數(shù)全部轉(zhuǎn)換為負(fù)數(shù)單純形法步驟松弛基本解為(x1,x2,x3,x4,x5,x6)=(0,0,13,10,5,2)單純形法步驟基本解為(x1,x2,x3,x4,x5,x6)=(0,0,13,10,5,2)在此基本解下，目標(biāo)函數(shù)的值為0通過增大x1或x2來使目標(biāo)函數(shù)變大單純形法步驟目標(biāo)函數(shù)中x1的系數(shù)大于x2，選擇增大x1約束條件4的約束最緊湊單純形法步驟約束條件4變?yōu)橛眠@個(gè)表達(dá)式替換目標(biāo)函數(shù)和其他約束條件中的x1

單純形法步驟目標(biāo)函數(shù)的值為16單純形法步驟用這個(gè)表達(dá)式替換目標(biāo)函數(shù)和其他約束條件中的x2

單純形法步驟單純形表注意表格中的值是變量系數(shù)的值（取負(fù)），目標(biāo)函數(shù)變量的系數(shù)同樣取負(fù)單純形表1.從目標(biāo)函數(shù)中選擇一個(gè)需要變大的變量（系數(shù)最?。﹛12.找出最緊湊約束最緊湊約束是b/(x1系數(shù))最小的約束（第4行約束）3.x1變量替入為基變量，而原來的基變量x6替出為非基變量單純形表1.從目標(biāo)函數(shù)中選擇一個(gè)需要變大的變量（系數(shù)最?。﹛12.找出最緊湊約束最緊湊約束是b/(x1系數(shù))最小的約束（第4行約束）3.x1變量替入為基變量，而原來的基變量x6替出為非基變量單純形表4.用x1的表達(dá)式替換目標(biāo)函數(shù)和其他約束條件中的x1

高斯消元單純形表4.用x1的表達(dá)式替換目標(biāo)函數(shù)和其他約束條件中的x1

高斯消元重復(fù)上述步驟單純形表重復(fù)上述步驟最緊湊約束為第一行約束，對(duì)第一行進(jìn)行替入和替出操作單純形表重復(fù)上述步驟用第一行約束對(duì)所有其他約束行和目標(biāo)函數(shù)行進(jìn)行x2高斯消元對(duì)偶對(duì)偶性是線性規(guī)劃最重要的內(nèi)容之一每個(gè)線性規(guī)劃（LP1）必然有與之相伴而生的另一個(gè)線性規(guī)劃問題（LP2），即任何一個(gè)求maxz的LP1都有一個(gè)求minw的LP2對(duì)偶對(duì)偶矩陣形式對(duì)偶例子對(duì)偶對(duì)偶規(guī)則（標(biāo)準(zhǔn)型）原問題的目標(biāo)函數(shù)是最大化，對(duì)偶問題的目標(biāo)函數(shù)是最小化，原問題的約束條件是小于等于，對(duì)偶問題的約束條件是大于等于原問題約束條件的個(gè)數(shù)(m)決定對(duì)偶問題變量的個(gè)數(shù)，且第一個(gè)約束條件對(duì)應(yīng)第一個(gè)變量，第二個(gè)約束條件對(duì)應(yīng)第二個(gè)變量，以此類推對(duì)偶對(duì)偶規(guī)則（標(biāo)準(zhǔn)型）原問題變量的個(gè)數(shù)(n)決定對(duì)偶問題約束條件的個(gè)數(shù)，且第一個(gè)變量對(duì)應(yīng)第一個(gè)約束條件，第二個(gè)變量對(duì)應(yīng)第二個(gè)約束條件，以此類推對(duì)偶問題的目標(biāo)函數(shù)中每個(gè)變量的系數(shù)由其對(duì)應(yīng)原問題中約束條件b值決定對(duì)偶問題約束條件的c值是其對(duì)應(yīng)變量(原問題)在目標(biāo)函數(shù)的系數(shù)，約束條件中各變量的系數(shù)是其對(duì)應(yīng)變量(原問題)在約束條件中的系數(shù)對(duì)偶對(duì)偶：例子對(duì)偶：例子對(duì)偶是怎么來的設(shè)線性規(guī)劃的原始問題：轉(zhuǎn)化為優(yōu)化問題的標(biāo)準(zhǔn)形式對(duì)偶是怎么來的對(duì)偶是怎么來的對(duì)偶是怎么來的對(duì)偶問題可以化為對(duì)偶是怎么來的如果對(duì)原問題按照“原問題和對(duì)偶問題的轉(zhuǎn)換”表可得：等價(jià)對(duì)偶例子：矩陣博弈矩陣博弈：猜硬幣，兩個(gè)參與者分別同時(shí)從兩個(gè)硬幣(一元和兩元)中選取一個(gè)讓對(duì)方猜，如果都猜錯(cuò)或都猜對(duì)，繼續(xù)玩，如果只有一方猜對(duì)，則猜對(duì)一方贏得此次雙方的所有硬幣對(duì)偶例子：矩陣博弈矩陣博弈：猜硬幣，收益矩陣如下：行和列表示（player1和player2）的策略（選取的硬幣和猜對(duì)方的硬幣），如（1，2）表示選取硬幣1元，猜對(duì)方選取的是2元；矩陣的值表示列player2的收益

對(duì)偶例子：矩陣博弈對(duì)偶例子：矩陣博弈對(duì)偶例子：矩陣博弈對(duì)偶例子：矩陣博弈對(duì)偶例子：矩陣博弈對(duì)偶例子：矩陣博弈即player2

LP問題C的對(duì)偶問題即為player1的LP問題R對(duì)偶性質(zhì)線性規(guī)劃標(biāo)準(zhǔn)式對(duì)偶性質(zhì)可得：即：對(duì)偶性質(zhì)：弱對(duì)偶性對(duì)偶性質(zhì)：強(qiáng)對(duì)偶性和互補(bǔ)松馳性對(duì)偶性質(zhì)：互補(bǔ)松馳性如果原問題和對(duì)偶問題得出的解滿足互補(bǔ)松弛性，則為最優(yōu)解互補(bǔ)松馳性例子互補(bǔ)松馳性例子原問題的對(duì)偶問題為互補(bǔ)松馳性例子互補(bǔ)松馳性例子原問題的對(duì)偶問題為互補(bǔ)松弛性可得互補(bǔ)松馳性例子整數(shù)規(guī)劃當(dāng)變量的取值從實(shí)數(shù)變?yōu)檎麛?shù)后，這個(gè)問題到底是變難了，還是變?nèi)菀琢?整數(shù)規(guī)劃松弛整數(shù)規(guī)劃：分支限界分支限界：例子對(duì)線性規(guī)劃問題求解，得最優(yōu)解為x1=2.5,x2=2.25，目標(biāo)函數(shù)為21.5分支限界：例子此時(shí)，可以對(duì)x1進(jìn)行分支，也可對(duì)x2進(jìn)行分支。對(duì)x1進(jìn)行分支，則分為x1≤2和x1≥3兩部分。

分支限界：例子對(duì)左邊分支(x1≤2)求解得x1=2,x2=2.5，目標(biāo)函數(shù)為20對(duì)右邊分支(x1≥3)求解得x1=3,x2=1.5，目標(biāo)函數(shù)為21分支限界：例子接著搜索節(jié)點(diǎn)3，對(duì)x2進(jìn)行分支，則分為x2≤1和x2≥2兩部分分支限界：例子對(duì)左邊分支(x2≤1)求解得x1=3.3,x2=1，目標(biāo)函數(shù)為20.7而右邊分支(x2≥2)無可行解。分支限界：例子接著搜索節(jié)點(diǎn)4，對(duì)x1進(jìn)行分支，則分為x1≤3和x1≥4兩部分分支限界：例子對(duì)左邊分支(x1≤3)求解得x1=3,x2=1，目標(biāo)函數(shù)為19，找到整數(shù)解，結(jié)束搜索而右邊分支(x1≥4)無可行解分支限界：例子因?yàn)楣?jié)點(diǎn)2的上限大于目前找到的最優(yōu)值19，需要繼續(xù)搜索，對(duì)x2進(jìn)行分支，則分為x2≤2和x2≥3兩部分分支限界：例子對(duì)左邊分支(x2≤2)求解得x1=2,x2=2，目標(biāo)函數(shù)為18而右邊分支(x2≥3)無可行解最終的最優(yōu)解為x1=3,x2=1，最優(yōu)值為190-1整數(shù)規(guī)劃整數(shù)規(guī)劃的一個(gè)特列是0-1整數(shù)規(guī)劃，也就是參數(shù)的取值只能是0或1。很多算法問題都可以建模成0-1整數(shù)規(guī)劃問題，如0-1背包問題、任務(wù)分配、集合覆蓋等問題。0-1整數(shù)規(guī)劃：建模0-1背包問題中，設(shè)背包的承重為C，共n個(gè)物品，每個(gè)物品的重量和價(jià)值分別為wi和vi，則問題建模為0-1整數(shù)規(guī)劃：建模在應(yīng)用中，有時(shí)會(huì)遇到變量可以取多個(gè)整數(shù)值的問題。如果用0-1變量來表示，也可以用一組0-1變量來取代。

如x取0－9之間的任意整數(shù)時(shí)。

x=20x0+

21x1+

22x2+

23x3￡90-1整數(shù)規(guī)劃：建模含有相互排斥的約束條件的問題（1）兩個(gè)約束中，只有一個(gè)起作用。例：a11x1+a12x2<B1a21x1+a22x2<B2

解：引入0-1變量Y1,Y2和足夠大的正數(shù)M，則a11x1+a12x2<B1+M1Y1a21x1+a22x2<B2+M2Y2Y1+Y2=10-1整數(shù)規(guī)劃：建模某企業(yè)生產(chǎn)產(chǎn)品的費(fèi)用如下，建立0-1規(guī)劃模型單耗量產(chǎn)品資源IIIIII資源量A248500B234300C123100單件可變費(fèi)用456固定費(fèi)用100150200單件售價(jià)810120-1整數(shù)規(guī)劃：建模解：設(shè)Xj是第j種產(chǎn)品的產(chǎn)量。Yj是0－1變量，表示是（Yj=1）否（Yj=0）生產(chǎn)第j種產(chǎn)品。maxZ=4X1+5X2+6X3–100Y1

–150Y2

–200Y32X1+4X2+8X3￡5002X1+3X2+4X3￡300X1+2X2+3X3￡100X1￡

M1Y1X2￡

M2Y2X3

￡

M3

Y3X1,

X2,

X330整數(shù)Y1,Y2,Y3為0－1變量。

s.t.0-1整數(shù)規(guī)劃：隱枚舉法0-1整數(shù)規(guī)劃：隱枚舉法0-1整數(shù)規(guī)劃：隱枚舉法0-1整數(shù)規(guī)劃：隱枚舉法原始-對(duì)偶算法通過對(duì)偶問題來求解原問題的最優(yōu)解或者近似解，統(tǒng)稱為原始-對(duì)偶算法對(duì)于0-1整數(shù)規(guī)劃問題，是很難通過互補(bǔ)松弛性來求得最優(yōu)解，但我們依然可以通過原問題(Primal)和對(duì)偶問題(Dual)的弱對(duì)偶性來求得一個(gè)近似解原始-對(duì)偶算法原始-對(duì)偶算法原始-對(duì)偶算法原始-對(duì)偶算法的應(yīng)用：頂點(diǎn)覆蓋頂點(diǎn)覆蓋問題是指從圖中選取最少的頂點(diǎn)，這些頂點(diǎn)能夠覆蓋圖中所有的邊(一個(gè)頂點(diǎn)覆蓋一條邊，指這個(gè)頂點(diǎn)和這條邊相連)。數(shù)學(xué)模型。設(shè)G=(V,E)，節(jié)點(diǎn)個(gè)數(shù)為n，邊的條數(shù)為m，令xv

為0-1變量，0代表不選取頂點(diǎn)v，1代表選取頂點(diǎn)v，則頂點(diǎn)覆蓋的0-1整數(shù)規(guī)劃模型:原始-對(duì)偶算法的應(yīng)用：頂點(diǎn)覆蓋頂點(diǎn)覆蓋問題是指從圖中選取最少的頂點(diǎn)，這些頂點(diǎn)能夠覆蓋圖中所有的邊(一個(gè)頂點(diǎn)覆蓋一條邊，指這個(gè)頂點(diǎn)和這條邊相連)。對(duì)偶：圖的最大匹配問題原始-對(duì)偶算法的應(yīng)用：頂點(diǎn)覆蓋擴(kuò)展頂點(diǎn)覆蓋問題：給每個(gè)頂點(diǎn)都賦予一個(gè)權(quán)重wv(wv>0)，頂點(diǎn)覆蓋問題轉(zhuǎn)化為求頂點(diǎn)集合，使其能夠覆蓋所有的邊且頂點(diǎn)集的總權(quán)重最小。線性模型對(duì)偶模型原始-對(duì)偶算法的應(yīng)用：頂點(diǎn)覆蓋原始-對(duì)偶算法來求解帶權(quán)重頂點(diǎn)覆蓋問題的近似最優(yōu)解。原始-對(duì)偶算法的應(yīng)用：頂點(diǎn)覆蓋原始-對(duì)偶算法來求解帶權(quán)重頂點(diǎn)覆蓋問題的近似最優(yōu)解。原始-對(duì)偶算法的應(yīng)用：頂點(diǎn)覆蓋原始-對(duì)偶算法的應(yīng)用：頂點(diǎn)覆蓋高級(jí)算法設(shè)計(jì)與分析高級(jí)圖算法主要內(nèi)容最大流最小割圖的中心性算法社群發(fā)現(xiàn)算法流網(wǎng)絡(luò)找到一個(gè)從s出發(fā)，到t的流量最大的流，這就是最大流問題網(wǎng)絡(luò)的流網(wǎng)絡(luò)的流需要滿足的兩個(gè)條件：網(wǎng)絡(luò)的流如何找到最大流從流量為0開始，逐步增加流量，直到達(dá)到最大流量為止從s出發(fā)，找到一條到t的可行路徑，并將流增加到這個(gè)路徑能夠支持的最大流量在剩余的流網(wǎng)絡(luò)（殘存網(wǎng)絡(luò)）中再找一條可行的路徑，增加相應(yīng)的流重復(fù)以上步驟網(wǎng)絡(luò)的流原始流網(wǎng)絡(luò)找到一條路徑殘存網(wǎng)絡(luò)？殘存網(wǎng)絡(luò)網(wǎng)絡(luò)的流殘存網(wǎng)絡(luò)新的路徑：新的流網(wǎng)絡(luò)網(wǎng)絡(luò)的流殘存網(wǎng)絡(luò)此時(shí)已無法在此殘存網(wǎng)絡(luò)中再找到一條從s到t的路徑，前面的流為最大流Ford-Fulkerson算法Ford-Fulkerson算法Ford-Fulkerson算法的兩個(gè)問題當(dāng)在殘存網(wǎng)絡(luò)中無法再找出一條從s到t的路徑時(shí)，那么得到的流一定是最大流嗎？最大流最小割定理在殘存網(wǎng)絡(luò)中如何找到一條從s到t的路徑？Edmonds-Karp算法最大流最小割定理最大流最小割定理最大流最小割定理最大流最小割定理最大流最小割定理設(shè)f是最大流，其所對(duì)應(yīng)的殘存網(wǎng)絡(luò)Gf還存在一條從s到t的路徑p，

在殘存網(wǎng)絡(luò)Gf

上可以找到一個(gè)流f′

最大流最小割定理最大流最小割定理結(jié)論1:也就是由最大流最小割陳述2得出的(S,T)割上，(S,T)的流量(從S到T的流量)等于(S,T)的容量最大流最小割定理(S′,T′)是任意s-t割,根據(jù)能量守恒來證明，即從源節(jié)點(diǎn)s來的流f等于從集合S流到T的流

結(jié)論2:是s?t流f等于任意(S′,T′)割最大流最小割定理(S′,T′)是任意s-t割結(jié)論3:

f小于等于任意(S′,T′)割的容量最大流最小割定理由結(jié)論1和結(jié)論2，可知s?t流f等于(S,T)割的容量，即f=C(S,T)結(jié)合結(jié)論3

，可知(S,T)割的容量小于等于任意割，即C(S,T)≤C(S′,T′)，即C(S,T)是最小割

最大流最小割定理Edmonds-Karp算法在殘存網(wǎng)絡(luò)中如何找到一條從s到t的路徑?圖的深度優(yōu)先遍歷方法？Edmonds-Karp算法最短路徑算法Dijsktra算法(復(fù)雜度O(mlogn))廣度優(yōu)先搜索（O(m)）短路徑為vs→v2→vt

或者vs→v3→vt，所以通過兩次增廣路徑即可找到網(wǎng)絡(luò)的最大流Edmonds-Karp算法：復(fù)雜度基于最短路徑算法證明：設(shè)在殘存網(wǎng)絡(luò)G中找到流f，形成新的殘存網(wǎng)絡(luò)G’。從G到G’，增加了指向上一層級(jí)的邊，并刪除了指向下一層級(jí)的關(guān)鍵邊增加的邊并不會(huì)減少從s到其他節(jié)點(diǎn)的距離，但減少的邊有可能會(huì)增加s到其他節(jié)點(diǎn)的距離，所以引理得證Edmonds-Karp算法：復(fù)雜度基于最短路徑算法Edmonds-Karp算法：復(fù)雜度邊ei→j再次成為關(guān)鍵邊時(shí)，源節(jié)點(diǎn)到vi的距離至少增加了2跳Edmonds-Karp算法：復(fù)雜度可以得出邊ei→j最多(n?2)/2次成為關(guān)鍵邊總的關(guān)鍵邊的次數(shù)為O(m?(n?2)/2)=O(mn)Edmonds-Karp算法最大容量路徑也為vs→v2→vt

或者vs→v3→vt，所以也通過兩次增廣路徑即可找到網(wǎng)絡(luò)的最大流最大容量路徑算法Dijsktra算法

Edmonds-Karp算法

Dijkstra算法，對(duì)路徑的邊求最小容量，并最大化之，Edmonds-Karp算法Edmonds-Karp算法流量分解證明Edmonds-Karp算法流量分解證明由流量守恒，可得：在每次容量更新中，路徑中最小容量的邊(至少一條)的容量會(huì)被置0，因圖G邊的條數(shù)是mEdmonds-Karp算法流量分解定理說明了最大流fopt

可以被分解為最多m個(gè)路徑流{f1,f2,···,fm}，在這些路徑流中，必然存在一個(gè)流fk≥fopt/m,1≤k≤m，而此流所在路徑上所有邊的容量必然≥fopt/m。引理得證。Edmonds-Karp算法Edmonds-Karp算法如果原始圖G的邊數(shù)為m，則在任意的殘存圖Gt中，其邊的條數(shù)不會(huì)超過2m，所以對(duì)任意殘存圖Gt，剩余最大流為

因?yàn)槿萘慷紴檎椭饕獌?nèi)容最大流最小割圖的中心性算法社群發(fā)現(xiàn)算法圖的中心性算法度中心性(DegreeCentrality):一個(gè)點(diǎn)與其他點(diǎn)直接連接的程度緊密中心性(ClosenessCentrality):一個(gè)節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的距離，一個(gè)擁有高緊密性中心性的節(jié)點(diǎn)擁有著到所有其他節(jié)點(diǎn)的距離較小;中介中心性(BetweennessCentrality):一個(gè)節(jié)點(diǎn)位于最短路徑上的次數(shù)，如果有很多條最短路徑經(jīng)過此節(jié)點(diǎn)，說明此節(jié)點(diǎn)的中介中心性越高;特征向量中心性(EigenvectorCentrality):一個(gè)節(jié)點(diǎn)的重要性有時(shí)也取決于其鄰居節(jié)點(diǎn)的重要性，與之相連的鄰居節(jié)點(diǎn)越重要，則該節(jié)點(diǎn)特征向量中心性就越高;PageRank:PageRank也是考慮鄰節(jié)點(diǎn)重要性的一種中心性算法，可看出是特征向量中心性的一種變體。度中心性度中心性是來衡量一個(gè)節(jié)點(diǎn)重要性相對(duì)簡(jiǎn)單的算法，其基于一個(gè)非常直接的觀察，和越多其他節(jié)點(diǎn)連接的節(jié)點(diǎn)越重要緊密中心性緊密中心性用來衡量一個(gè)節(jié)點(diǎn)處于圖的中心的程度，當(dāng)一個(gè)節(jié)點(diǎn)越處于中心的位置，則其在圖上散播信息的能力越強(qiáng)。為了適應(yīng)圖不是強(qiáng)連通圖的情況，采用調(diào)和平均數(shù)緊密中心性前面的表述形式難以處理這種對(duì)幾個(gè)子圖進(jìn)行連接的情形緊密中心性Dangalchev變體中介中心性在社交網(wǎng)絡(luò)中，有時(shí)候并不是那些具有最多關(guān)注者的節(jié)點(diǎn)(度中心性)或者處于網(wǎng)絡(luò)中心位置的節(jié)點(diǎn)(緊密中心性)是最重要的，而是那些起著關(guān)鍵橋梁或者中介作用的節(jié)點(diǎn)起著決定性的作用其中，σjk

是節(jié)點(diǎn)vj到節(jié)點(diǎn)vk

的最短路徑的個(gè)數(shù)，σijk是節(jié)點(diǎn)vj到節(jié)點(diǎn)vk

且經(jīng)過節(jié)點(diǎn)vi

的最短路徑的個(gè)數(shù)中介中心性假設(shè)從節(jié)點(diǎn)vj

到vk

的最短路徑在就要到達(dá)vk

前，可沿著不同的路徑分別經(jīng)由三個(gè)節(jié)點(diǎn)u1、u2、u3，也就是u1、u2、u3

是vk

在最短路徑上的前一鄰節(jié)點(diǎn)中介中心性中介中心性算法如何降低復(fù)雜度？快速中介中心性算法累積節(jié)點(diǎn)對(duì)依賴簡(jiǎn)單場(chǎng)景節(jié)點(diǎn)vs

到任意其他節(jié)點(diǎn)只存在一條最短路徑，即σst=1,?vt∈V

快速中介中心性算法累積節(jié)點(diǎn)對(duì)依賴：簡(jiǎn)單場(chǎng)景快速中介中心性算法快速中介中心性算法快速中介中心性算法快速中介中心性算法快速中介中心性算法累積節(jié)點(diǎn)對(duì)依賴：簡(jiǎn)單場(chǎng)景從前面的例子可以看出，累積節(jié)點(diǎn)對(duì)依賴(δ值)是個(gè)遞歸式，所以其計(jì)算類似于動(dòng)態(tài)規(guī)劃，也就是從最底層的值，這里是樹中葉子節(jié)點(diǎn)的δ值(其值為0)開始計(jì)算，依次沿著樹枝向跟節(jié)點(diǎn)計(jì)算快速中介中心性算法累積節(jié)點(diǎn)對(duì)依賴：一般場(chǎng)景在簡(jiǎn)單場(chǎng)景中，如果最短路徑經(jīng)過某個(gè)節(jié)點(diǎn)vj，則必然經(jīng)過其父節(jié)點(diǎn)。但是在一般場(chǎng)景中，并不存在這樣的關(guān)系，也就是最短路徑經(jīng)過節(jié)點(diǎn)vj，但并不一定經(jīng)過其前一跳鄰節(jié)點(diǎn)從vs

到vk

的最短路徑數(shù)目共有σsk

個(gè)，從vs

到v1

的最短路徑數(shù)目共有σs1

個(gè)。所以我們只需考慮σsk/σs1

比例的最短路徑快速中介中心性算法累積節(jié)點(diǎn)對(duì)依賴：一般場(chǎng)景特征向量中心性在度中心性中，節(jié)點(diǎn)的重要程度只考慮了連接數(shù)，而沒有考慮到連接節(jié)點(diǎn)的重要程度。在社交網(wǎng)絡(luò)上，和一個(gè)有影響力的節(jié)點(diǎn)有連接關(guān)系，顯然比和一個(gè)普通節(jié)點(diǎn)有連接關(guān)系，更能使提高自身的重要程度。特征向量中心性特征向量中心性圖的鄰接矩陣特征向量中心性第一次迭代特征向量中心性第二次迭代特征向量中心性第三次迭代特征向量中心性第四次迭代收斂時(shí)特征向量中心性從以上式子可知，特征向量中心性x是圖的鄰接矩陣A的特征值為λ時(shí)的特征向量，這就是為什么稱之為特征向量中心性的原因特征向量中心性特征向量中心性發(fā)現(xiàn)節(jié)點(diǎn)3和節(jié)點(diǎn)5

的特征向量中心性是一致的，這個(gè)從圖12.7很容易得到驗(yàn)證，這兩個(gè)節(jié)點(diǎn)的鄰節(jié)點(diǎn)是相似的，它們都連接了4節(jié)點(diǎn)，同時(shí)連接對(duì)方。此外，節(jié)點(diǎn)4具有最大的特征向量中心性，這個(gè)從圖中也容易得出，節(jié)點(diǎn)4具有最多的鄰節(jié)點(diǎn)，且其鄰居具有較大的特征向量中心性值。PageRankPageRank是谷歌的網(wǎng)頁排序算法，可以認(rèn)為其特性向量中心性算法的一個(gè)變體：節(jié)點(diǎn)的重要性不僅僅取決于有多少個(gè)其他節(jié)點(diǎn)指向自己，同時(shí)也取決于那些指向自己的節(jié)點(diǎn)的重要性PageRankPageRankPageRankPageRankPageRank另得主要內(nèi)容最大流最小割圖的中心性算法社群發(fā)現(xiàn)算法社群發(fā)現(xiàn)社群發(fā)現(xiàn)基于模塊度的算法基于標(biāo)簽傳播的算法基于團(tuán)的算法社群發(fā)現(xiàn):基于模塊度的算法模塊度其中m是圖邊的條數(shù);A為鄰接矩陣，也就是說如vi和vj間存在邊，Aij=1，否則，Aij=0;ki表示vi的度;Si表示vi所屬的社群，Sj表示vj所屬的社群，當(dāng)Si=Sj時(shí)，δ(Si,Sj)=1，當(dāng)Si?