论文题目

标题：时序交互网络中的流量计算 (Flow Computation in Temporal Interaction Networks)
作者：Chrysanthi Kosyfaki; Nikos Mamoulis; Evaggelia Pitoura; Panayiotis Tsaparas
刊物：2021 IEEE 37th International Conference on Data Engineering (ICDE)
链接：https://ieeexplore.ieee.org/document/9458820

领域综述

I. 概念

时序交互网络对实体之间的数据沿时间轴的转移进行建模。在每次交互中，一定量的数据（金钱、信息、流量）从一个网络结点（实体）流向另一个。分析交互网络可以揭示重要的信息（如循环交易、信息拦截）。例如，金融智能单位通常对寻找交易网络的子图感兴趣，其中结点（金融实体）直接或通过中介机构交换了大量的资金。这种交换可能与犯罪行为有关，如洗钱或盗窃¹。

II. 应用

交互网络中的流量计算在不同领域都有应用。正如已经讨论过的，计算从一个金融实体（如银行账户、加密货币用户）到另一个金融实体的资金流可以帮助定义它们之间的关系和任何中间人角色²。另如，考虑一个运输网络（例如航班网络、道路网络）和计算从源点到目的地结点的最大流量（例如车辆或乘客）的问题。识别大流量传输的情况有助于改善调度或重新设计网络。同样，在通信网络中，测量结点（如路由器）之间的流量可以帮助识别异常情况（如攻击）或不良设计。

III. 独特性

尽管网络流是一个经典问题^{3 4}，但以前没有任何工作对时序交互网络的问题进行过表述和研究。具体来说，对于经典网络流问题，假设输入图的边有一个容量，目标是找到从一个源点$s$到达一个汇点$t$的最大流量。时序交互网络是不同的，因为我们的结点是实体模型，而边是交互的时间序列，每个交互都发生在一个特定的时间戳；也就是说，我们的边没有容量，计算的流量也不是连续的。由于这个原因，我们的问题不能用计算传统图或有容量的时间图的流量的算法来解决（例如⁵）。

论文阅读报告

I. 摘要

时序交互网络捕捉了实体之间沿着时间线的活动历史。在每次交互中，一定量的数据（金钱、信息、流量）从网络的一个结点流向另一个结点。基于流量的分析可以揭示重要的信息，例如在金融交易网络的某个部分出现异常大的资金转移。本文中介绍了交互网络中两个结点之间的流量计算问题，提出并研究了两种流量计算的模型：一种是基于贪心的流量转移假设，另一种是找到最大可能的流量。研究表明贪心流计算问题可以很容易地通过按时间顺序对交互进行一次扫描来解决。对于更难的最大流问题，本文提出了预计算和简化的方法，可以在实践中大大降低其复杂性。本文还处理了交互网络中的流量模式列举问题，并提出了一种有效的路径索引技术。本文使用真实的数据集来评估算法，结果证明了算法的效率和可扩展性。

II. 引入

本文中研究计算时序交互网络中从源点$s$到汇点$t$的流量。例如图1(a)展示了一个交互网络，其中结点表示银行账户，每条边包含形如$(t_i,q_i)$的交互序列，其中$t_i$是时间戳，$q_i$是转移的数据量（金钱）。为了模拟和解决从$s$到$t$的流量计算问题，我们假设在整个交互历史中，任何来自$s$并到达结点$v$的数据在从$v$传递到其他结点前都会暂时累积在$v$的缓冲区$B_v$。作为边$(u,v)$上的交互$(t_i,q_i)$的结果，结点$v$可能会从$B_v$转移$[0,\min\{q_i,B_v\}]$的数据量到$u$的缓冲区$B_u$。例如，如果边$(s,x)$上的交互$(1,\$3)$从$B_s$转移\$3到$B_x$，边$(x,z)$上的交互$(5,\$5)$可以至多从$B_s$转移\$3到$B_z$。在时间轴的最后，汇点$t$的缓冲量模拟了从$s$到$t$转移的流量。

本文提出并研究了两种流量转移的模型作为边$(u,v)$上交互$(t_i,q_i)$的影响以及相应的流量计算问题。第一个模型是基于贪心的流量转移假设，即$v$向$u$转移最大可能的数据量，即$\min\{q_i,B_v\}$。这个模型适用于那些在中间结点预留流量是不实际的的场景（例如运输网络）。根据第二个模型，$v$可以将$[0,\min\{q_i,B_v\}]$范围内任意量的数据转移给$u$，将剩余的数据量保留给未来从$v$（到任何结点）发出的交互。

III. 定义

定义1：时序交互网络

一个时序交互网络是一个有向图$\mathcal{G(V,E)}$。$\mathcal E$中每条边$e=(v,u)$包含一个从结点$v$到$u$的交互序列$e_S=\{(t_1,q_1),(t_2,q_2),...\}$。每个交互$(t_i,q_i)$意味着在时间戳$t_i$从$v$移动数据量$q_i$到$u$。

图2(a)展示了一个例子：边$(z,x)$上的序列$\{(6,2),(8,1)\}$意味着$z$在时刻6向$x$转移了2个单位的数据量，然后在时刻8转移了1个单位的数据量。

我们研究的问题是通过$\mathcal G$的一个子网络$G$来测量从一个特定的源点$s$到一个特定的汇点$t$（$s$和$t$可能重合）的总流量，其中$G$是一个有向无环图（DAG），可以通过舍去无关的结点（例如那些没有从$s$来的路径或没有到$t$去的路径）和边来形成。图2(b)显示了测量从$s$到$t$的流量时的子网络。

为了定义通过DAG图$G(V,E)$的流量$f(G)$，我们按时间顺序考虑$G$的边上的交互。我们的目标是计算来自$s$的总数据量，这些数据量最终会在汇点$t$积累。然而，每次交互的数据量并不一定直接来自$s$。因此，流量计算应该遵守这样的原则：边$(v,u)$上的交互$(t_i,q_i)$所转移的数据量不能大于$v$在时刻$t_i$之前从传入其的交互中收到的，并且在时刻$t_i$之前尚未通过其传出的交互转移的数据量。 具体来说，假设除了$s$外的每个结点$v\in V$，在一个缓冲器$B_v$中保留来自$s$的总数据量，这些数据量从传入其的交互中收到，并且尚未通过其传出的交互转移。那么此时，边$(v,u)$上的交互可以从$B_v$向$B_u$转移$[0,\min\{q_i,B_v\}]$范围内任意量的数据。

给定网络$\mathcal G$的子图$G(V,E)$和源点$s\in V$、汇点$t\in V$，我们提出两个关于从$s$到$t$的流$f(G)$的定义：

问题1：贪心流计算

按时间顺序考虑$s$中的所有交互，并假设边$(v,u)$上的每个交互$(t_i,q_i)$从$B_v$向$B_u$转移最大可能的数据量$\min\{q_i,B_v\}$，$f(G)$是最终在汇点$t$缓冲的总数据量。

问题1基于这样的假设：每次交互都会转移最大可能的数据量。这个假设适用于那些在中间结点保留数据量成本很高，应尽力避免的网络（例如运输网络）。

问题2：最大流计算

按时间顺序考虑$s$中的所有交互，并假设边$(v,u)$上的每个交互$(t_i,q_i)$可以从$B_v$向$B_u$转移$[0,\min\{q_i,B_v\}]$范围内任意量的数据，$f(G)$是最终在汇点$t$缓冲的总数据量。

问题2假定每次交互的源结点不一定要转移最大可能的数据量，并且可能为未来的交互保留一些数据量：这可能会增加从$s$到$t$的最大总流量。例如在金融网络中，这一假设是成立的，因为缓冲不承担任何成本。

定义2：网络模式和实例

一个网络模式$G_P(V_P,E_P)$是一个有向无环图，其中每个结点$v\in V_P$有一个标签$l(v)$。时序交互网络$\mathcal G$中模式$G_P$的一个实例是一个满足以下条件的子图$G_M(V_M,E_M)$：

• 存在一个从模式$G_P$的点集$V_P$到$G_M$的点集$V_M$的映射$\mu:V_P\rightarrow V_M$
• 对于$G_P$中的两个点$v,u$，$\mu(v)=\mu(u) \iff l(v)=l(u)$
• $(v,u)\in E_P \iff (\mu(v),\mu(u))\in E_M$

问题3：流量模式枚举

给定一个网络$\mathcal G$和一个模式$G_P$、源点$s\in V_P$、汇点$t\in V_P$，找到$\mathcal G$中$G_P$的所有实例；对于每个实例$G_M$，计算（贪心/最大）流$f(G_M)$。

图3展示了一个网络$\mathcal G$，一个模式和该模式的一个实例。注意在这个模式中两个（或更多）具有相同标签的结点应该被映射到$\mathcal G$中的同一个结点。在这里，$a,b,c$分别被映射为$u_1,u_2,u_3$。我们的目标是找到所有的模式实例并测量每个实例的（最大）流量（例如：实例图3(c)的最大流$5）。表一总结了本文中经常使用的符号。

IV. 算法

A. 贪心流计算

算法1展示了贪心流计算算法的步骤，该算法解决了问题1。首先初始化DAG图$G$中的所有结点的缓冲区。回顾一下，每个缓冲区累积了从$s$收到的总数据量，所以所有的缓冲区初始都应该是0，除了$B_s$，我们将其设置为$\infty$，以便所有从$s$发出的交互$(t_i,q_i)$都能够将$q_i$转移到其目标结点。然后，我们按时间顺序处理所有的交互$(t_i,q_i)$。根据问题的定义，每个交互从其源点$src_i$的缓冲区$B_{src_i}$中减去$\min\{q_i,B_{src_i}\}$个单位，并将其加入其目的结点$dest_i$的缓冲区。在处理完所有交易后，缓冲区$B_t$将存放从$s$到$t$的总数据量$f(G)$。

时间复杂度

算法1在$O(m_G)$的时间内运行，其中$m_G$是$G$的边上的交互总数，假设交互可以按时间顺序访问。

B. 基于线性规划的最大流计算

在一般情况下，算法1并不能解决问题2。例如，在图2(b)中，从$s$到$t$的最大可能转移量是5；如果边$(y,z)$上的交互$(3,5)$不从$B_y$转移任何单位到$B_z$，而是将这些单位保留从$y$到$t$的交互$(4,4)$，我们就会得到这个结果。

问题2可以用线性规划（LP）来制定和解决。我们为每条边上的每个交互$(t_i,q_i)$定义一个变量$x_i$；$x_i$对应该交互结果将被转移的数据量。注意对于源自源点$s$的交互，有$x_i=q_i$，因为如果不从$s$转移最大可能的数据量则不能增加到达汇点$t$的总数据量。

每个变量$x_i$的值是非负的，且不能超过$q_i$。此外，还有一个约束条件，即边$(src_i,dest_i)$上的交互$(t_i,s_i)$不能转移大于$B_{src_i}$的数据量，即到时刻$t_i$为止，流入$src_i$的总单位减去流出$src_i$的总单位。鉴于上述约束条件，我们的目标是找到所有变量$x_i$的值，使得到达汇点的总数据量最大化。因此，我们制定以下的线性规划。

$$ Maximize: \sum_{dest_i=t}x_i $$

$$ Subject\ to:0\le x_i\le q_i $$

$$ x_i\le \sum_{dest_j=src_i\land t_j<t_i}x_j-\sum_{src_j=src_i\land t_j<t_i}x_j $$

时间复杂度

问题2为每个交互定义了一个变量，因此LP问题中的变量数为$O(m_G)$。LP问题的复杂度至少为变量数的平方⁶，因此，计算通过$G$的最大流的成本至少是$O(m^2_G)$。

V. 最大流计算框架

鉴于与算法1相比，LP的时间复杂度很高，本文研究了比直接使用LP求解器更快地解决问题2的方法。在V-A节中，本文表明，对于一类特定的图，我们可以使用算法1在线性时间内解决问题2。在第V-B节中，本文提出了一种预处理方法，它消除了保证不影响求解的交互（还有可能的$G$的边和结点）。最后，在第V-C节中，本文提出了一种图的简化方法，该方法使用算法1计算部分解决方案，因此减少了最大流计算的总体成本。把所有这些方法放在一起（第V-D节），就会产生一种强大的时序交互网络的最大流计算技术，它比直接使用LP求解器要快几个数量级。作者通过实验证明了这一点。

A. 可用算法1计算最大流的图

对于一类图，算法1可以计算出最大流。这意味着对于这些图，我们不必制定和解决一个LP问题，并且我们可以在与交互数量成线性关系的时间内计算出$f(G)$。

定理1

如果对于每个结点$v\in V\{s, t\}$，$v$恰有一条出边，那么贪心算法能够计算出$G$的最大流。

证明：考虑一个满足定理条件的图$G(V,E)$。假设一个结点$v\in V\{s,t\}$有出边$(v,u)$，其上一次交互$(t_i,q_i)$没有转移最大可能的流量，相反保留了一些数据量。那么这就意味着，在时间$t_j>t_i$时，$u$可用于转移的流量将严格小于可能的最大值。这只能减少离开$u$到达$t$的流量，保留在$v$中的流量不能以其他方式利用，因为$(v,u)$是$v$的唯一出边（即$t$只能通过$u$从$v$到达）。因此，在每次交互中传输最大可能的数据量，才能在汇点$t$积累最大流量。

图4展示了两个满足该条件的DAG示例图，其中算法1保证能计算出最大流。图4(a)中的DAG是一个链，即一个从$s$开始到$t$结束的成对连接的结点序列。图4(b)是另一类DAG，其中每个结点，除了$s$和$t$都恰有一条出边。

时间复杂度

检查输入图$G$是否满足定理1的条件（即检查每个结点的出度）只需花费$O(|V|)$的时间。

B. 图预处理算法

在应用LP计算不满足定理1条件的DAG上的最大流之前，我们可以通过删除不影响解的交互来降低问题的复杂度。例如，图1(a)图中边$(z,t)$上的交互$(2,3)$可以去掉，因为时间戳2比所有进入$z$的交互的时间戳都要小。去除交互对LP的性能影响很大，因为其成本与交互的数量$m_G$成平方关系。此外，去除交互可能会同时去除边和结点，并可能大大简化输入图$G$。

本文提出了一种预处理算法，它从G的交互、边和结点中剔除了那些对最大流计算没有贡献的东西，步骤如下：

按拓扑序考虑$G$的所有结点，对于每个不是源或汇的结点检查其出边，并从其中删除所有时间戳小于该结点的最小传入时间戳的交互（第9-13行）。如果某条边上没有留下任何交互，该边就从$G$中删除（第14-15行）。删除从当前结点$v$发出的边上的交互可能会减少拓扑序中下一个结点$v$的传入交互的最小时间戳。因此，只需要对结点进行一次遍历就可以消除不必要的交互。此外，从$v$中删除一条出边可能会导致对应结点$v$没有入边。这种情况下，将导致$u$和它的所有出边被删除（因为$u$没有办法从$s$向$t$转移任何数据量），这种情况在算法2的第3-5行处理。如果当前结点$v$的所有出边被删除，那么我们必须删除$v$和它的所有入边（第18-21行）。这可能会导致一个或多个连接到$v$的结点$w$也没有出边。在这种情况下，会触发一个递归的结点删除。如果递归删除导致源$s$没有出边，那么算法2就会以$f(G)=0$终止，从而不再需要执行LP。当所有连接到汇点$t$的结点被删除时，也会发生同样的情况。

时间复杂度

算法2的成本与交互的数量呈线性关系，因为对于每条被检查的边，其上每个交互最多被处理一次；每条边最多被检查删除两次（一次为出边，另一次为入边）；拓扑排序对DAG的每条边检查一次。因此算法2的复杂度是$O(m_G)$。

C. 链缩减

对问题2的算法框架的最后一部分是一个图的简化算法，基于这样的观察：源于源点的链可以被简化为单边。简而言之，图简化算法通过对这些链应用贪心算法，迭代地识别和减少这些链，直到不能进一步减少。然后用LP解决所得到的图。

一条由结点$v_1,v_2,...,v_k$表示的链$C$是$G$的一个子图，其中每一个结点$v_i,i\in [2,k-1]$在$G$中恰有一条出边到结点$v_{i+1}$。算法基于这样一个事实：任何从图$G$的源开始的链都可以被减少为一条边而不影响图中最大流计算的正确性。为了将链$sv_1v_2...v_k$缩为一条边$(s,v_k)$，我们在链上运行算法1的变体，如算法3所示，并为最后一条边$(v_{k-1},v_k)$上的每个交互定义一个新的从$s$到$v_k$的交互。算法3在将所有缓冲区初始化为0后（除了$B_s$被设置为$\infty$），按时间顺序访问链上的所有交互，并更新相应结点的缓冲区，如算法1。每个以链中最后一个结点$v_k$为目标的交互$(t_i,q_i)$都会产生一个新的交互，其数据量从$v_{k-1}$转移到$v_k$。在处理完所有的交互后，该算法返回新边$(s,v_k)$及其交互集$(s,v_k)_S$。

下面的定理表明，对DAG图$G$，用算法3计算的单边替换从源点$s$开始的链并不影响最大流计算的正确性。

定理2

令$G$为一个包含源点$s$的DAG图。假设$G$包含一条链$sv_1v_2...v_k$，令$G'(V',E')$为一个DAG图，其中$V'=V-\{v_1,v_2,...,v_{k-1}\},\ E'=E-\{(s,v_1),(v_1,v_2),...,(v_{k-1},v_k)\}+\{e\}$。其中新边$e$为链$sv_1v_2...v_k$对应的算法3输出。则通过$G$的最大流等于通过$G'$的最大流。

证明：回顾一下，在$G$的源点保留流量不能增加到达其汇点的最大流量。由定理1，同样的道理也适用于源自源$s$的链$sv_1v_2...v_k$中的所有结点$\{v_1,v_2,...,v_{k-1}\}$，但最后一个结点$v_k$除外。因此，用算法3计算的边$e$替换链$sv_1v_2...v_k$并不影响$G$中最大流计算的正确性，因为$v_k$在任何时候从$v_{k-1}$收到的数据量都等于$v_k$在任何时候通过$(s,v_k)=e$收到的数据量。

算法4是所提出的图简化方法的伪码，它使用算法3逐步减少从s开始的链。注意，取代链$sv_1v_2...v_k$的边$(s,v_k)=e$可能已经存在于图中。在这种情况下，算法3产生的新边$e$的交互$e_S$将与现有边$(s,v_k)$的交互合并。链缩减和由此产生的边的合并可能会导致$G$中出现新的链。因此，算法在每次缩减后都会重新检查可能的新链。

时间复杂度

$G$的链上的每条边在被缩减之前只会被检查一次。此外，每条新创建的边如果成为链的一部分，也最多被检查一次。通过链缩减产生的新交互数不能多于链的最后一条边上的交互数。因此，算法4对每条边（及其上的交互）最多检查两次。总体而言，其成本为$O(m_G)$。

D. 融合

算法5总结了对时序交互网络中最大流计算的建议。首先，我们通过测试定理1的条件来判断是否可用算法1在DAG图$G$上计算最大流。如果这不可能，我们应用算法2删除与问题无关的交互（可能还有结点和边）。如果得到的图的结构发生了变化，我们再次检查算法1是否能够解决最大流问题。否则，我们首先通过应用算法4简化图，然后用LP计算所得图的最大流。

VI. 流模式搜索

到目前为止，我们假设我们要计算流量的DAG是给定的。在这一节中，我们将解决问题3：在一个时序交互网络中找到一个小的DAG模式$G_P$的实例，并测量每个实例的最大流。寻找图模式的实例是无标签图中的一个经典搜索问题。另一方面，子图的最大流计算可能很费时，所以使用以前工作中的一些方法简单地寻找模式实例（如⁷），并计算每个实例的流量可能不是最好的方法。本文提出了一种流量路径索引技术，它预先计算出网络$G$的路径，以及它们的流量。模式搜索可以从预处理的数据中大大受益。在提出建议之前，我们先讨论一个基线图浏览方法。

A. 图浏览方法

解决模式搜索问题的直接方法是遍历整个网络$\mathcal G$，并通过逐步扩大模式的部分匹配来识别$G_P$的实例。如⁷所述，图浏览适合于在可能拥有巨大数量实例无标签图（如$\mathcal G$）中进行模式搜索。具体来说，图浏览（GB）方法，以拓扑序考虑$G_P(V_P,E_P)$的结点。GB是一种回溯算法⁸，它从$G_P$的源点开始，试图将每个顶点$v_P\in V_P$映射到一个顶点$v\in \mathcal G$，从当前实例化的结点在$\mathcal G$中的相邻结点中选择，并确保所有的映射和结构约束同先前实例化的结点相符合。对于每个确定的模式实例，我们计算相应的流量。

注意对于某些模式，如图3(b)的链式模式，它满足定理1的条件，我们可以逐步计算其实例的最大流。也就是说，对于每个与这种模式的前缀相匹配的部分实例，我们可以应用算法3将其建模为一条边$e_I$。当这部分实例被一条边$e$扩展后，我们再通过在有两条连续的边$e_I$和$e$的图上运行算法3来增量更新流量。当我们回溯并再次扩展之前，我们可以重新使用$e_I$，避免多余的重复计算。

B. 流路径索引

在搜索任何模式之前，本文建议对网络$\mathcal G$进行预处理，并从中提取可作为模式实例组成部分的小路径。这样，我们就可以避免从头开始搜索模式$G_P$的子图；相反，我们可以检索模式的结构成分（和预先计算的流量数据），然后用连接算法将它们“缝合”起来。提取和索引子图以辅助图搜索的想法以前就被使用过^{9 10}；在这里，我们将其应用于流模式搜索的场景下，并展示如何从沿索引路径的流量预计算中获益。

索引构建

我们应用GB来识别和索引所有长度为$k$的路径。我们为每个长度为$k$的路径建立一个表，保存该长度的所有路径。也就是说，对于每条路径，我们都要存储：(i) 形成该路径的顶点ID序列；(ii) 对该路径应用算法3所产生的交互$e_S$序列。每张表都按照顶点ID序列进行排序，以便于合并连接。

模式搜索

算法6展示了使用索引的模式搜索算法的步骤。为了找到一个给定模式$G_P$的实例，我们首先确定$G_P$中的索引路径子模式，访问和连接相应的表，以形成$G_P$的实例。一旦确定了一个完整的模式匹配$G_M$，我们就计算$G_M$的流量$f(G_M)$。我们利用预先计算好的流量序列$e_S$来构成$G_M$的路径集，从而降低计算$f(G_M)$的成本。

例如，考虑图6(a)中所示的流模式$G_{P_1}$。假设我们已经预处理了所有两跳和三跳循环路径的实例，它们分别从两个表$L_2$和$L_3$中的同一个结点$a$开始，并以该结点为终点。在这种情况下，我们可以很容易地计算$G_{P_1}$的所有实例，只需访问和使用预处理的数据。具体来说，我们扫描$L_2$和$L_3$并将其合并，以便从$L_2$和$L_3$中找到所有具有相同起点（因此也是终点）的路径对。为了计算每个模式实例的总流量，我们简单地将所有预先计算好的流向两条路径的汇的流量相加。

预计算的流量并不总是能被使用。例如，在图7(b)的图$G_{P_2}$中，路径$a\rightarrow b\rightarrow c\rightarrow d$不是孤立的；因此，其实例的预计算流量信息并不起作用。不过，即使预计算的流量信息没有用，也可以利用索引表来加速寻找模式的实例。

C. 非刚性模式

到目前为止，我们所定义的模式都有一个刚性的结构。然而，在某些应用中，我们可能对搜索具有更宽松结构的模式感兴趣。例如，考虑一种洗钱模式，源结点$a$向收件人（没有固定的数量）发送付款，然后这些收件人将钱送回给$a$。现在，我们只能定义一组不同的模式，并独立测量它们的流量，如图7(a)所示。然后，我们可以把对应于同一结点$a$的不同模式的所有实例的流量汇总起来，以计算出通过其他节点从$a$到$a$的总流量。

这种方法有几个不足之处。首先，我们将不得不计算和合并多个模式的查询结果。其次，对于我们应该使用多少个模式没有限制。第三，最终结果可能不正确，因为子模式的流量可能包括在父模式的流量中（例如，图7(a)中第二个模式的实例包括第一个模式的两个实例）。

为了避免这些问题，我们可以定义一个宽松的模式，如图7(b)所示，它通过任意数量中间结点的平行路径将$a$与$a$连接起来。使用我们的预计算方法，找到这种模式的实例并测量其流量是非常容易的，因为我们只需要扫描2跳循环表$L_2$，对于$a$的每个实例，汇总该表相应行的流量。我们还可以对非刚性模式中的路径数量设置约束。例如，我们可能对图7(b)所示模式中的至少包括10条路径的实例感兴趣。

VII. 总结

这篇论文中研究了时序交互网络中的流量计算问题。作者定义了两种流量计算模型，一种是基于贪心的流量转移，另一种是假设可进行任意的流量转移，目标是计算最大流量。本文表明，基于第一个模型的计算可以在线性时间内完成，同时提出并评估了一些技术，大大降低了最大流量计算问题的成本。基于贪心的计算方法的价值不仅在于有效地解决贪心转移假设下的问题，而且还在于尽可能地简化最大流计算。这项技术很容易适用于该问题的时间限制版本，即我们只考虑在一个时间窗口内发生的交互（即简单地忽略窗口外的所有交互）。此外，如果交互按时间顺序来自一个流，贪心算法可以无缝地用于持续维护汇点的传入流。

参考文献