《高級算法設計》課件 第2章 高級圖算法

高級算法設計與分析高級圖算法林海lin.hai@B站：foretmer主要內(nèi)容最大流最小割圖的中心性算法社群發(fā)現(xiàn)算法流網(wǎng)絡找到一個從s出發(fā)，到t的流量最大的流，這就是最大流問題網(wǎng)絡的流網(wǎng)絡的流需要滿足的兩個條件：網(wǎng)絡的流如何找到最大流從流量為0開始，逐步增加流量，直到達到最大流量為止從s出發(fā)，找到一條到t的可行路徑，并將流增加到這個路徑能夠支持的最大流量在剩余的流網(wǎng)絡（殘存網(wǎng)絡）中再找一條可行的路徑，增加相應的流重復以上步驟網(wǎng)絡的流原始流網(wǎng)絡找到一條路徑殘存網(wǎng)絡？殘存網(wǎng)絡網(wǎng)絡的流殘存網(wǎng)絡新的路徑：新的流網(wǎng)絡網(wǎng)絡的流殘存網(wǎng)絡此時已無法在此殘存網(wǎng)絡中再找到一條從s到t的路徑，前面的流為最大流Ford-Fulkerson算法Ford-Fulkerson算法Ford-Fulkerson算法的兩個問題當在殘存網(wǎng)絡中無法再找出一條從s到t的路徑時，那么得到的流一定是最大流嗎？最大流最小割定理在殘存網(wǎng)絡中如何找到一條從s到t的路徑？Edmonds-Karp算法最大流最小割定理最大流最小割定理最大流最小割定理最大流最小割定理最大流最小割定理設f是最大流，其所對應的殘存網(wǎng)絡Gf還存在一條從s到t的路徑p，

在殘存網(wǎng)絡Gf

上可以找到一個流f′

最大流最小割定理最大流最小割定理結(jié)論1:也就是由最大流最小割陳述2得出的(S,T)割上，(S,T)的流量(從S到T的流量)等于(S,T)的容量最大流最小割定理(S′,T′)是任意s-t割,根據(jù)能量守恒來證明，即從源節(jié)點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)絡中如何找到一條從s到t的路徑?圖的深度優(yōu)先遍歷方法？Edmonds-Karp算法最短路徑算法Dijsktra算法(復雜度O(mlogn))廣度優(yōu)先搜索（O(m)）短路徑為vs→v2→vt

或者vs→v3→vt，所以通過兩次增廣路徑即可找到網(wǎng)絡的最大流Edmonds-Karp算法：復雜度基于最短路徑算法證明：設在殘存網(wǎng)絡G中找到流f，形成新的殘存網(wǎng)絡G’。從G到G’，增加了指向上一層級的邊，并刪除了指向下一層級的關(guān)鍵邊增加的邊并不會減少從s到其他節(jié)點的距離，但減少的邊有可能會增加s到其他節(jié)點的距離，所以引理得證Edmonds-Karp算法：復雜度基于最短路徑算法Edmonds-Karp算法：復雜度邊ei→j再次成為關(guān)鍵邊時，源節(jié)點到vi的距離至少增加了2跳Edmonds-Karp算法：復雜度可以得出邊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)絡的最大流最大容量路徑算法Dijsktra算法

Edmonds-Karp算法

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

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

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

是節(jié)點vj到節(jié)點vk

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

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

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

到vk

的最短路徑在就要到達vk

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

是vk

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

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

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

到vk

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

個，從vs

到v1

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

個。所以我們只需考慮σsk/σs1

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

的特征向量中心性是一致的，這個從圖12.7很容易得到驗證，這兩個節(jié)點的鄰節(jié)點是相似的，它們都連接了4節(jié)點，同時連接對方。此外，節(jié)點4具有最大的特征向量中心性，這個從圖中也容易得出，節(jié)點4具有最多的鄰節(jié)點，且其鄰居具有較大的特征向量中心性值。PageRankPageRank是谷歌的網(wǎng)頁排序算法，可以認為其特性向量中心性算法的一個變體：節(jié)點的重要性不僅僅取決于有多少個其他節(jié)點指向自己，同時也取決于那些指向自己的節(jié)點的重要性PageRankPageRankPageRankPageRankPageRank另得主要內(nèi)容最大流最小割圖的中心性算法社群發(fā)現(xiàn)算法社群發(fā)現(xiàn)社群發(fā)現(xiàn)基于模塊度的算法基于標簽傳播的算法基于團的算法社群發(fā)現(xiàn):基于模塊度的算法模塊度其中m是圖邊的條數(shù);A為鄰接矩陣，也就是說如vi和vj間存在邊，Aij=1，否則，Aij=0;ki表示vi的度;Si表示vi所屬的社群，Sj表示vj所屬的社群，當Si=Sj時，δ(Si,Sj)=1，當Si?=Sj時，δ(Si,Sj)=0。社群發(fā)現(xiàn):基于模塊度的算法模塊度社群發(fā)現(xiàn):基于模塊度的算法模塊度基于模塊度的算法：例子基于模塊度的算法合并方式將每個節(jié)點看成一個社群，之后逐步的合并社群，直到所有的節(jié)點成為一個社群或者直到合并再不能增加模塊度為止分割方式將整個圖看成一個的社群，之后逐步的分割社群，直到每個節(jié)點都成為一個社群或者直到分割再不能增加模塊度為止Girvan-Newman算法基于分割方式，每次刪除條邊如何選擇一條邊？最多最短路徑通過的邊FastNewman算法基于合并方式Louvain算法基于合并方式：合并和粗化輪流進行，直到模塊度不能再增加為止合并Louvain算法基于合并方式合并：當一個節(jié)點vi并入某個社群S時，只有社群S和節(jié)點vi所代表社群的模塊度發(fā)生改變，其他社群沒有變化Louvain算法基于合并方式Louvain算法基于合并方式Louvain算法：例子第3個圖的模塊度Louvain算法：例子第4個圖的模塊度基于標簽傳播的算法在基本標簽傳播算法LPA的初始化階段，每個節(jié)點被賦予一個標簽，一個簡單的標簽賦予方式是每個節(jié)點被賦予自身的標號。之后，每個節(jié)點從其鄰節(jié)點中選擇一個數(shù)目最多的標簽作為自身的標簽，當數(shù)目最多的標簽具有多個時，則隨機選擇一個基于標簽傳播的算法：例子基于標簽傳播的算法：例子基于標簽傳播的算法重疊社群的標簽傳播算法：COPRA算法COPRA算法：例子COPRA算法：例子因α=1/Nc=1/2，節(jié)點a和節(jié)點g保留所有的二元組，其他節(jié)點因