Social Media Mining: An Introduction

P1: WQS Trim: 6.125in×9.25in Top: 0.5in Gutter: 0.75in
CUUS2079-02 CUUS2079-Zafarani 978 1 107 01885 3 January 13, 2014 16:38

42 Graph Essentials

2/2

2/3

2/3

1/1

2/2

1/2

1/3

1/3 1/3

v 3 v 4

v 1 v 2

s t

2

2

1

1

1 2

(^21)
1
2
(^11221)
v 3 v 4
v 1 v 2
s t
(a) Flow Network
(b) Residual Network
Figure 2.24. A Flow Network and Its Residual.
in the residual. However, in the residual network, one has the ability to send
flow in the opposite direction to cancel some amount of flow in the original
network.
Theresidual capacity cR(u,v) for any edge (u,v) in the residual graph
is
cR(u,v)=

{

c(u,v)−f(u,v)if(u,v)∈E

f(v,u)if(u,v) ∈E (2.23)

A flow network example and its resulted residual network are shown in

Figure2.24. In the residual network, edges that have zero residual capacity

are not shown.

Augmentation and Augmenting Paths

In the residual graph, when edges are in the same direction as the original

graph, their capacity shows how much more flow can be pushed along that

edge in the original graph. When edges are in the opposite direction, their

capacities show how much flow can be pushed back on the original graph

edge. So, by finding a flow in the residual, we canaugmentthe flow in

the original graph. Any simple path fromstotin the residual graph is an

augmentingpath. Since all capacities in the residual are positive, these paths

can augment flows in the original, thus increasing the flow. The amount of

flow that can be pushed along this path is equal to the minimum capacity

along the path, since the edge with that capacity limits the amount of flow