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 41

v 1

11/14

12/12

4/4

4/9

11/16

15/20

8/13

1/4 7/7

v 2 v 4

v 3

s t

Figure 2.23. A Sample Flow Network with Flows and Capacities.

Flow Quantity

The flow quantity (or value of the flow) in any network is the amount

of outgoing flow from the source minus the incoming flow to the source.

Alternatively, one can compute this value by subtracting the outgoing flow

from the sink from its incoming value:

flow=

∑

v

f(s,v)−

∑

v

f(v,s)=

∑

v

f(v,t)−

∑

v

f(t,v). (2.21)

Example 2.4.The flow quantity for the example in Figure2.23is 19:

flow=

∑

v

f(s,v)−

∑

v

f(v,s)=(11+8)− 0 = 19. (2.22)

Our goal is to find the flow assignments to each edge with the maximum

flow quantity. This can be achieved by a maximum flow algorithm. A

well-established one is the Ford-Fulkerson algorithm [Ford and Fulkerson,

1956].

Ford-Fulkerson Algorithm

The intuition behind this algorithm is as follows: Find a path from source

to sink such that there is unused capacity for all edges in the path. Use that

capacity (the minimum capacity unused among all edges on the path) to

increase the flow. Iterate until no other path is available.

Before we formalize this, let us define some concepts.

Given a flow in network G(V,E,C), we define another network

GR(V,ER,CR), called theresidualnetwork. This network defines how

much capacity remains in the original network. The residual network has

an edge between nodesuandvif and only if either (u,v)or(v,u) exists

in the original graph. If one of these two exists in the original network, we

would havetwoedges in the residual network: one from (u,v) and one from

(v,u). The intuition is that when there is no flow going through an edge in

the original network, a flow of as much as the capacity of the edge remains