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

2.6 Graph Algorithms 43

2/2

3/3

3/3

1/1

2/2 1/2

2/3

0/3 2/3

v 3 v 4

v 1 v 2

s t

2

3

3

1

(^21)
1
1
(^23)
12
v 3 v 4
v 1 v 2
s t
(a) Flow Graph
(b) Residual Graph
Figure 2.25. Augmenting Flow Graph.
being pushed.^3 Given flowf(u,v) in the original graph and flowfR(u,v) WEAK LINK
andfR(v,u) in the residual graph, we can augment the flow as follows:
faugmented(u,v)=f(u,v)+fR(u,v)−fR(v,u). (2.24)
Example 2.5.Consider the graph in Figure2.24(b) and the augmenting
path s,v 1 ,v 3 ,v 4 ,v 2 ,t. It has a minimum capacity of 1 along the path, so
the flow quantity will be 1. We can augment the original graph with this
path. The new flow graph and its corresponding residual graph are shown
in Figure2.25. In the new residual, no more augmenting paths can be found.
The Ford-Fulkerson algorithm will find the maximum flow in a network,
but we skip the proof of optimality. Interested readers can refer to the
bibliographic notes for proof of optimality and further information. The
algorithm is provided in Algorithm2.6.
Algorithm 2.6Ford-Fulkerson Algorithm
Require:Connected weighted graphG(V,E,W), Sources, Sinkt
1: return A Maximum flow graph
2: ∀(u,v)∈E,f(u,v)= 0
3: whilethere exists an augmenting pathpin the residual graphGRdo
4: Augment flows byp
5: end while
6: Return flow value and flow graph;