Flow in Graph

看Course果然自己就是容易走神，所以也就基本上没办法专注进去吧，一天也倒干不了什么事情，还不如对着Slides写东西，这样自己的精神还稍微能够更加专注一些。

这个文章是对于今天看的一些Course的总结，本来想放进不同的Note之中的，不过发现他们有相同的共性，所以我就全部在这一篇文章之中写完以图求更好的连贯性吧。

对应在CS224W之中就是

11. Link Analysis: PageRank

12. Network Effects and Cascading Behavior

13. Probabilistic Contagion and Models of Influence

14. Influence Maximization in Networks

15. Outbreak Detection in Networks 

Web as A Graph

Web Structure

首先讲的内容是谷歌的PageRank算法，这个算法是谷歌的立身之本吧。那么我们就好好的看看整个算法。网络的结构可以表示成为一个有向图(Directed Graph),在这个图之中的Node就是网络的页面，而其Edge就是HyperLinks，也就是那些超链接。在此基础上，我们给出两个概念，分别是进点和出点

对于节点$v$的In就是说，可以到达$v$的那些节点，比如说我们上面附的那个视频的连接和我们的网站做为例子的话。这个网站就是上面的链接的In节点，而由于我们的网站可以到达上面的连接，那么我们的网站的Out节点就是哔哩哔哩的视频界面。

而对于上面的那个图来说

$$In(A) = \{A,B,C,E,G \}$$

$$Out(A) = \{A,B,C,D,F\}$$

可以发现这里的$A$的In以及Out之中都有$A$，也有在距离2之外的节点，这是因为我们的这里的距离不仅仅是限于1而是只要可以走到就行了。有了这个概念的话，我们在给出两个术语，分别是Strongly Connected 与Directed Acyclic Graph(DAG),DAG我们在另外的一篇文章之中讲过了即Overview Of PGM这里面给了例子那么现在就不赘述了。

而所谓的Strongly Connected也就是说对于两个节点他们的进以及出都是相同的，而一般来说就是说出现了环状的结果才有可能有这样的结果。

比如说上面的这张图之中的$In(A)  = Out(A)$，所以在这里就形成了一个Strongly Connected的结构。而一旦形成了Strongly Connected的结构的话，我们就将这里的以$A$为中心的图结构记作是一个Strongly Connected Component.在SCC之中的任何的两个节点都可以通过图形的结构走到对方。

如上图之中就存在了四个SCC结构，而那三个可怜的Single Node自然也算是SCC了。那么如果将SCC看成是一个Strong Node或者称为是Super Node的话，每一个Directed Graph都可以看成是由这些Super Node组成的DAG。

那么怎么找到这些SCC呢？我们注意到一点，对于$In(v)$和$Out(v)$之间只有三种关系，两者相等自然就是SCC了，要不是前者大于后者或者vice verse。在后面的两者的情况之中，如果我们选择了$In(v) \cap Out(v)$的话，自然就可以找到了节点$v$的SCC了。举个栗子

而在2000年,Broder et al.对于互联网做了一个研究，研究了203 million  个网络的URL，即地址。而有1.5billion 个Link。其发现了互联网的状态是如下的

呈现一个领结的形状，对于大多数的Node而言，他们被包含在了一个大小为56million Node之中，其中大概有44million的节点无法与他们的出去的节点相连接，同样大概有44million的节点无法与他们的进的节点相连接。有点抽象，我举个例子，对于世界上的很多人，大家都是互相认识，可以通过某一个熟人认识到其他的人的。而这个群体之中大概是有56million的人，但是在世界上还是有其他的人无法和我们形成连接。比如说那些异常贫困的地区的人们，他们可能知道马云或者王健林是谁，但是他们也仅仅是知道，而无法和他们产生任何的联系，这时候他们就是In，而这时候马云也就是Out，因为他们也永远无法和那些穷困的人们产生联系.

PageRank(AKA.  Google Algorithm)

现在我们对于网络的结构已经有了一定的了解了，那么我们现在来看看怎么给网络排序。为什么要对于网络进行排序呢？因为在网络之中的各个节点的重要性本来就是不同的，你说我的这个网站能有其他的大佬的网站对于整个网络贡献大吗？显然是没有的。那么我们就要使得那些更加重要的网站更容易被世人发现，那么就要进行排序，那么排序的依据是什么呢？我们接下来要思考的就是该怎么对于一个网络排序，参造现实生活之中的现象，我们对于某些事物进行排序的方法是通过投票所进行的，而在网络之中他们的投票的方式就是通过Link，所以这里的Idea 就是 Links AS Votes

一个Page如果有更多的Link的话，那么就可以认为他更重要。但是所有的Link又是相同重要的吗？不见得吧，所以又要对于Link进行排序，所以这就变成了一个递归(Recursive)Question.

那么我们暂时把我们的小脑袋瓜停留在思考节点周围距离为1的Neighbor的情况下。

如果节点$i$的重要程度是$r_{i}$ ，其其有$d_{i}$个出去的Edge的话，每一个Edge上都可以得到$r_{i}/d_{i}$个的重要性。而节点$j$的重要性等于所有输入他的重要性之和.然后$j$再把他的所有的重要性都分配到其他的节点上，很直观的思路。

那么我们就可以很快的得到一个矩阵，将这个矩阵记作是$M$，而其中的$M_{ij} = \frac{1}{d_{j}}$,当且仅当第$j$个page的度为$d_{j}$,且$j\to i$这条边存在。而在矩阵$M$的第$j$列代表了其节点分配到什么其他的节点，所以其和为1.

而对于某一个初始状态来说，我们可以给定每一个节点相同的重要性，也就是说，在初始的时候，每一个节点的重要性都是相同的，假设其重要性是$r_{i}$,而$\sum_{i}r_{i} = 1$,对于整个网络之中的重要性记作是$r$,而经过网络的一轮传播之后，可以得到

$$r = M\cdot r$$

而图像化的解释则如下

其中$M$承担了这个Voting的过程。

大家看到这样的一个矩阵不断乘一个向量的情形，应该想到一个东西叫做状态转移矩阵，或许又想到一个东西叫做马尔科夫链Markov Chain.那么之后就可以达到一个平稳分布(Stationary Distribution)，而最终的这个分布的结果$r$就是我们想要的东西。

那么一个非常朴实的问题就是，上面的东西真的可以收敛到一个平稳分布吗？在网络之中存在两种问题，第一种问题叫Dead Ends，这些End并没有Out-Links，他们就像是在树结构之中的叶节点，无法再向外延展了。还有一种问题叫做Spider Traps，也就是说所有的Out Links 都在一个Group之中，这里就是形成了一个环状的结构 ，在环内的节点的重要性不断的增加，环外的重要性不断的减少。所以我们必然是要解决这样的一个问题的，怎么解决呢？在这里加入一个Jump的机制。

在网络之中以概率$\beta$还是按照上面的操作进行，但是同时以另外的一个概率$1-\beta$跳到其他的任意的一个Page之中。

那么这时候

$$r_{j} = \sum_{i\to j} \beta \frac{r_{i}}{d_{i}} + (1-\beta) \frac{1}{N}$$

如果是在矩阵的状态的话，我们就相当于是对于原来的矩阵$M$进行了下面的一些简单的变换

$$A = \beta M + (1-\beta)[\frac{1}{N}]_{N\times N}$$

然后使用$A$代替$M$做仿射变换，但是事实上在实际之中我们往往并不是这样真正的进行运算，为什么呢？

假设一个数据需要4个字节，假设有两百万个节点的话，那么大概需要我们8GB的内存去记录每一个节点的State，而对于矩阵$M$就需要更多的数据，也就是$4\times 10^18$字节的空间，基本上要耗费如今地球上的所有的储存资源才能搞定这两百万个节点。

所以我们还是使用下面的方法对于重要性进行处理，即

$$r = \beta M \cdot r + [\frac{1-\beta}{N}]_{N}$$

在这时的$M$并非是上面的$A$，所以这时候他是一个Sparse Matrix，也就可以节省大量的存储空间。如果每一个节点只有10个Link的话，只需要10N个存储空间，从上面的指数级别变成了线性的，可以说是一个巨大的进步。

Network Effects and Cascading Behavior

我们每个人都生活在网络之中，不管做什么都会受到网络的影响，生活受到朋友圈的影响、吃饭会习惯性看评分、买东西会习惯性的看评论，这都是我们与这张网络所交互的方式。网络的汹涌澎湃的对我们造成影响，从难以感受的，到可以切实感到的，而我们对于这种影响使用一个特别的术语描述，即Cascade.而Cascade也分成了两种，分别是Decision Based的Model还有Probabilistic Models.这一个Section之中所讲的是Decision Based的模型

Decision Based Model

A or B

这个模型基于一个假说，就是如果我们和周围的人采用相同的策略的话，我们就可以获得更多的回报，即You Gain more payoff if your friends have adopted the same behavior as you.

那么我们就可以建立起来一个Payoff 的策略

如果假设$v$有$d$个Neighbors，其中有$p$的比例选择行为$A$，而相应的有$ 1-p$的比例的节点选择$B$

那么我们就有一个选择的阈值，如果在$a\cdot p > b\cdot (1-p)$的时候就去选择策略$A$,简单的改写一下就是

$$p > \frac{b}{a+b}$$

的时候选择策略$A$,将这时候的$p$记做是$p^*$

文中采用的一个例子是在2011年的五月在西班牙所爆发的Indignados运动，这是一场Anti-Austerity 运动，应该是为了拯救当地的低迷的经济吧。在这场运动之中，推特被用来组织相关的活动。

研究人员选择了在这场运动之中所出现了七十个HashTags，超过了58万条Tweets，涉及的用户超过八万七千人。根据这些数据，创造了两个无向的网络，第一个网络是一个Full Network,也就是所有的Twitter的Follow Links.而第二个网络是一个Symmetric Network，这个网络的要求就是这两个用户之间必须是互相关注的。

先给出下面的几个定义

User Activation Time : 也就是用户开始写相关的Tweets的时间

$K_{in}$:当一个用户开始写Tweets的时候他周围的Neighbors的数量

$K_a$::当一个用户开始写Tweets的时候他周围的Neighbors也在写Tweets的数量。

Activation threshold : 即$k_{a}/k_{in}$,表示了在用户变得Active的时候其周围的Active的用户的比例。

如果$k_{a}/k_{in}$接近于0的话，说明这个用户是在周围的朋友都并不热衷于这个的时候加入的，换言之就是不存在社交压力。而$k_{a}/k_{in}$接近1的haul，则说明这个用户周围的用户都热衷于这个运动，换言之就是这个用户的社交压力很大。

通过对于网络进行分析，很多的用户在自己的周围的朋友们超过半数加入这场运动的时候也就加入了战斗。证明了网络的影响对于我们普通人而言还是比较明显的。研究者接下来有进行了下一个假设的验证，如果在短时间内有很多的朋友加入了这个战斗，那么他就更倾向于加入这个队伍。

其所验证的方法是计算一个变化的速度，即

$$\Delta k_{k_a} / k_{a} = (k_{a}^{t+1} – k_{a}^{t}) / k_{a}^{t+1}$$

这个图就很有意思，横轴的左边是那些在周围的人并不多参加这些活动的时候就会参加这些活动的人，而右边是那些周围的人很多的时候才会选择参加这些活动的人。从图中的数据也可以看出来，那些在周围的朋友都参加了这次活动的人对于这种气氛的快速的变化会显得更敏感，也就是更容易受到这种突然的Burst的影响，而那些周围没啥志同道合的人则更不容易受到这种突然增加的影响。似乎证明了，在周围的人不选择去做的时候你选择去做会有更好的独立思考的能力。但是私认为这里有一个问题就是，推特或者微博这种社交媒体不是仅仅朋友圈范围的，也是一个广场，那些Low Threshold的人受到的影响很有可能是来自于热搜或者是其他的一个机制，而不能直接武断的下判断。

现在我们要在网络之中寻找到Cascades，很简单的思路，由于Cascades表示的是周围的人对于他的影响，所以，如果在一个用户发完之后，他周围的用户也发了信息，那么这里就存在了一个Cascades。

而事实上其实大多数的Cascades都是很小的

绝大多数的Cascades都是发生在最初的时候。

那么还有一个问题就是，是不是那些成功的Cascades都是发生在一个网络的最中心的位置呢？那些KOL的发声是否有意想之中的效果呢？文中使用的方法称为是k-core decomposition,所谓的k-core也就是在这个子图之中每一个节点的度都至少为degree k，有点百万富豪俱乐部的意思，只有度达到了k才可以加入之中。

一个节点有更高的k-core的数量意味着其所在的子图在网络之中越重要。

A and B

上面的模型之中仅仅是可以适用于要么$A$要么$B$的场景，但是事实上在生活之中并不是非$A$即$B$的，成年人全都要。

所以对于上面的策略进行一些简单的修改，或者说加入一个策略就是$AB$,

但是由于采用了这样的一个耍无赖的战术，我们自然也要多付出额外的代价，所以如果选择$AB$的话，我们就要付出额外的$c$.理论的推导就是加法和减法的问题。

对于上面的情况，假设$b$是1固定不动，$A$的回报记作$a$，这是如果有一个节点$w$他在摇摆自己的选择，那么他的选择视$a$与$c$的大小而定

选择AB的仅仅是在$a$的回报很高而且$c$的成本并不高的情况下才会选择，如果$c$的成本太高了，会直接选择$A$，而如果$A$也不够吸引人的话，会去选择$B$。

那么如果情况有所改变

同样这时候假设$b$是$2$，$a$依旧不变，那么$AB$的回报就是$a+1-c$.

其决策情况如上图所示，对于两个情况进行综合的考虑的话，可以得到下满的这样的一张图

Probabilistic Contagion and Models

在上面的Decision Based的模型之中我们考虑问题的方法仅仅是根据他的回报的程度。但是有一些情况下我们根部没有办法进行个人的权衡利弊的，比如说把我困在家里三个月的新冠肺炎，这玩意就根本不是个人的意志可以决定的事情。

那么我们同样是使用流行病作为网络模型之中的例子吧，假设平均而言每一个病人会碰见$d$个新的病人，而以概率$q$去对于他们进行传染，那么以什么概率可以无限的传染下去呢？

$$\lim_{h\to \infty}P[\text{A node as depth h is infected}] > 0 $$

也就是在任意深的情况下都有人被传染，就是可以无限的传染下去了。

如果将$p_{h}$记作是节点在深度$h$的时候被Infected了的概率,写成递归的形式

$$p_{h} = 1 – (1 – q\cdot p_{h-1})^{d}$$

其中$q\cdot p_{h-1}$则是在上一层被感染的概率乘以他感染别人的概率，即传染概率，用1减去就是未被感染的概率，而有$d$个子节点，说明要这$d$个节点都不被传染才可以，所以取一个幂指数，再用1 减去后面的那一堆，就得到了被感染的概率。

所以现在就变成了一个数列的递推的问题，而这个数列的初始值是$1$，也就那个0号病人。根据我们高中的知识，先拿个不动点探探路

很有可能会出现上面的这种情况，也即是数列收敛到了不动点的位置，他就真的一动不动了，因为之后不管怎么迭代也都还在这个不动点的附近进行摇摆，或者换言之，他Trap了。他被Trap了也就意味了这个不管怎么样，不管多深都会有人被感染。如果想让这个传染病消灭的话，就必须要使得其到达0的位置，也就是将其控制在那条线下方。

那么怎么处理呢？首先对于函数的性质进行研究

$$\begin{split} f(0) & = 0 \\ f(1) & = 1 – (1 – q)^{d} < 1 \\ f'(x) & = q\cdot d(1 – qx)^{d-1} \\ f'(0) & = q\cdot d  \end{split}$$

其中这个函数的导数是一个单调非增函数。

如果要求整个流行病消失，我们需要$f(x)$在$y=x$下方，所以在一开始

$$f'(0) = q\cdot d <1$$

将$R_0 = q\cdot d$记作是再生出的新的病人的人数,或者说是一个已经被传染的人传染的人数。当$R_0$接近于1的时候，$q$或者$d$的细小的改变都会导致传染病重新爆发或者是消失。那么防治的手段，比如说中国现在的采用的措施就是减少$d$.

Viruses Spreading

对于病毒而言还有一个治愈率，如果病人治愈了自然无法向下传播了，如果将传播率记作是$\beta$,而将治愈率记做是$\delta$

而其中的每一个节点都会经历下面的这些阶段，从疑似病例，到潜伏期，到被感染，或者疑似之后就得到免疫了。

上面的就是SEIR模型了，那么还有一种模型更加清晰，也更加广为传播一些，就是经典的SIR模型。模型所经历阶段没有了Exposed这个潜伏期，而是直接进被传染

这里的$\beta$与$\delta$与上面的意义相同，都是代表了被感染以及痊愈。当然在这里还有一个隐含的假设就是一旦被治愈了，就获得了永久的免疫。

那么如果考虑SIR这三个状态的导数的

$$\begin{split} \frac{d S}{d t} & = -\beta \cdot S \cdot I \\ \frac{d R}{d t} & = \delta \cdot I \\ \frac{d I}{d t } & = \beta\cdot S\cdot I  – \delta I \end{split}$$

然后更新状态可以得到他们的图像如

当然上面的获得了永久的免疫力的假设还是有一些过于绝对吧。所以还有一个模型也就是SIS就破除了这个假设

这里他们的变化的导数即

$$\begin{split}  \frac{d S}{d t }  = – \beta \cdot S \cdot I + \delta I \\ \frac{d I}{d t} = – \beta \cdot S \cdot I – \delta I \end{split}$$

当然还有更复杂的模型，是学则对于Ebola病毒进行建模的时候使用的模型

当然，如果对于节点之中的类型自己做一些定义或者加一些门控机制或者再增加一些节点，就可以测试出你手中的数据到底拟合的怎么样，也就可以得到你手中的模型了。

Influence Maximization In Network

我们已经知道了在网络之中存在了这种Influence的现象，那么我们怎么通过利用这些现象达到我们的目标呢？商家常用的方法就是使用Discount或者是Samples来帮助我们完成这临门一脚，而这些人得到了这些Benefit之后又会对于他旁边的人们进行安利，从而不断的使得Influence进行延展，从而达到获利的目的。

Linear Threshold Model

每一个节点$v$都有一个随机的阈值$\theta_{v} \sim U[0,1]$,而每一条边上都有一个权重，这个权重就是一种影响力，比如说$b$对于$v$的影响力记作是$b_{v,w}$,那么一个节点如果被激活的话，当且仅当这个影响力超过了阈值。

Independent Cascade Model

假设有一个图$G = (V,E)$,在其中的每一条边$(v,w)$具有概率$p_{vw}$,如果节点$v$是Active的，那么她就有一个机会使得$w$也变成Active，这个概率是$p_{vw}$.那么现在我们就开始初始化一个图，令某些节点是Active的

其中的黄色的节点就是那些Active的节点。

我们现在的问题就是使得上面的图之中尽可能多的节点被Activation，假设一开始激活的节点记作$S$，我们的目标就是最大化最终被激活的节点的数量$f(S)$.可以看成是一个简单的最大化的任务。那么这个任务要怎么处理呢？

很遗憾的说，这个问题是一个NP问题，所以我们无法得到最优解。但是我们所处理的NP问题其实也不少了，最经典的处理NP问题的方法就是使用一些Approximation的算法。

首先给定输入，记作$X_{u}$，其代表了如果我们激活了$u$的话，我们最终可以激活的节点的集合。如果将最初的激活的集合记作是$S_{i}$的话

$$f(S_{i}) = \cup \{ X_{u} |u \in S_{i}\}$$

也就是对于初始的点之中的那些可以最终影响到的点的集合。还是非常的清楚的。那么我们在每一次迭代的时候，都激活那些可以带来最大的Marginal Gain的$u$，也就是说，在每一步迭代的时候，加入的节点都是在当前的状态下可以使得最终被影响的人数增加最多的那个节点。

算法流程如上，还是很直观的。这个算法也被称作是Hill Climbing 算法。可以知道这种算法一定会收敛到一个特定的值，也就是将整个网络在一开始就激活的情况，此时$S_i $就等于网络之中的所有的节点。而整个网络的Return也是一个递减函数

其增长的速率会逐渐的减少，也就是说他是一个Submodular，次模函数。具体的证明过程我就不赘述了。大家可以看看Stanford的Slides里面有具体的证明的过程。

但是上面的算法是一个比较慢的算法，因为在每一步我们都需要去对于所有的边进行一次遍历，这时候的时间复杂度是$O(\text{# of Edges})$为了使得其加速起来我们有另外的一个算法叫做Sketch-Based ALgorithms.可以使得复杂度变成$O(1)$.

其想法是，现在我们有一个假定的(随机生成的)世界$G^{(i)}$,给予其中的每一个节点一个平均分布.然后计算他们的Rank，这个Rank的评分标准是什么呢？以他们可以到达的节点的最低的数量作为评分标准。一个节点可以到达的节点越多，那么这时候他们可以造成的影响就越大，需要注意的是，这里并没有考虑边的值。

但是需要注意的是，这里的Influence的估计是基于单个Rank，可能会出现一些错误。在这里，研究者就考虑生成多个网络，然后按照多个网络的平均值对于上面的节点进行排序。

当然这种Influence Maximum的算法的使用场景应该仅仅是在于市场营销或者是投放广告的时候才有用吧，我感觉这种算法对我来说应用的场景不大。

Outbreak Detection

这里的虽然是讲解如何判断网络之中出现异常的那些点，但是使用的方法依旧还是在上一个Section之中的那一套，思想也很像，所以我们就统一在这里面进行写了。

什么叫做是Outbreak Detection呢？总体的来说，就是对于一个Dynamic的过程，我们在网络之中选择一系列的节点，看看他们的传播的情况是否是正常。

现在假设我们有了一个Graph – $G (V,E)$,以及有了在$G$之中如何Outbreak数据。对于每一个Outbreak $i$，都有一个$T(u,i)$代表了在节点$u$上发生了Outbreak.

那么我们的目标就是寻找节点$S$的一个子集， 可以最大化期望的回报Reward，写成优化问题的形式的话

其中的$p(i)$是Outbreak发生的概率，而$f(i)$是在那些选择的Node之中检测到了Outbreak的回报。

回报包括什么呢？包括

1. Minimize time to detection
2. Maximize number of detected propagations
3. Minimize number of infected people

而成本包括哪些呢？直觉上来说

1. 寻找的范围大会是费时的
2. S如果过于遥远那么也会更加费力

所以我们需要对于惩罚项进行数学化的表达

1. Time to Detection(DT) ：如果寻找到这个点，需要耗费多长时间，那么增加一个惩罚项$\pi_{i}(t) = t$
2. Detection Likelihood(DL) : 发现了多少个Outbreak个点，那么增加一个惩罚项$\pi_{i}(t) = 0 , \pi_{I}(\infty) = 1$
3. Population Affected(PA):这个Outbreak影响力多少人，那么增加一个惩罚项$\pi_{i}(t) = \{ \text{# of infected nodes in outbreak i }\}$

将所有的Penalty记作是$\pi_{i}(\infty)$,那么如果我们检测到了一个Outbreak也就意味着Penalty减少了，也就是说检测到的效用就是这个减少的Penalty

$$f_{i}(S) = \pi_{i}(\infty) – \pi_{i}(T(S,i))$$

需要注意到的是，这个的增加的量也是递减的，也就是说我们的检测的所产生的回报是一个递减的函数，可以看下面的图，当增加了$x’$之后，其所能够影响的范围和其他的节点也会出现重叠，所以这个也是个次模函数，证明过程这里也同样并不赘述了。

那么我们还是使用爬山法(Hill-Climbing)来解决这样的一个问题吗？可能就并不适合了，因为对于爬山法来说，其所适应的情况是放入$S$的成本是相同的，但是在本文之中所适用的场景是对于每一个$s$都有它的自适应的成本，即$c(s)$.而且爬山法确实也是慢的可以。那么我们该怎么对于上面的这个问题进行处理呢？

CELF Algorithm

我们的解决的方法叫做是Cost-Effective Lazy Forward – Selection 算法，是两个贪心算法的组合

1. S’ : Use Benefit-Cost Greedy
2. S” : Use Unit-Cost Greedy

而最后的解则取两个函数的最大值$S = \arg \max (f(S’) , f(S”))$

什么是Benefit-Cost Greedy 算法呢。假设我们现在有预算$B$,有两个Sensors $s_{1}$以及$s_{2}$,其中$c(s_1) = \epsilon, c(s_2) = B$，而他们的Benefit分别是$f(s_1) =2\epsilon ,f(s_2) = B$，所以我们可以计算出Benefit-Cost Ratio分别是

$$f(s_1)/c(s_1) = 2 \quad f(s_2) /c(s_2) =1$$

所以我们会优先选择$s_1$而并非$s_2$,很简单，就是一个计算Ratio的过程。然后根据Ratio选择该在什么地方选择$s$,而对于Unit-Cost Greedy就是假设他们的成本都是一样的，然后再进行Greedy。

而CELF还有一个部分就是Lazy Forward部分，这个部分是干嘛的呢？由于我们的函数的目标是一个Submodular函数,所以每次选择的增量部分$\delta(\cdot)$都会下降。即

$$\delta_{i}(u) \geq \delta_{j}(u) \text{for} i < j $$

那么我们就使用$\delta_{i}$作为$\delta_{j}$的一个Upper-Bound.在第一次迭代的时候，我们不仅仅寻找到了那个最高的Marginal Gain的Sensor，同时我们也可以找到第二第三以及第四……，并对于这些节点进行排序。在下一次迭代的时候，计算第二在有第一的情况下的Marginal Gain，如果他的Marginal Gain依旧是超过了第三在第一轮的情况下的Upper Bound，那么我们就使用第二作为第二轮的Sensor，但是如果第二的Marginal小于第三的Upper Bound，我们就把第二的真实的Marginal与其他的节点的值进行比较，然后把他安排在他该在的位置(即由大到小排序)。这时候第三就上升，计算他真实的Marginal Gain，并与第四的Upper Bound比较，并做相同的判断。通过这样的算法的确可以大幅的降低计算的开销吧。

上图就是实际的情况。

好了这里就写完了有关网络之中的这种Influence的Flow的算法的一些经典的案例了，其实我对于原Slides之中的顺序和算法都按照自己的想法进行了一些删减和自己的处理，可能会和原Slides之中的内容略有不同，非常建议大家去看一看原Slides。