《高级算法设计》课件 第2章 高级图算法

高级算法设计与分析高级图算法林海lin.hai@B站：foretmer主要内容最大流最小割图的中心性算法社群发现算法流网络找到一个从s出发，到t的流量最大的流，这就是最大流问题网络的流网络的流需要满足的两个条件：网络的流如何找到最大流从流量为0开始，逐步增加流量，直到达到最大流量为止从s出发，找到一条到t的可行路径，并将流增加到这个路径能够支持的最大流量在剩余的流网络（残存网络）中再找一条可行的路径，增加相应的流重复以上步骤网络的流原始流网络找到一条路径残存网络？残存网络网络的流残存网络新的路径：新的流网络网络的流残存网络此时已无法在此残存网络中再找到一条从s到t的路径，前面的流为最大流Ford-Fulkerson算法Ford-Fulkerson算法Ford-Fulkerson算法的两个问题当在残存网络中无法再找出一条从s到t的路径时，那么得到的流一定是最大流吗？最大流最小割定理在残存网络中如何找到一条从s到t的路径？Edmonds-Karp算法最大流最小割定理最大流最小割定理最大流最小割定理最大流最小割定理最大流最小割定理设f是最大流，其所对应的残存网络Gf还存在一条从s到t的路径p，

在残存网络Gf

上可以找到一个流f′

最大流最小割定理最大流最小割定理结论1:也就是由最大流最小割陈述2得出的(S,T)割上，(S,T)的流量(从S到T的流量)等于(S,T)的容量最大流最小割定理(S′,T′)是任意s-t割,根据能量守恒来证明，即从源节点s来的流f等于从集合S流到T的流

结论2:是s−t流f等于任意(S′,T′)割最大流最小割定理(S′,T′)是任意s-t割结论3:

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

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

最大流最小割定理Edmonds-Karp算法在残存网络中如何找到一条从s到t的路径?图的深度优先遍历方法？Edmonds-Karp算法最短路径算法Dijsktra算法(复杂度O(mlogn))广度优先搜索（O(m)）短路径为vs→v2→vt

或者vs→v3→vt，所以通过两次增广路径即可找到网络的最大流Edmonds-Karp算法：复杂度基于最短路径算法证明：设在残存网络G中找到流f，形成新的残存网络G’。从G到G’，增加了指向上一层级的边，并删除了指向下一层级的关键边增加的边并不会减少从s到其他节点的距离，但减少的边有可能会增加s到其他节点的距离，所以引理得证Edmonds-Karp算法：复杂度基于最短路径算法Edmonds-Karp算法：复杂度边ei→j再次成为关键边时，源节点到vi的距离至少增加了2跳Edmonds-Karp算法：复杂度可以得出边ei→j最多(n−2)/2次成为关键边总的关键边的次数为O(m∗(n−2)/2)=O(mn)Edmonds-Karp算法最大容量路径也为vs→v2→vt

或者vs→v3→vt，所以也通过两次增广路径即可找到网络的最大流最大容量路径算法Dijsktra算法

Edmonds-Karp算法

Dijkstra算法，对路径的边求最小容量，并最大化之，Edmonds-Karp算法Edmonds-Karp算法流量分解证明Edmonds-Karp算法流量分解证明由流量守恒，可得：在每次容量更新中，路径中最小容量的边(至少一条)的容量会被置0，因图G边的条数是mEdmonds-Karp算法流量分解定理说明了最大流fopt

可以被分解为最多m个路径流{f1,f2,···,fm}，在这些路径流中，必然存在一个流fk≥fopt/m,1≤k≤m，而此流所在路径上所有边的容量必然≥fopt/m。引理得证。Edmonds-Karp算法Edmonds-Karp算法如果原始图G的边数为m，则在任意的残存图Gt中，其边的条数不会超过2m，所以对任意残存图Gt，剩余最大流为

因为容量都为整型主要内容最大流最小割图的中心性算法社群发现算法图的中心性算法度中心性(DegreeCentrality):一个点与其他点直接连接的程度紧密中心性(ClosenessCentrality):一个节点到所有其他节点的距离，一个拥有高紧密性中心性的节点拥有着到所有其他节点的距离较小;中介中心性(BetweennessCentrality):一个节点位于最短路径上的次数，如果有很多条最短路径经过此节点，说明此节点的中介中心性越高;特征向量中心性(EigenvectorCentrality):一个节点的重要性有时也取决于其邻居节点的重要性，与之相连的邻居节点越重要，则该节点特征向量中心性就越高;PageRank:PageRank也是考虑邻节点重要性的一种中心性算法，可看出是特征向量中心性的一种变体。度中心性度中心性是来衡量一个节点重要性相对简单的算法，其基于一个非常直接的观察，和越多其他节点连接的节点越重要紧密中心性紧密中心性用来衡量一个节点处于图的中心的程度，当一个节点越处于中心的位置，则其在图上散播信息的能力越强。为了适应图不是强连通图的情况，采用调和平均数紧密中心性前面的表述形式难以处理这种对几个子图进行连接的情形紧密中心性Dangalchev变体中介中心性在社交网络中，有时候并不是那些具有最多关注者的节点(度中心性)或者处于网络中心位置的节点(紧密中心性)是最重要的，而是那些起着关键桥梁或者中介作用的节点起着决定性的作用其中，σjk

是节点vj到节点vk

的最短路径的个数，σijk是节点vj到节点vk

且经过节点vi

的最短路径的个数中介中心性假设从节点vj

到vk

的最短路径在就要到达vk

前，可沿着不同的路径分别经由三个节点u1、u2、u3，也就是u1、u2、u3

是vk

在最短路径上的前一邻节点中介中心性中介中心性算法如何降低复杂度？快速中介中心性算法累积节点对依赖简单场景节点vs

到任意其他节点只存在一条最短路径，即σst=1,∀vt∈V

快速中介中心性算法累积节点对依赖：简单场景快速中介中心性算法快速中介中心性算法快速中介中心性算法快速中介中心性算法快速中介中心性算法累积节点对依赖：简单场景从前面的例子可以看出，累积节点对依赖(δ值)是个递归式，所以其计算类似于动态规划，也就是从最底层的值，这里是树中叶子节点的δ值(其值为0)开始计算，依次沿着树枝向跟节点计算快速中介中心性算法累积节点对依赖：一般场景在简单场景中，如果最短路径经过某个节点vj，则必然经过其父节点。但是在一般场景中，并不存在这样的关系，也就是最短路径经过节点vj，但并不一定经过其前一跳邻节点从vs

到vk

的最短路径数目共有σsk

个，从vs

到v1

的最短路径数目共有σs1

个。所以我们只需考虑σsk/σs1

比例的最短路径快速中介中心性算法累积节点对依赖：一般场景特征向量中心性在度中心性中，节点的重要程度只考虑了连接数，而没有考虑到连接节点的重要程度。在社交网络上，和一个有影响力的节点有连接关系，显然比和一个普通节点有连接关系，更能使提高自身的重要程度。特征向量中心性特征向量中心性图的邻接矩阵特征向量中心性第一次迭代特征向量中心性第二次迭代特征向量中心性第三次迭代特征向量中心性第四次迭代收敛时特征向量中心性从以上式子可知，特征向量中心性x是图的邻接矩阵A的特征值为λ时的特征向量，这就是为什么称之为特征向量中心性的原因特征向量中心性特征向量中心性发现节点3和节点5

的特征向量中心性是一致的，这个从图12.7很容易得到验证，这两个节点的邻节点是相似的，它们都连接了4节点，同时连接对方。此外，节点4具有最大的特征向量中心性，这个从图中也容易得出，节点4具有最多的邻节点，且其邻居具有较大的特征向量中心性值。PageRankPageRank是谷歌的网页排序算法，可以认为其特性向量中心性算法的一个变体：节点的重要性不仅仅取决于有多少个其他节点指向自己，同时也取决于那些指向自己的节点的重要性PageRankPageRankPageRankPageRankPageRank另得主要内容最大流最小割图的中心性算法社群发现算法社群发现社群发现基于模块度的算法基于标签传播的算法基于团的算法社群发现:基于模块度的算法模块度其中m是图边的条数;A为邻接矩阵，也就是说如vi和vj间存在边，Aij=1，否则，Aij=0;ki表示vi的度;Si表示vi所属的社群，Sj表示vj所属的社群，当Si=Sj时，δ(Si,Sj)=1，当Si̸=Sj时，δ(Si,Sj)=0。社群发现:基于模块度的算法模块度社群发现:基于模块度的算法模块度基于模块度的算法：例子基于模块度的算法合并方式将每个节点看成一个社群，之后逐步的合并社群，直到所有的节点成为一个社群或者直到合并再不能增加模块度为止分割方式将整个图看成一个的社群，之后逐步的分割社群，直到每个节点都成为一个社群或者直到分割再不能增加模块度为止Girvan-Newman算法基于分割方式，每次删除条边如何选择一条边？最多最短路径通过的边FastNewman算法基于合并方式Louvain算法基于合并方式：合并和粗化轮流进行，直到模块度不能再增加为止合并Louvain算法基于合并方式合并：当一个节点vi并入某个社群S时，只有社群S和节点vi所代表社群的模块度发生改变，其他社群没有变化Louvain算法基于合并方式Louvain算法基于合并方式Louvain算法：例子第3个图的模块度Louvain算法：例子第4个图的模块度基于标签传播的算法在基本标签传播算法LPA的初始化阶段，每个节点被赋予一个标签，一个简单的标签赋予方式是每个节点被赋予自身的标号。之后，每个节点从其邻节点中选择一个数目最多的标签作为自身的标签，当数目最多的标签具有多个时，则随机选择一个基于标签传播的算法：例子基于标签传播的算法：例子基于标签传播的算法重叠社群的标签传播算法：COPRA算法COPRA算法：例子COPRA算法：例子因α=1/Nc=1/2，节点a和节点g保留所有的二元组，其他节点因