论文标题
有效计算无标度网络中的最大流量
Efficiently Computing Maximum Flows in Scale-Free Networks
论文作者
论文摘要
我们研究了无标度网络上的最大流量/最小切割问题，即其度分布遵循幂律的图。我们提出了一种简单的算法，该算法利用了一个事实，即这种网络的一小部分与流量有关。从本质上讲，我们的算法通过平衡的双向搜索增强了Dinitz的算法。我们在无标度随机网络模型上进行的实验表明了sublinear运行时间。在无标度的现实世界网络上，我们的表现胜过最多两个数量级的常用最高标签的推杆实现。与Dinitz的原始算法相比，我们的修改将搜索空间（例如，在自主系统图中）减少了275倍。 除了这些良好的运行时间之外，我们的算法还具有与推送标签相比的额外优势。后者计算一个预流，这使得最小切割的提取可能更加困难。例如，这与Gomory-Hu树的计算相关。在具有70000个节点的社交网络上，我们的算法在3秒钟内计算Gomory-Hu树，而使用推杆式标签时，可以计算出12分钟。
We study the maximum-flow/minimum-cut problem on scale-free networks, i.e., graphs whose degree distribution follows a power-law. We propose a simple algorithm that capitalizes on the fact that often only a small fraction of such a network is relevant for the flow. At its core, our algorithm augments Dinitz's algorithm with a balanced bidirectional search. Our experiments on a scale-free random network model indicate sublinear run time. On scale-free real-world networks, we outperform the commonly used highest-label Push-Relabel implementation by up to two orders of magnitude. Compared to Dinitz's original algorithm, our modifications reduce the search space, e.g., by a factor of 275 on an autonomous systems graph. Beyond these good run times, our algorithm has an additional advantage compared to Push-Relabel. The latter computes a preflow, which makes the extraction of a minimum cut potentially more difficult. This is relevant, for example, for the computation of Gomory-Hu trees. On a social network with 70000 nodes, our algorithm computes the Gomory-Hu tree in 3 seconds compared to 12 minutes when using Push-Relabel.
