Cut Tree Construction from Massive Graphs∗
Takuya Akiba†
†

Preferred Networks, Inc.

Yoichi Iwata‡
‡

Yosuke Sameshima#

National Institute of Informatics

#

Naoto Mizuno§

Recruit Holdings Co., Ltd.

Yosuke Yano#
§

The University of Tokyo

arXiv:1609.08723v1 [] 28 Sep 2016

akiba@preferred.jp, yiwata@nii.ac.jp,
yosukes@indeed.com, mizuno@eps.s.u-tokyo.ac.jp, yosukey@indeed.com

Abstract—The construction of cut trees (also known as GomoryHu trees) for a given graph enables the minimum-cut size of the
original graph to be obtained for any pair of vertices. Cut trees
are a powerful back-end for graph management and mining, as
they support various procedures related to the minimum cut,
maximum flow, and connectivity. However, the crucial drawback
with cut trees is the computational cost of their construction. In
theory, a cut tree is built by applying a maximum flow algorithm
for n times, where n is the number of vertices. Therefore, naive
implementations of this approach result in cubic time complexity,
which is obviously too slow for today’s large-scale graphs. To
address this issue, in the present study, we propose a new
cut-tree construction algorithm tailored to real-world networks.
Using a series of experiments, we demonstrate that the proposed
algorithm is several orders of magnitude faster than previous
algorithms and it can construct cut trees for billion-scale graphs.

I. I NTRODUCTION
The minimum cut (min-cut), maximum flow (max-flow), and
connectivity are fundamental concepts in graph theory. For
a pair of vertices s and t, the s-t min-cut is the minimum
set of edges such that the removal of any one edge makes
s and t disconnected. The s-t max-flow is the flow from s
to t with the maximum amount (see Section II for a formal
definition). The beautiful mathematical duality of the min-cut
max-flow theorem [17], [18] states that the values of the s-t
min-cut and the s-t max-flow are equal. This value is also
called the connectivity between s and t. As graph-theoretic
building blocks, the min-cut, max-flow, and connectivity are
used in a wide range of areas, including graph analysis and
mining [3], [4], [9], [20], [31], [33], [34].
Because of their importance and rich mathematical properties, a myriad of algorithms for computing the max-flow and
min-cut have been proposed [16], [21], [22], [29]. However,
they each have at least quadratic time complexity in theory [29], making it time consuming to compute the max-flow
between a pair of vertices. Moreover, practical applications often require the repeated computation of max-flows for different
vertex pairs. Therefore, the scalability of connectivity-based
network-analysis methods is severely limited.
However, a graph has cut trees [24] (also known as
Gomory–Hu trees), which are a succinct encoding scheme of
all the min-cuts of the original graph. In other words, the mincut of the original graph can be quickly obtained from the cut
tree for any pair of vertices. Moreover, cut trees are compact,
∗

This work is done while all authors were at National Institute of
Informatics. A shorter version of this paper appeared in the proceedings of
ICDM 2016 [1].

having a space complexity that is linear with respect to the
number of vertices (see Section II for a formal definition).
Thus, it appears that cut trees could play a key role as
a powerful back-end for various network-analysis methods.
However, the crucial drawback is the huge computational cost
of constructing cut trees. In general, a cut tree is built by
running a max-flow algorithm n times, where n is the number
of vertices [24], [25]. Therefore, naive implementations of
this approach have at least cubic time complexity, which is
obviously too slow for today’s large-scale graphs.
Contributions. To address the abovementioned issue, we
propose a new cut-tree construction algorithm tailored to realworld networks of interest, i.e., large-scale social and web
graphs. The proposed algorithm combines a number of new
techniques within three main components.
• First, we aggressively reduce the given graph into smaller
graphs using a series of rules, allowing the total cut tree
for the original graph to be easily obtained from the cut
trees for these smaller graphs (Section VIII).
•

Second, to reduce the number of executions of the maxflow algorithm, we propose two efficient heuristics to find
“easy” min-cuts a priori (Sections V and VI).

Third, to further reduce the time consumption of the maxflow algorithms, we discuss the most suitable techniques
for these real networks, and propose a practical improvement using bidirectional searches (Section IV). We
also discuss source–sink pair ordering strategies (Section
VII).
Experimental results using real large-scale networks confirm
that the combination of these new techniques yields a highly
scalable cut-tree construction algorithm. Specifically, whereas
previous sophisticated implementations could not construct cut
trees for graphs with over one million edges in less than ten
hours, the proposed algorithm successfully constructs cut trees
for very large social and web graphs with more than one billion
edges within eight hours. We also confirm that the data size
of the cut trees is sufficiently smaller than the original graph
itself, and find that the average query time for the min-cut
size is several microseconds. Overall, our experimental results
verify that the proposed algorithm makes cut trees a practical
back-end for large-scale graph management and mining.
•

Applications. Let us consider some applications of cut trees
that will be enabled by the proposed algorithm.
• Application 1: For any two vertices, we can consider

their connectivity as an indicator of the strength of the
relationship. Thus, it is natural to use the connectivity as
a feature of prediction tasks related to vertex pairs (e.g.,
the link prediction problem [28]). Cut trees enable the
connectivity to be used for such tasks, as the connectivity will be computed for many vertex pairs during the
training and evaluation stages.
•

Application 2: As mentioned above, the min-cut, maxflow, and connectivity are used as graph-theoretic building blocks in various graph analysis and mining techniques. Cut trees can substantially improve the scalability
of these methods as a back-end.

•

Application 3: As cut trees elegantly
encode all the min
cuts (i.e., the min-cuts of n2 pairs) of the original
graph in O(n) size, we can design algorithms that extract
interesting statistics about all the min-cuts from a cut tree
in near-linear time without instantiating all the min-cuts.
We discuss a few examples of algorithms that efficiently
compute the connectivity distribution and connectivity
dendrogram from cut trees in Section X.

Scope. We focus on real sparse graphs such as social networks
and web graphs, and design an efficient algorithm tailored to
these networks. We do not claim that our algorithm is efficient
for all kinds of graphs, e.g., those arising from optimization
problems.
Organization. The remainder of this paper is organized as
follows. In Section II, we explain the basic notation and definitions used throughout this paper. We present an overview of
our cut-tree construction algorithm in Section III. We discuss
s-t cut computation algorithms tailored to real-world networks
of interest in Section IV. In Sections V and VI, we propose two
heuristics to efficiently find min-cuts without running maxflow algorithms. We explain how to select separation pairs in
Section VII. Section VIII is devoted to the graph reduction
rules. We present our experimental results in Section IX, and
discuss applications of cut trees to large-scale network analysis
in Section X. We describe some previous work in this area in
Section XI. Finally, we conclude the paper in Section XII.
II. P RELIMINARIES
A. Notations and Definitions
In this paper, we focus on networks that can be modeled
as undirected graphs. Let G = (V, E) be an undirected graph.
We denote the degree of a vertex v by d(v). For a vertex
subset S ⊆ V and a fresh vertex s 6∈ V , we denote the graph
obtained by contracting S into s as G/(S → s), i.e., the graph
obtained by adding s, reconnecting all edges between S and
V \ S to s, and removing S. For a directed graph, we denote
the set of edges outgoing from vertex v as δ + (v) and the set
of incoming edges as δ − (v).
B. Network Flows
Let G = (V, E, c) be a directed graph with an edge-capacity
function c : E → R≥0 . For two distinct vertices s and t, a

vertex subset S ⊆ V is called an s-t cut if S contains s but
does not contain t, and its capacity cG (S) is defined as the
total capacity of the outgoing edges {uv ∈ E | u ∈ S, v 6∈ S}.
An s-t cut with the minimum capacity is called the minimum
s-t cut.
A function f : E → R≥0 is called an s-t flow if it satisfies
the following two conditions:
• 0 ≤ f (e) ≤ c(e) (∀e ∈ E), and
P
P
•
e∈δ + (v) f (e) =
e∈δ − (v) f (e) (∀v ∈ V \ {s, t}).
The
value
of
an
s-t
flow
f is defined by val(f, s) =
P
P
f
(e)
−
f
(e),
and an s-t flow with the
e∈δ + (s)
e∈δ − (s)
maximum value is called the maximum s-t flow. The famous
min-cut max-flow theorem states that, for any graph, the
capacity of the minimum s-t cut is equal to the value of the
maximum s-t flow.
Let f be an s-t flow (which may not be maximum). A
residual graph with respect to f is a directed graph Gf =
(V, Ef ) defined as
Ef = {e ∈ E | f (e) < c(e)} ∪ {vu | uv ∈ E, f (uv) > 0}.
An s-t path in the residual graph Gf is called an f -augmenting
path. If there exists an f -augmenting path, we can obtain a
greater flow f 0 . A flow is maximum if and only if there are
no f -augmenting paths. For any maximum s-t flow f , a set
of vertices S reachable from s in Gf becomes a minimum s-t
cut, which is also minimal among all the minimum s-t cuts in
the sense of set inclusion.
In this paper, we focus on undirected graphs with the
unit-capacity function c(e) = 1; however, most parts of the
proposed algorithm can be applied to capacitated graphs. In an
undirected graph G = (V, E), the cut and flow are defined by
considering the bidirected graph Ḡ = (V, Ē) obtained from G
by replacing each undirected edge uv with two directed edges
uv and vu. In this setting, the capacity of the minimum s-t
cut is the number of edges that must be removed to separate
s and t into different connected components. Thus, this value
is called the connectivity between s and t, which is denoted
by λG (s, t).
C. Cut Trees
For an undirected graph G = (V, E), a tree T = (V, E 0 ) on
the same vertex set is called a cut tree (or Gomory-Hu tree)
if it satisfies the following condition for any distinct vertices
s, t ∈ V :
λG (s, t) = min cG (Se ),
e∈Pst

where Pst is the unique path from s to t in the tree T , Se is
the connected component of T containing s obtained by the
removal of an edge e, and cG (Se ) is the number of outgoing
edges from Se in the graph G. In other words, the condition
states that at least one of the cuts Se induced by an edge e on
the path Pst becomes the minimum s-t cut. For convenience,
we will construct an edge-weighted cut tree T = (V, E 0 , c0 )
satisfying c0 (e) = cG (Se ) for all e ∈ E 0 . Using such a tree,
we can obtain the connectivity between two vertices s and t

𝑖
𝑎

𝑐

𝑒

𝑔

𝑏

𝑑

𝑓

ℎ

Algorithm 1: Basic construction algorithm [24].

𝑖
𝑙

𝑎

𝑚

𝑏

2
2

𝑗

𝑐

3

3

𝑒

2

𝑔

3

𝑑

𝑘

3

2

3

3 𝑗
𝑓

ℎ

𝑙

3
2

3

Procedure Construct-Basic(G = (V, E))
Init(G);
Separate-All();
return T ;

4

Procedure Init(G = (V, E))
G ← {(G, V )}; T ← ({V }, ∅, ∅); φ ← ∅;

1
2

𝑚

𝑘

Fig. 1. An example of the cut tree.

by simply computing the minimum c0 (e) value over the edges
e ∈ Pst .
Figure 1 shows an example of a graph (left) and its cut tree
(right). The orange-colored edges have a weight value of two
and the green-colored edges have weight three. Each edge in
the tree induces a minimum cut in the original graph; e.g., the
edge eg in the cut tree induces a cut {a, b, c, d, e, f } and this
is the minimum e-g cut in the original graph. We can find the
connectivity by identifying the minimum weight edge on the
unique path; e.g., the unique path from d to j consists of edges
dc, ce, eg, and gj, and edge eg has the minimum weight of
two. Thus, the connectivity between d and j is two.

5
6
7

8
9
10
11
12
13
14
15
16

D. Basic Cut-Tree Construction Algorithm
Algorithm 1 describes the basic algorithm developed by
Gomory and Hu for constructing a cut tree [24]. In the
algorithm, each vertex of tree T corresponds to a subset of
vertices X ⊆ V , which induces a partition of V . To avoid
confusion, we refer to the vertices of the tree as nodes. Initially,
T consists of only a single node V . The algorithm iteratively
picks a node X of size at least two, and splits it into two
smaller nodes (Procedure Separate). The details of this part
are described later. Finally, each node of T corresponds to a
single vertex, and we have obtained the cut tree.
For each node X ⊆ V , there is a corresponding graph
GX on a vertex set VX ⊇ X. Vertices in VX \ X are
called contracted, and each contracted vertex v corresponds
to an edge φ(v) incident to the node X. At first, the node
V corresponds to the original graph G, and there are no
contracted vertices.
We now describe the details of Procedure Separate. When
splitting a node X, the algorithm first picks an arbitrary pair
{s, t} from X
2 and computes a minimum s-t cut S. Node
X is then split into two smaller nodes Xs = X ∩ S and
Xt = X \ S. These two nodes are connected by an edge e
whose capacity is equal to the capacity of the minimum s-t
cut. Node Xs corresponds to a graph Gs obtained from GX by
contracting the outside of the cut S into a single vertex t0 , and
node Xt corresponds to a graph Gt obtained by contracting the
inside of the cut S into a single vertex s0 . The two contracted
nodes s0 and t0 are set to correspond to the newly introduced
edge e. Finally, the edges incident to node X are reconnected
as follows: for each contracted vertex v ∈ VX \ X inside the
cut S, the corresponding edge φ(v) is reconnected to Xs , and
for each other contracted vertex, the corresponding edge is
reconnected to Xt .

17

Procedure Separate-All()
while there is (GX , X) ∈ G such that |X|
 > 1 do
{s, t} ← an arbitrary pair from X
;
2
Separate(GX , X, s, t);
Procedure Separate(GX = (VX , EX ), X, s, t)
S ← MinCut(GX , s, t);
Xs ← X ∩ S; Xt ← X \ S;
Add new nodes Xs and Xt connected by an edge e of
capacity λG (s, t) into T ;
Gs ← GX /(VX \ S → t0 ); Gt ← GX /(S → s0 );
G ← (G \ {(GX , X)}) ∪ {(Gs , Xs ), (Gt , Xt )};
φ(s0 ) ← e; φ(t0 ) ← e;
for each v ∈ VX \ X do
if v ∈ S then Reconnect φ(v) from X to Xs ;
else Reconnect φ(v) from X to Xt ;
Remove the node X from T ;

Figure 2 illustrates an example execution. The green dotted
lines show s-t min-cuts, and the orange lines denote the tree
and the corresponding sets. At first, the tree consists of only
a single node V . A pair {s, t} is selected and a min-cut is
computed, as shown in the leftmost figure. Node V is then
split into two sets and the graph is split into two contracted
graphs, as shown in the second figure. In the next step, another
pair is selected from the right node, and the corresponding
min-cut is computed, as in the third figure. The right node is
then split into two nodes and the edge incident to this node is
reconnected to Xs , because the contracted node created in the
first step is located inside the cut S. This process is repeated
until all the nodes become a singleton.
Note that the contracted graphs Gs and Gt are only created
for efficiency — we can correctly compute a cut tree using
the same graph GX instead of Gs and Gt . In this case,
when reconnecting edges at lines 14–16, instead of using the
contracted vertices s0 and t0 , we can use arbitrary vertices in
S and VX \ S, respectively1 .
For practical efficiency, we apply the following three naive
improvements to this basic algorithm. First, when constructing
contracted graphs Gs and Gt at line 11, instead of constructing
them from scratch, we reuse the original graph GX and convert
it into graphs Gs and Gt by creating new vertices {s0 , t0 } and
1 One may think that a future min-cut S 0 could cross the min-cut S, leaving
us unable to determine which side of the cut the corresponding edge should
reconnect with. However, from the submodularity and posimodularity of the
min-cut, using the minimal min-cut S ensures that such a case never occurs.
For details, see the paper by Gomory and Hu [24].

2

2

𝑆
𝑠

𝑠
𝑡

𝑋𝑠

𝑠
𝑡′

𝑠′

𝐺𝑠

𝐺𝑡

3

2

𝑆

𝑠

𝑡

𝑡

𝐺𝑡
𝑡′
𝑠′
𝐺𝑠

𝑋𝑡
𝑡

…

𝑋𝑠

𝑋𝑡

Fig. 2. Example execution of the Gomory-Hu algorithm.

reconnecting the edges between S and VX \ S. Because the
graph GX is never used again, it does not need to be restored.
Second, when the size of the obtained cut is 1, we do not
construct the contracted graphs. By renaming s as s0 , the graph
GX is exactly the same as the contracted graph Gt . Moreover,
the other contracted graph Gs is never used in the algorithm.
Thus, it is sufficient to set the vertex s to correspond to the
edge between nodes {s} and X \ {s}.
Third, instead of traversing all the contracted vertices at
line 14, we only traverse the vertices inside the cut S and
reconnect the corresponding edges to the node Xs . Then,
instead of creating the node Xt and reconnecting the remaining
edges, we just rename the node X as Xt .
Algorithm 1 contains two degrees of freedom: the first is
how to select a pair {s, t} at line 6 and the second is how to
compute the minimum s-t cut at line 8. Although any selection
strategy and any max-flow algorithm can correctly compute cut
trees, the choice can have a significant effect on performance.

Algorithm 2: Overall proposed construction algorithm.
1
2
3
4
5
6
7
8
9
10
11
12
13

Algorithm 3: Dinitz’s max-flow algorithm [24].
1
2

III. A LGORITHM OVERVIEW
In this section, we present an overview of our cut-tree
construction algorithm. The overall algorithm is described in
Algorithm 2. To computing min-cuts efficiently, we discuss the
max-flow algorithms best suited to real networks of interest
and propose practical improvements in Section IV. In our algorithm, instead of finding individual min-cuts by computing a
max-flow |V |−1 times, we detect multiple min-cuts at once by
tree packing (line 6). This technique is described in Section V.
The remaining graph is then separated by computing maxflows. As we would still need to compute the max-flows for
a huge number of vertex pairs, we do not compute each max
flow from scratch, but instead precompute some information
to speed up the multiple computations (line 8). This method,
which is explained in Section VI, is only applied to large
components, and each separated component is processed by
the basic method. We explain how to select separation pairs in
Section VII (lines 10–12). Finally, in Section VIII, we explain
the reduction rules applied at the beginning of the algorithm
(lines 3–4) to reduce the size of the input graph.
IV. S - T C UT C OMPUTATIONS
We now discuss one of the most important building blocks:
algorithms to compute minimum s-t cuts. Among the various
methods for determining the max-flow, we focus on Dinitz’s
algorithm [16], which is described in Algorithm 3. This first

Procedure Construct-Fast(G = (V, E))
Init(G);
// Graph reduction.
Decompose-2-Connected-Components();
Contract-Degree-2-Vertices();
// Heuristics to find a large portion of cuts.
Find-Cuts-by-Tree-Packing();
// Accelerated max-flow computations by preprocessing.
Find-Cuts-by-Goal-Oriented-Search();
// Separate the remaining components.
Separate-High-Degree-Pairs();
Separate-Adjacent-Pairs();
Separate-All();
return T ;

3
4
5
6

Procedure Max-Flow(G = (V, E), s, t)
f ← 0;
while there exists an s-t path in Gf do
D ← Construct-Shortest-Path-DAG(Gf , s, t);
while there is an f -augmenting path P in D do
Augment f along P
return f ;

constructs a shortest-s-t-path directed acyclic graph (DAG)2
D in the residual graph Gf . The flow is then augmented
by identifying an f -augmenting path that uses only edges
contained in D. When no f -augmenting paths can be found
(such a flow f is called a blocking flow with respect to
D), the shortest-path DAG D is updated. This process is
repeated until t becomes unreachable from s in Gf . For
uncapacitated networks, computing a blocking flow has linear
time complexity in the size of the DAG D3 . Thus, if the DAGs
are small and can be found efficiently, the algorithm is fast.
Whereas Dinitz’s original algorithm conducts a standard
unidirectional breadth-first search (BFS), we propose a bidirectional BFS to compute shortest-path DAGs, as this improves
the practical efficiency on networks of interest. The shortestpath computation itself is also important and has been the subject of considerable research. These studies have found that,
in real networks of interest, shortest-path DAGs are relatively
2 The shortest-s-t-path DAG of G is a subgraph of G consisting of only
edges contained in some shortest path from s to t.
3 For a capacitated network, it is known to take O(|V (D)||E(D)|) time;
however, such a worst case rarely occurs in practice.

small and can be efficiently constructed using bidirectional
BFS [8]. Although the graphs for which we need to construct
shortest-path DAGs are actually residual graphs of the original
real networks, we found that the Dinitz’s algorithm with bidirectional DAG construction works efficiently in preliminary
experiments.
The bidirectional BFS for constructing a DAG is as follows.
We iteratively construct a set of vertices Sd (Td ) that are
located at distance d from the vertex s (t). Initially, we set
S0 = {s}, T0 = {t}, ds = 0, and dt = 0. The following
process is then repeated until the sets Sds and Tdt intersect;
if the number of edges incident to Sds is smaller than that of
Tdt , we compute Sds +1 by traversing the edges incident to
Sds and increase ds by one; otherwise, we do the same for
Tdt . This procedure gives the distances of vertices contained
in balls of radius ds and dt from s and t, respectively. Finally,
by running a reverse-BFS from Sds ∩ Tdt using only the
edges from Si+1 to Si , or from Ti+1 to Ti , we can construct
the shortest-s-t-path DAG. In our implementation, we do not
explicitly construct the DAG, but only compute the distances;
when computing augmenting paths, we only use edges from
Si to Si+1 or from Ti+1 to Ti .
Other practical max-flow algorithms. The push-relabel
method [22] is often considered as the best method in practice. However, this approach does not involve a shortest-path
computation, and it would appear to be difficult to make it
bidirectional. Thus, it does not allow the structure of real
networks to be exploited. For segmentation tasks in computer
vision, Goldberg et al. [21] proposed a practical max-flow
algorithm called IBFS that uses a bidirectional search. For the
networks appeared in the segmentation tasks, the initial DAG
already contains all the vertices in the graph. Thus, simply
constructing DAGs in a bidirectional manner does not enhance
the computation speed. Their approach expresses the DAG
as two shortest-path trees that are dynamically updated after
each augmentation. However, in the networks we are interested
in, the initial DAG is very small and grows through such
augmentations; hence, this dynamic update approach would
not lead to a significant speed-up.
V. G REEDY T REE PACKING
Although we have designed a fast max-flow algorithm,
computing |V | − 1 max-flows to construct a cut tree remains
very time consuming; e.g., even if a single max-flow can be
computed in only 10 ms, it would take 100, 000 s to compute
all necessary max-flows in a graph with 10 million vertices. To
develop a much faster cut-tree algorithm, we must find mincuts without relying on max-flow algorithms. In this section,
we propose a greedy tree packing heuristic that identifies mincuts between multiple pairs at once without using a max-flow
algorithm.
For a directed graph and a vertex r, a subgraph is called an
r-tree if (i) its underlying undirected graph is a connected tree
(which may not be a spanning tree), (ii) r has no incoming
edges, and (iii) all other vertices in the tree have in-degrees

of exactly one. For an undirected graph G = (V, E), a set T
of edge-disjoint r-trees of the bidirected graph Ḡ = (V, Ē)4
is called an r-tree packing of G. The vertex r is called the
root of the tree packing. The following relationship between
an r-tree packing and the edge-connectivity was derived by
Bang-Jensen et al. [5]. For an undirected graph G = (V, E)
and its vertices r, v ∈ V , if there exist k edge-disjoint paths
from r to v, the connectivity between r and v is at least k.
Such edge-disjoint paths can be composed into a single set
of edge-disjoint r-trees for all v ∈ V \ {r}: if there exists
an r-tree packing T of an undirected graph G = (V, E), the
connectivity between r and v is at least the number of r-trees
in T containing v. Moreover, they showed that the converse
also holds: there exists an r-tree packing T such that, for any
vertex v ∈ V \ {r}, exactly λG (r, v) r-trees in T contain v.
In our algorithm, we greedily construct an r-tree packing
T . The details of this greedy algorithm are explained later.
The constructed tree packing T may not contain each vertex
v λG (r, v) times; however, if a vertex v appears exactly d(v)
times in T , we can confirm that the connectivity between v
and r is exactly d(v), and thus the cut {v} is the minimum
v-r cut. After constructing an r-tree packing, we can detect
all such vertices v and separate pairs {v, r} in linear time.
We apply this strategy α times by selecting each of the top α
degree vertices as the root r. The effects of the parameter α
are discussed in Section IX.
Our greedy packing algorithm proceeds as follows. Starting
from the bidirected graph Ḡ, we iteratively construct an rtree and remove its edges from Ḡ. Basically, we do not
want to create dead ends; if we remove all outgoing edges
from a vertex v, it will become a leaf in the subsequent tree
construction. If we use the BFS to construct an r-tree, the
first tree removes all the outgoing edges of r, and we cannot
construct a second tree. Thus the BFS should not be used. In
order to avoid creating such dead ends, we use a depth-first
search (DFS).
Additionally, we restrict the out-degree of each vertex in an
r-tree to being at most β. If the current visiting vertex in the
DFS is v and we have already used β edges from δ + (v) in
the current tree, we immediately backtrack from vertex v to its
parent without using the remaining edges in δ + (v). A larger
value of β would find a larger tree, but may create more dead
ends. We discuss the trade-off effects of different β values in
Section IX.
Figure 3 illustrates a tree-packing constructed by the greedy
DFS. Here, the highest degree vertex j is chosen as the root,
and the three trees are colored orange, blue, and green. The
degree-two vertices {a, b, i, k} appear twice in the tree-packing
and a subset of degree-three vertices {l, m} appear three
times. Thus, for each of these vertices, we can immediately
obtain a min-cut. Because the remaining degree-three vertices
{c, d, e, f, g, h} appear only twice, they cannot be separated
4 T can contain both directed edges uv and vu corresponding to a single
undirected edge.

𝑖
𝑎

𝑐

𝑒

𝑔

𝑙

𝑗
𝑏

𝑑

𝑓

ℎ

𝑚
𝑘

Fig. 3. An example of the tree-packing.

by this tree-packing, and are processed by other tree-packings
or different methods.
VI. G OAL -O RIENTED S EARCH
To construct a cut tree, we must compute the maximum st flows multiple times. Instead of computing each max-flow
from scratch, we propose to precompute some information
and accelerate these multiple computations for certain kinds
of vertex pairs.
In the Gomory-Hu algorithm, we are free to choose the separation pairs. To make the necessary precomputation possible,
instead of selecting an arbitrary pair, we first fix a sink t ∈ X.
When separating a set X containing t, we then always choose
a pair {s, t} for some vertex s ∈ X. Using this selection
strategy, we can compute the initial shortest-s-t-path DAG
used in Dinitz’s algorithm more efficiently than using the
bidirectional BFS. First, we precompute a shortest path tree
from the vertex t. When processing a pair {s, t}, we construct
a shortest-s-t-path DAG using DFS from vertex s and only
using edges uv for which the distance from u to t is exactly
the distance from v to t plus one, i.e., a shortest path from
u to t passes vertex v. To avoid updating the shortest-path
tree after the contraction, we only create the contracted graph
Gs . Instead of creating Gt , we reuse GX . As explained in
Section II, such a modification does not affect the correctness
of the algorithm.
As this construction only visits vertices contained in the
constructed DAG, it is much faster than the bidirectional BFS.
Computing the blocking flow has linear time complexity with
respect to the size of the DAG. Thus, if the first blocking
flow becomes the maximum flow, this strategy leads to a
significant speed-up. However, if the first blocking flow is not
the maximum, we need to update the shortest-s-t-path DAG.
As this second DAG computation uses the residual graph
rather than the original graph, we cannot use the precomputed
shortest-path tree.
To avoid time-consuming DAG updates, we search for
augmenting paths that use edges not on the DAG. In addition
to the edges uv for which the distance from u to t is exactly the
distance from v to t plus one, we also allow the use of detour
edges uv for which the distance from u to t is equal to the
distance from v to t. The resulting graph might not be a DAG
and could contain loops. When searching for an augmenting
path from s to t, we allow the use of at most γ detour edges,
where γ is a parameter. This can be done by extending each

vertex v to a set of vertices {v0 , . . . , vγ }, adding an edge ui vi
for each edge uv contained in the original DAG, and adding an
edge ui vi+1 for each detour edge uv. A larger value of γ will
produce more augmenting paths and increase the likelihood of
finding a maximum flow, but will have a higher computation
time. We discuss the trade-off effects of γ in Section IX.
As the networks of interest tend to have unbalanced cuts
that separate a small set of vertices from the remaining large
set of vertices, we only apply this strategy against the initial
set V and the highest degree vertex t.
VII. S ELECTING S EPARATION PAIRS
In this section, we discuss how to select the next separation
pair among the remaining vertex sets after the goal-oriented
search. In general, there are two choices: select a pair with
a balanced min-cut to make the graphs obtained by the
contraction smaller, or select a pair whose min-cut is easy
to compute. Here, the term balanced means that both |S| (the
inside of the cut) and |VX \ S| (the outside of the cut) are
large.
A. High Degree Pairs
Goldberg and Tsioutsiouliklis [23] developed heuristics
to find such balanced min-cuts. However, the networks of
interest to us do not seem to have well-balanced min-cuts.
For example, it would be surprising if a social graph of
2 million vertices could be split into two components of 1
million vertices just by removing 100,000 edges. Thus, it is
not important to make the cut balanced, and it is better to
focus on the pairs whose min-cut can be easily computed.
In our algorithm, we attempt to make the graphs smaller by
finding somewhat balanced cuts. Hence, we try to split the
top-k degree vertices before moving to the second selection
strategy. In this study, we use k = 10. We split large-degree
vertices because the size of the min-cut is at most the size
of the trivial cut {s}, which is equal to the degree of s, and
therefore small-degree vertices are less to have balanced cuts
than high-degree vertices.
B. Adjacent Pairs
If the distance between s and t is d, the bidirectional BFS
visits vertices contained in balls whose radius is approximately
d/2 from s and t. Therefore, the smaller the distance, the
faster the bidirectional BFS procedure, and a cut between
nearby vertices would be easy to find using the bidirectional
form of Dinitz’s algorithm. In our algorithm, we choose a
pair {s, t} ⊆ X such that s and t are adjacent in GX . If
there are no such pairs, we choose an arbitrary pair from the
remaining vertices. Note that such a case can actually occur:
consider a graph G = ({s, t, a, b, c}, {sa, sb, sc, at, bt, ct});
after separating pairs {s, a}, {s, b}, and {s, c}, we need to
separate the non-adjacent pair {s, t}.
VIII. G RAPH R EDUCTIONS
To reduce the size of the input graph before applying the
algorithm, we use the following two strategies.

TABLE II
DATA SIZE AND AVERAGE QUERY TIME .
Dataset
ca-GrQc
ca-CondMat
soc-Epinions1
com-DBLP
com-Youtube
web-Google
web-BerkStan
soc-Pokec
soc-LiveJournal1
hollywood-2011
com-Orkut
indochina-2004
arabic-2005
it-2004
twitter-2010

Graph size

Cut-tree size

56KB
364KB
1.5MB
4.0MB
11.4MB
16.5MB
25.4MB
85.1MB
163.5MB
436.8MB
447.0MB
576.0MB
2.1GB
3.8GB
4.5GB

40KB
180KB
0.6MB
2.4MB
8.7MB
6.7MB
5.2MB
12.5MB
37.0MB
16.6MB
23.4MB
56.6MB
0.2GB
0.3GB
0.3GB

Query time
0.069
0.073
0.101
0.119
0.142
0.181
0.177
0.168
0.337
0.139
0.137
0.405
0.469
0.369
0.294

µs
µs
µs
µs
µs
µs
µs
µs
µs
µs
µs
µs
µs
µs
µs

A. Decomposing 2-Connected Components
Let us assume that the input graph is connected; otherwise,
we can construct cut trees separately for each connected
component. We can compute all the cuts of size 1, called
bridges, in linear time [32]. For any pair that is not separated
by bridges, the max-flow does not pass the bridges. Thus,
we can simply remove all the bridges and deal with each 2connected component separately.
This reduction not only reduces the graph size, but also has
a positive effect on the greedy tree packing heuristic described
in Section V. If a vertex v has a neighbor u of degree 1, u
can only become a leaf of a tree, and no r-trees can use the
edge from u to v. Thus, such a vertex v cannot appear d(v)
times in the constructed disjoint r-trees. After applying this
reduction, all vertices of degree 1 are removed, and therefore
more min-cuts can be found by greedy tree packing.
B. Contracting Degree-2 Vertices
If there is a vertex v of degree 2, the connectivity between
v and any other vertex in the same 2-connected component is
exactly 2. For any other vertices s and t, if an s-t flow uses
one of the edges incident to v, it must use the other one. Thus,
we can replace vertex v and its incident edges with an edge
connecting the neighbors of v.
IX. E XPERIMENTAL E VALUATION
A. Setup
Environment. We conducted experiments on a Linux machine
with an Intel Xeon X5650 processor (2.67 GHz) and 96 GB
main memory. All algorithms were implemented in C++ and
compiled using gcc 4.8.4 with the -O3 option.
Algorithms. We compared the proposed method with two
state-of-the-art cut-tree construction algorithms. (1) GH G [23],
which combines the Gomory–Hu algorithm with balanced
min-cut heuristics and the Hao–Orlin algorithm [26]. (2)
Lemon [15], which is a highly tuned implementation of combinatorial optimization algorithms. For the proposed algorithm,

unless otherwise stated, we set the number of tree packings
α = 1, the breadth limit parameter β = ∞ (i.e., no limit), and
the search relaxation parameter γ = 2, which we recommend
as a robust setting.
Datasets. We used real-world social and web graphs that are
publicly available from the Stanford Large Network Dataset
Collection [27] and Laboratory for Web Algorithms [6], [7].
Table I summarizes the number of vertices and edges in
these datasets. The web-Google, web-BerkStan, indochina2004, arabic-2005, and it-2004 datasets are web graphs; the
others are social graphs.
B. Construction
Our main focus is on reducing the cut-tree construction
time. We compared the following six versions of the proposed algorithm. A0 is the plain Gomory–Hu algorithm with
a standard implementation of Dinitz’s max-flow algorithm.
A1 is another implementation of the Gomory–Hu algorithm
using the bidirectional blocking flow algorithm introduced
in Section IV. A2 uses the same bidirectional blocking flow
algorithm, but employs graph reduction techniques such as
2-connected component decomposition and degree-2 vertex
contraction, and applies the high-degree pair separation strategy. In addition to the above, A3 employs the adjacent pair
separation strategy, and A4 also uses greedy tree packing. A5
further conducts the goal-oriented search. A5 is the overall
proposed algorithm using the whole set of new techniques,
and is thus equivalent to Algorithm 2.
Table I lists the construction times achieved by each
algorithm. We wish to emphasize that the A5 algorithm,
which includes all of the proposed techniques, successfully
constructed cut trees for billion-scale web and social graphs
(it-2004 and twitter-2010) in 8 h and 4 h, respectively. The
baseline methods, GH G and Lemon, took several hours for a
million-scale social graph (com-DBLP), and failed to construct
complete cut trees for larger networks within the time limit of
10 h. Therefore, the proposed method improves the scalability
of cut-tree construction by several orders of magnitude.
The results from different versions of the proposed method
show that more datasets were successfully processed within the
time limit as more of the new techniques were employed (i.e.,
from A0 to A5), and the time required to treat each dataset
consistently decreased. These results indicate that most of the
proposed techniques are effective and essential for scalable
cut-tree construction.
C. Data Size and Query Time
To confirm the practicality of cut trees, we briefly discuss
their data size and query times. Note that these metrics are
independent of the construction algorithm (except the ways to
break arbitrariness).
The data sizes of the resulting cut trees are listed in Table II,
together with those of the original graphs. It is clear that
the cut trees are much smaller than the graphs. This is as
expected, as the graph and cut tree have sizes Θ(|E|) and
Θ(|V |), respectively.

TABLE I
DATASET INFORMATION AND CUT- TREE CONSTRUCTION TIME ( S ). DNF DENOTES THAT THE ALGORITHM DID NOT FINISH WITHIN 10 H .

Name
ca-GrQc
ca-CondMat
soc-Epinions1
com-DBLP
com-Youtube
web-Google
web-BerkStan
soc-Pokec
soc-LiveJournal1
hollywood-2011
com-Orkut
indochina-2004
arabic-2005
it-2004
twitter-2010

Dataset
|V |

|E|

A0

A1

5, 242
23, 133
75, 879
317, 080
1, 134, 890
875, 713
685, 230
1, 632, 803
4, 847, 571
2, 180, 759
3, 072, 441
7, 414, 866
22, 744, 080
41, 291, 594
41, 652, 230

14, 484
93, 439
405, 740
1, 049, 866
2, 987, 624
4, 322, 051
6, 649, 470
22, 301, 964
42, 851, 237
114, 492, 816
117, 185, 083
150, 984, 819
553, 903, 073
1, 027, 474, 947
1, 202, 513, 046

3.0
110.1
977.2
DNF
DNF
DNF
DNF
DNF
DNF
DNF
DNF
DNF
DNF
DNF
DNF

0.1
1.4
7.0
72.7
307.0
365.1
569.9
3501.7
DNF
22681.3
DNF
DNF
DNF
DNF
DNF

4000
com-Orkut
indochina-2004

0.1
0.8
5.0
28.9
134.7
62.6
327.1
2942.8
9543.3
11649.8
23376.3
7254.4
DNF
DNF
DNF

A5

0.1
0.7
3.8
24.2
76.3
43.9
102.7
2216.7
6043.3
10392.1
16511.2
1880.2
20961.2
DNF
DNF

< 0.1
0.2
0.7
9.9
9.6
50.2
40.3
71.8
3178.2
533.8
679.0
1169.3
17836.6
28792.3
15323.1

1000

com-Orkut
indochina-2004

2000
1000

0

1

2

Tree packing

4

(a) Number of tree packings (α)

8

0

4.0
256.7
2444.1
28212.1
DNF
DNF
DNF
DNF
DNF
DNF
DNF
DNF
DNF
DNF
DNF

2.2
75.7
1113.5
22098.0
DNF
DNF
DNF
DNF
DNF
DNF
DNF
DNF
DNF
DNF
DNF

com-Orkut
indochina-2004

3000

Time (s)

2000

Baselines
GH G [23] Lemon [15]

4000

3000

Time (s)

Time (s)

0.1
1.2
4.2
62.9
164.0
294.7
530.8
2996.9
DNF
20622.3
DNF
DNF
DNF
DNF
DNF

A4

4000

3000

0

Proposed Algorithms
A2
A3

2000
1000

0

1

2

4

8

Breadth limit

16

inf

(b) Breadth limit of tree packing (β)

0

0

1

Search relaxation
(c) Search relaxation (γ)

Fig. 4. Runtime for various performance parameters.

Table II also gives the average query time for computing
the s-t cut size from the cut trees for 107 random pairs of
vertices. Using a naive query algorithm that simply ascends
the trees from both ends, the average query time is very small
at less than 1 µs. This is because the cut trees for these real
graphs tend to be very shallow.

limit of searches during tree packing. For indochina-2004,
setting β = ∞ (no breadth limit) results in construction that
are approximately twice as fast as for other settings. This
is why we generally recommend β = ∞ for robustness. In
contrast, for com-Orkut, enabling the breadth limit accelerates
the algorithm up to 1.5 times. In general, β should be set to
a moderate constant when handling social networks.

D. Parameter Analysis
Finally, we discuss the effect of different parameter values.
In these experiments, we used a social network dataset, comOrkut, and a web graph dataset, indochina-2004. The trend for
these two networks can generally be observed in other social
and web graphs.
Number of tree packings. Figure 4a illustrates the construction time for various values of α, which is the number of tree
packings. From the results for α ≥ 1, we see that applying tree
packing multiple times is not beneficial. The results for α = 0
and 1 indicate that tree packing is effective for indochina2004, but is not effective for com-Orkut. The same trend can
be observed for other web and social graphs.
Breadth limit of tree packing. Figure 4b shows the construction time for different value of β, which is the breadth

Search relaxation. Figure 4c shows the construction time for
various γ, which is the maximum number of detour steps
allowed during goal-oriented searches. It can be observed that
a small positive value of γ drastically reduces the runtime for
com-Orkut. Indeed, with γ = 0, the algorithm did not finish
within the time limit. In contrast, changes in the value of γ
had relatively little effect with the indochina-2004 dataset. This
is because indochina-2004 was separated earlier by balanced
cuts. In general, web graphs tend to have more balanced cuts
than social graphs, and search relaxation is more effective for
social graphs.
X. A PPLICATIONS
We now discuss some applications of cut trees to demonstrate the utility of the proposed algorithm.

2

Algorithm 4: Computing the connectivity distribution.

2
3
4
5
6
7

1014
1012
1010
108
106
104
102
100

1
2
3
4
5
6
7

Procedure Connectivity-Dendrogram(T = (VT , ET , cT ))
V ← {{v} | v ∈ VT }; VT0 ← {{v} | v ∈ VT }; ET0 ← ∅;
`({v}) = ∞ for all v ∈ VT ;
for e ∈ ET in descending order of c(e) do
S, T ← sets in V to which the ends of e belong;
X ← S ∪ T ; V ← (V \ {S, T }) ∪ {X};
VT0 ← VT0 ∪ {X}; ET0 ← ET0 ∪ {(S, X), (T, X)};
`(X) = c(e);
return T 0 = (VT0 , ET0 ) and `;

8

return f ;

Number of pairs (CDF)

8

Procedure Connectivity-Distribution(T = (VT , ET , cT ))
C = {cT (e) | e ∈ ET }; V ← {{v} | v ∈ VT }; f ← ∅;
for x ∈ C in decreasing order do
f (x) ← 0;
for e ∈ ET such that c(e) = x do
S, T ← sets in V to which the ends of e belong;
f (x) ← f (x) + |S| × |T |;
V ← (V \ {S, T }) ∪ (S ∪ T );

15

com-Orkut
indochina-2004

9

13
16

7

12

8

17

5

10

14

6

11
1
0
2

100

101

102

103

Connectivity

104

105

4
3

(a) A graph
Fig. 5. Examples of connectivity distribution.

Connectivity

1

Algorithm 5: Computing the connectivity dendrogram.

1
2
3
4
5
6
7

0 1 2 3 4 5 6 7 8 9 10 11121314 151617

(b) The dendrogram

Fig. 6. An example of a graph and its connectivity dendrogram.

A. Connectivity Distribution

B. Connectivity Dendrogram

The common structural properties of real networks are of
interest to the data mining community, although they have
not yet been comprehensively studied. We believe that the
connectivity distribution represents a new tool for the structural
analysis of networks, and have designed an efficient algorithm
using cut trees.
We define the connectivity distribution as the distribution of
connectivity between every pair of vertices. More specifically,
the connectivity distribution of a graph G is {fG (k)}k , where
fG (k) denotes the
pairs whose connectivity

P number of vertex
is k. Note that k fG (k) = n2 .
As the total number of pairs is quadratic, it is reasonable
to assume that its computation will require quadratic time.
However, we propose an algorithm that exactly computes the
connectivity distribution in O(n log n) time for a given cut
tree. The procedure is described in Algorithm 4. For each
edge in the cut tree, the underlying idea of the algorithm is to
count the number of pairs with that corresponding minimum
cut.
In experiments, this algorithm required only 0.06 s and
0.12 s for cut trees of the com-Orkut and indochina-2004
datasets, respectively (excluding the time taken to construct
the cut trees), as illustrated in Figure 5. Interestingly, the
connectivity seems to follow a power law, similar to the degree
distributions. However, deeper analysis of these distributions
is beyond the scope of this paper. We emphasize that our
algorithms enable the connectivity distributions of large-scale
networks to be studied for the first time.

As the connectivity can be considered to indicate the
strength of a relationship, we can define hierarchical clustering
based on connectivity. This can be visualized using a connectivity dendrogram. Figure 6 shows a graph and its connectivity
dendrogram.
The dendrogram of a cut tree can also be easily obtained. Algorithm 5 explains the procedure, which works in
O(n log n) time. Given a cut tree, it returns a tree T 0 =
(VT0 , ET0 ) and a function `, where each X ∈ VT0 is a subset
of the vertices of the original graph, and `(X) denotes the
connectivity of vertex set X. The underlying idea of the
algorithm is to look at edges in the cut tree in descending order
of their weights and merge the vertex subsets corresponding to
both endpoints. In experiments, this algorithm required 0.20 s
and 0.30 s with the com-Orkut and indochina-2004 datasets,
respectively (excluding the time taken to construct the cut
trees).
XI. R ELATED W ORK
Graph Indexing Methods. Because of their importance
as back-ends for efficient network analysis, graph indexing
methods, i.e., methods that precompute and store some data
structures to accelerate certain kinds of computation, have
been studied in the data mining community. Examples include
methods for the point-to-point shortest-path distance [2], [13],
[14], single-source shortest-path distance [10], [35], neighborhood function [11], [30], and personalized pagerank [19]. Cut
trees can also be considered as an indexing method for graphs.

Cut-Tree Construction Algorithms. There has been little
work on cut-tree construction algorithms, other than the
original algorithm of Gomory and Hu [24]. Gusfield’s algorithm [25] is very similar to the Gomory–Hu algorithm,
but does not include a contraction step. Though slightly
simpler than the Gomory–Hu algorithm, preliminary experiments indicate that Gusfields algorithm is almost always
slower for networks of interest. Goldberg and Tsioutsiouliklis
proposed practical improvements to the Gomory–Hu algorithm
for instances arising from optimization problems [23]. Cohen
et al. studied thread-level parallelization of the Gomory–Hu
algorithm [12].
XII. C ONCLUSIONS
In this paper, we have described a new algorithm for
constructing cut trees from massive real-world graphs. Our
overall algorithm combines several new techniques covering
graph reduction, max-flow acceleration, and min-cut enumeration heuristics. These techniques are tailored to real-world
networks, and, as confirmed by our experimental results, the
resulting algorithm works surprisingly well. Specifically, our
algorithm constructed cut trees for web and social graphs with
more than one billion edges, some three orders of magnitude
larger than can be handled by previous methods. We also
discussed some applications of cut trees to graph data mining.
Repeatability. As the implementations and datasets used in
our experiments are available online, our results are completely
replicable. The proposed method is available from http://git.io/
cut-tree. The previous methods are available from http://www.
cs.princeton.edu/∼kt/cut-tree/ and https://lemon.cs.elte.hu/trac/
lemon. The datasets are available from http://snap.stanford.
edu/data and http://law.di.unimi.it/datasets.php.
Acknowledgement. This work was supported by JSPS Grantin-Aid for Research Activity Startup (No. 15H06828) and JST,
PRESTO.
R EFERENCES
[1] T. Akiba, Y. Iwata, Y. Sameshima, N. Mizuno, and Y. Yano. Cut tree
construction from massive graphs. In ICDM, 2016. to appear.
[2] T. Akiba, Y. Iwata, and Y. Yoshida. Fast exact shortest-path distance
queries on large networks by pruned landmark labeling. In SIGMOD,
pages 349–360, 2013.
[3] T. Akiba, Y. Iwata, and Y. Yoshida. Linear-time enumeration of maximal
k-edge-connected subgraphs in large networks by random contraction.
In CIKM, pages 909–918, 2013.
[4] Y. Asano, T. Nishizeki, M. Toyoda, and M. Kitsuregawa. Mining
communities on the web using a max-flow and a site-oriented framework. IEICE transactions on information and systems, 89(10):2606–
2615, 2006.
[5] J. Bang-Jensen, A. Frank, and B. Jackson. Preserving and increasing
local edge-connectivity in mixed graphs. SIAM J. Discrete Math.,
8(2):155–178, 1995.
[6] P. Boldi, M. Rosa, M. Santini, and S. Vigna. Layered label propagation: a multiresolution coordinate-free ordering for compressing social
networks. In WWW, pages 587–596, 2011.
[7] P. Boldi and S. Vigna. The webgraph framework I: compression
techniques. In WWW, pages 595–602, 2004.
[8] M. Borassi and E. Natale. KADABRA is an adaptive algorithm for
betweenness via random approximation. CoRR, abs/1604.08553, 2016.

[9] L. Chang, J. X. Yu, L. Qin, X. Lin, C. Liu, and W. Liang. Efficiently
computing k-edge connected components via graph decomposition. In
SIGMOD, pages 205–216, 2013.
[10] J. Cheng, Y. Ke, S. Chu, and C. Cheng. Efficient processing of distance
queries in large graphs: A vertex cover approach. In SIGMOD, pages
457–468, 2012.
[11] E. Cohen. All-distances sketches, revisited: HIP estimators for massive
graphs analysis. IEEE TKDE, 27(9):2320–2334, 2015.
[12] J. Cohen, L. A. Rodrigues, and E. P. Duarte Jr. A parallel implementation
of gomory-hu’s cut tree algorithm. In SBAC-PAD, pages 124–131, 2012.
[13] A. Das Sarma, S. Gollapudi, M. Najork, and R. Panigrahy. A sketchbased distance oracle for web-scale graphs. In WSDM, 2010.
[14] D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck. Robust distance
queries on massive networks. In ESA, pages 321–333. 2014.
[15] B. Dezs, A. Jüttner, and P. Kovács. Lemon - an open source c++ graph
template library. Electron. Notes Theor. Comput. Sci., 264(5):23–45,
2011.
[16] E. A. Dinic. Algorithm for Solution of a Problem of Maximum Flow in
a Network with Power Estimation. Soviet Math Doklady, 11:1277–1280,
1970.
[17] P. Elias, A. Feinstein, and C. E. Shannon. A note on the maximum flow
through a network. Information Theory, IRE Transactions on, 2(4):117–
119, 1956.
[18] L. R. Ford and D. R. Fulkerson. Maximal flow through a network.
Canadian journal of Mathematics, 8(3):399–404, 1956.
[19] Y. Fujiwara, M. Nakatsuji, T. Yamamuro, H. Shiokawa, and M. Onizuka.
Efficient personalized pagerank with accuracy assurance. In KDD, pages
15–23, 2012.
[20] A. V. Goldberg. Finding a maximum density subgraph. University of
California Berkeley, CA, 1984.
[21] A. V. Goldberg, S. Hed, H. Kaplan, R. E. Tarjan, and R. F. F. Werneck.
Maximum flows by incremental breadth-first search. In Algorithms ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany,
September 5-9, 2011. Proceedings, pages 457–468, 2011.
[22] A. V. Goldberg and R. E. Tarjan. A new approach to the maximum-flow
problem. J. ACM, 35(4):921–940, 1988.
[23] A. V. Goldberg and K. Tsioutsiouliklis. Cut tree algorithms: an
experimental study. Journal of Algorithms, 38(1):51–83, 2001.
[24] R. E. Gomory and T. C. Hu. Multi-terminal network flows. Journal
of the Society for Industrial and Applied Mathematics, 9(4):551–570,
1961.
[25] D. Gusfield. Very simple methods for all pairs network flow analysis.
SIAM Journal on Computing, 19(1):143–155, 1990.
[26] J. Hao and J. B. Orlin. A faster algorithm for finding the minimum cut
in a directed graph. Journal of Algorithms, 17(3):424–446, 1994.
[27] J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network
dataset collection. http://snap.stanford.edu/data, 2014.
[28] D. Liben-Nowell and J. Kleinberg. The link-prediction problem for
social networks. Journal of the American society for information science
and technology, 58(7):1019–1031, 2007.
[29] J. B. Orlin. Max flows in o(nm) time, or better. In STOC, pages 765–774,
2013.
[30] C. R. Palmer, P. B. Gibbons, and C. Faloutsos. ANF: A fast and scalable
tool for data mining in massive graphs. In KDD, pages 81–90, 2002.
[31] L. Qin, R.-H. Li, L. Chang, and C. Zhang. Locally densest subgraph
discovery. In KDD, pages 965–974, 2015.
[32] R. E. Tarjan. A note on finding the bridges of a graph. Information
Processing Letters, 2(6):160–161, 1974.
[33] C. Tsourakakis. The k-clique densest subgraph problem. In WWW,
pages 1122–1132, 2015.
[34] R. Zhou, C. Liu, J. X. Yu, W. Liang, B. Chen, and J. Li. Finding
maximal k-edge-connected subgraphs from a large graph. In EDBT,
pages 480–491, 2012.
[35] A. D. Zhu, X. Xiao, S. Wang, and W. Lin. Efficient single-source shortest
path and distance queries on large graphs. In KDD, pages 998–1006,
2013.

